Concept三元可满足性问题
3SAT
A classical NP-complete problem: given a set of three-literal Boolean clauses, determine whether there exists an assignment of variables that makes all clauses true. It is the standard problem for studying computational complexity lower bounds.
Timeline (last 90 days)
Oct 30
ETH was proposed by Russell Impagliazzo and Ramamohan Paturi, conjecturing that the 3SAT problem cannot be solved in subexponential time.
Unverified50%