Remix.run Logo
▲ dooglius 2 hours ago

The proof appears to be a sub-exponential algorithm for #3-SAT not just 3-SAT, I think this is considered a much stronger result?

▲geysersam an hour ago | parent [-]

Isn't 3-SAT NP-complete?

▲krackers an hour ago | parent | next [-]

Yes. Up until now, it was unknown whether containment of NP in EXPTIME was strict or not. (Obviously you can brute-force all possible witnesses, so any problem in NP can be solved in EXPTIME, it was open whether you could do better than that.)

Showing 3SAT (technically #3SAT) can be solved in less than EXPTIME resolves this. It's only slightly subexponential, not even quasipolynomial, but it is a very surprising result. And that too a constructive algorithm.

Edit: Apparently not true, the constructive algorithm given may not survive under reductions. See discussion in https://news.ycombinator.com/item?id=50251661

▲LPisGood an hour ago | parent | prev [-]

It is the canonical NP complete problem.