Submission + - The Exponential Time Hypothesis might be false (github.com)
FeelGood314 writes: OpenAI is claiming a sub exponential time solution to the 3-SAT problem
A non deterministic computer is one that when it has to make a decision it can always guess correctly.
NP is the set of problems a nondeterministic computer can solve in polynomial time and that the solution can be verified in polynomial time on a deterministic computer.
NP-Complete is a set of NP problems that are believed to be hard (i.e. would require exponential time to solve). Further the set of NP-complete problems are equivalent in that you can convert any NP-Complete problem into any other NP-Complete problem in polynomial time. That is to say if you can solve any NP-Complete problem you can solve any other one with at most a polynomial time extra effort.
The 3-SAT (3-Satisfiability) problem asks whether a given Boolean formula in 3-CNF (Conjunctive Normal Form) can be made true by assigning a value of true or false to each of its variables. The 3-SAT problem is in NP-Complete.
Thus if 3-SAT can be solved in under exponential time then all NP-Complete problems can be solved in under exponential time.
Note: sub exponential time still doesn't mean polynomial time.
A non deterministic computer is one that when it has to make a decision it can always guess correctly.
NP is the set of problems a nondeterministic computer can solve in polynomial time and that the solution can be verified in polynomial time on a deterministic computer.
NP-Complete is a set of NP problems that are believed to be hard (i.e. would require exponential time to solve). Further the set of NP-complete problems are equivalent in that you can convert any NP-Complete problem into any other NP-Complete problem in polynomial time. That is to say if you can solve any NP-Complete problem you can solve any other one with at most a polynomial time extra effort.
The 3-SAT (3-Satisfiability) problem asks whether a given Boolean formula in 3-CNF (Conjunctive Normal Form) can be made true by assigning a value of true or false to each of its variables. The 3-SAT problem is in NP-Complete.
Thus if 3-SAT can be solved in under exponential time then all NP-Complete problems can be solved in under exponential time.
Note: sub exponential time still doesn't mean polynomial time.