printable pdf
比利时vs摩洛哥足彩
,
比利时vs摩洛哥足彩
,
university of california san diego
****************************
math 268 - computability and logic
nicholas sieger
uc san diego
the satisfiability threshold in random k-sat
abstract:
consider a uniformly random k-sat instance with a fixed ratio of the number of clauses to the number of variables. as the clause-variable ratio increases, a curious phenomenon appears. with high probability the random instance is satisfiable below a certain threshold and unsatisfiable above the same threshold. this talk will give an overview of the problem of determining the precise threshold for random k-sat, including various algorithmic approaches, the connections to statistical physics, friedman's sharp threshold theorem, and the determination of the k-sat threshold for large k by ding, sun, and sly in 2014.
february 12, 2024
4:00 pm
apm 7218
research areas
logic and computational complexity****************************
