A Data-Centric View on Computational Complexity: P = NP
share
P = NP SAT ∈ P. We propose this to be true because the satisfiability problem for propositional logic formulas (SAT) is the Existential Halting Problem in disguise and therefore undecidable. Since the input space is finite, however, SAT can still be solved by simulating no less than all possible, that is exponentially many, configurations. In a nutshell, the halting portion of a program formulated for a Turing Machine can be expressed as one long propositional logic formula based on previous memory states (binary variables). Therefore solving SAT by analyzing a formula syntactically would equate to solving the Existential Halting Problem. A propositional logic formula is nothing else but a specific encoding of a truth table. There are 2^2^n unique truth tables of n binary variables and this means we need at least 2^n bits to universally encode any truth table. Thus simulating less than 2^n configurations would be in violation of the pigeon hole principle and therefore imply lossy compression. SAT requires an exact solution, however, and not an approximate one. Consequently, SAT needs an exponential amount of decisions to be solved.
READ FULL TEXT