What One Has to Know When Attacking P vs. NP (Extended Abstract)

摘要

Mathematics was developed as a strong research instrument with fully verifiable argumentations. We call any consistent and sufficiently powerful formal theory that enables to algorithmically verify for any given text whether it is a proof or not algorithmically verifiable mathematics (AV-mathematics for short). We say that a decision problem L ⊆ ∑~* is almost everywhere solvable if for all but finitely many inputs x ∈ ∑~* one can prove either 'x ∈ L' or 'x ∈ L' in AV-mathematics. First, we formalize Rice's theorem on unprovability, claiming that each nontrivial semantic problem about programs is not almost everywhere solvable in AV-mathematics. Using this, we show that there are infinitely many algorithms (programs that are provably algorithms) for which there do not exist proofs that they work in polynomial time or that they do not work in polynomial time. We can prove the same also for linear time or any time-constructible function. Note that, if P ≠ NP is provable in AV-mathematics, then for each algorithm A it is provable that 'A does not solve SATISFIABILITY or A does not work in polynomial time'. Interestingly, there exist algorithms for which it is neither provable that they do not work in polynomial time, nor that they do not solve SATISFIABILITY. Moreover, there is an algorithm solving SATISFIABILITY for which one cannot prove in AV-mathematics that it does not work in polynomial time. Furthermore, we show that P = NP implies the existence of algorithms X for which the true claim 'X solves SATISFIABILITY in polynomial time' is not provable in AV-mathematics. Analogously, if the multiplication of two decimal numbers is solvable in linear time, one cannot decide in AV-mathematics for infinitely many algorithms X whether 'X solves multiplication in linear time'. Finally, we prove that if P vs. NP is not solvable in AV-mathematics, then P is a proper subset of NP in the world of complexity classes based on algorithms whose behavior and complexity can be analyzed in AV-mathematics. On the other hand, if P = NP is provable, we can construct an algorithm that provably solves SATISFIABILITY almost everywhere in polynomial time.