Skip to main content
MANIFOLD
When will it be proven that SAT cannot be solved in linear time?
1
Ṁ125Ṁ65
2030
November 4, 2030
17%
Before 2028
24%
Before 2029
34%
Before 2030
41%
Before 2031
50%
Before 2032

This market resolves all thresholds according to the year in which a valid, unconditional proof of the following claim first becomes public:

SAT ∉ DTIME(n) on deterministic multitape Turing machines.

That is, there is no deterministic multitape Turing machine M and constant c such that M decides CNF-SAT and halts within cn steps on every input. Here n is the length in bits of the formula under any standard encoding (e.g., DIMACS-style CNF).

The proof must be broadly accepted by experts, with no unresolved substantive errors discovered after posting (I'll wait at least 3 months for a consensus). A proof that P≠NP, or any result implying the statement, also resolves the market.

If the claim is shown to be false or independent of ZFC, or no qualifying proof appears before a threshold’s date, that threshold resolves NO.

Get
Ṁ1,000
to start trading!