Abstract
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.