SAT is Not Solvable in Constant Time (Q7361121)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry SAT_Not_Const_Time
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | SAT is Not Solvable in Constant Time |
AFP entry SAT_Not_Const_Time |
Statements
26 March 2026
0 references
Daniel Shea
0 references
SAT is Not Solvable in Constant Time (English)
0 references
This entry establishes that the Boolean Satisfiability Problem (SAT) cannot be decided by a deterministic Turing machine in constant time \(O(1)\). The core of the argument rests on an indistinguishability invariant: a Turing machine bounded by constant time \(C\) can only ever read the first \(C+1\) cells of its input tape. Consequently, any language decided in constant time must be a prefix language. We then show that SAT is not uniquely determined by any finite prefix, yielding the impossibility result.
0 references
