An elementary proof that P ≠ NP

Bhupinder Singh Anand[1]

(A .pdf file of this essay before the current update is available at http://arXiv.org/abs/math.GM/0603605)

We show that first-order Peano Arithmetic has no non-standard models, and that this implies P ≠ NP.

1. Introduction

In a paper presented to ICM 2002, Ran Raz comments [Ra02]:

“A Boolean formula f(x1, ..., xn) is a tautology if f(x1, ..., xn) = 1 for every x1, ..., xn. A Boolean formula f(x1, ..., xn) is unsatisfiable if f(x1, ..., xn) = 0 for every x1, ..., xn. Obviously, f is a tautology if and only if ~f is unsatisfiable.

Given a formula f(x1, ..., xn), one can decide whether or not f is a tautology by checking all the possibilities for assignments to x1, ..., xn. However, the time needed for this procedure is exponential in the number of variables, and hence may be exponential in the length of the formula f. …

P ≠ NP is the central open problem in complexity theory and one of the most important open problems in mathematics today. The problem has thousands of equivalent formulations. One of these formulations is the following:

Is there a polynomial time algorithm A that gets as input a Boolean formula f and outputs 1 if and only if f is a tautology? P ≠ NP states that there is no such algorithm.”

Now, it follows from Gödel’s reasoning [Go31, Theorem VI, p25, eqn.12] that we can define a PA-formula, [R(x)][2],[3], such that:

(i)      [R(x)] is constructible in a standard, first-order, Peano Arithmetic, PA (Appendix A);

(ii)     we can prove, meta-mathematically, that [R(x)] translates as an arithmetical tautology, R(x), under the standard interpretation (Appendix A), M, of the Arithmetic;

(iii)    [R(x)] is not formally provable[4] in the Arithmetic.

Now, it also follows from Gödel’s reasoning [Go31, Theorem VI (1), p25-26], that R(x) is Turing-decidable as always TRUE in M, where:

Definition 1: A total number-theoretical relation, say R'(x1, x2, ..., xn), when treated as a Boolean function, is Turing-decidable in M if, and only if, it is instantiationally equivalent to a number-theoretic relation, S(x1, x2, ..., xn), and there is a Turing-machine T such that, for any given natural number sequence, (a1, a2, ..., an), T will compute S(a1, a2, ..., an) as either TRUE, or as FALSE, in M.

Definition 2: A total number-theoretical relation, R'(x1, x2, ..., xn), when treated as a Boolean function, is Turing-computable in M if, and only if, there is a Turing-machine T such that, for any given natural number sequence, (a1, a2, ..., an), T will compute R'(a1, a2, ..., an) as either TRUE, or as FALSE, in M.

The question arises: Is R(x) also Turing-computable as always TRUE in M?[5]

If we assume, first, that every total arithmetical relation that is Turing-computable as always TRUE in M is PA-provable, then R(x) is Turing-decidable as always TRUE in M, but not Turing-computable as always TRUE[6] in M, and, so, P ≠ NP[7].

If we assume, however, that there is a total arithmetical relation that is Turing-computable as always TRUE in M, but which is not PA-provable, then this implies that there is a non-standard[8] model of PA[9].

We conclude that, if PA has no non-standard model, then, under a strict interpretation of the above expression of the PvNP problem, P ≠ NP.

2. Standard, first-order, PA has no non-standard model

We give an elementary proof that, if PA is a standard, first-order, Peano Arithmetic (Appendix A) then PA has no non-standard model (i.e., a model whose domain contains an element that is not a successor of 0).

We denote by G(x) the PA-formula:

 [x=0 v ¬(∀y)¬(x=y')].

This translates, under every interpretation[10] of PA, as:

Either x is 0, or x is a ‘successor’[11].

Now, in every interpretation of PA, we have that:

(a)  G(0) is true;

(b)  If G(x) is true, then G(x') is true.

It follows, from Gödel's completeness theorem[12], that:

(c)  [G(0)] is provable in PA;

(d)  [G(x) => G(x')] is provable in PA.

We also have, by Generalisation (Appendix A), that:

(e)  [(∀x)(G(x) => G(x'))] is provable in PA;

From the Induction axiom S9 (Appendix A), we thus have that:

(f)  [(∀x)G(x)] is provable in PA.

We conclude that, except 0, every element in the domain of any interpretation of PA is a ‘successor’.

Now, it follows, first, that, since there are no infinitely descending sequences of ordinals[13], every set-theoretical interpretation of PA must be restricted to the domain that consists only of the ordinal 0, and the ordinals that are the ‘successors’ of the ordinal 0.

By definition, this domain corresponds to the natural numbers only.

Second, if we accept that [Se91]:

... ZFC exhausts our intuition except for things like consistency statements, so a proof means a proof in ZFC ... all of us are actually proving theorems in ZFC.

then we must conclude that all non-standard models of PA are isomorphic, and that there are no non-standard models of a standard, first-order, Peano Arithmetic.

3. Conclusions

(i)      A total arithmetical relation is Turing-computable as always TRUE under the standard interpretation of a Peano Arithmetic if, and only if, it is PA-provable.

(ii)     There are no non-standard models of PA.

(iii)    P ≠ NP.

Appendix A

1: Logical Symbols, Axioms, and Rules of Inference of PA

The primitive logical symbols of PA are:

   →             &         v         ~           ∀             x, y, ...           a, b, ...

implies       and       or       not       for all       variables       constant terms

If A, B, C are well-formed formulas of PA, then the logical axioms of PA are:

(1)     A → (B → A);

(2)     (A → (B → C)) → ((A → B) → (A → C));

(3)     (~B → ~A) → ((~B → A) → B);

(4)     (∀x)A(x) → A(t), if A(x) is a well-formed formula of PA, and t is a term of PA free for x in A(x);

(5)     (∀x)(A → B) → (A → (∀x)B), if A is a well-formed formula of PA containing no free occurrences of x.

The rules of inference of PA are:

(i)      Modus Ponens: B follows from A and A → B;

(ii)     Generalisation: (∀x)A follows from A.

By Tarski's definitions of the satisfiability and truth of the formulas of PA under an interpretation, when the rules of inference are applied to true well-formed formulas of PA under a given interpretation, then the results of these applications are also true (i.e., every theorem of PA is true in any model of PA).

2: Primitive Symbols and Proper Axioms of PA

(a)     PA has a single predicate letter, A21 (as usual, we write “ t = s ” for A21(t, s);

(b)     PA has one individual constant a1 (written, as usual, “ 0 “);

(c)     PA has three function letters f11, f21, f22. We shall write “ t' ” instead of f11(t); “ t+s ” instead of f21(t, s); and “ t*s ” instead of f22(t, s).

The proper axioms of PA are:

(S1)  (x1 = x2) → ((x1 = x3) → (x2 = x3));

(S2)  (x1 = x2) → (x1' = x2');

(S3)  0 ≠ (x1)';

(S4) ((x1)' = (x2)') → (x1 = x2);

(S5)  (x1 + 0) = x1;

(S6)  (x1 + x2') = (x1 + x2)';

(S7)  (x1*0) = 0

(S8)  (x1*(x2')) = ((x1* x2) + x1);

(S9)  For any well-formed formula F(x) of PA:

F(0) → ((∀x)(F(x) → F(x')) → (∀x)F(x)).

3: The standard interpretation, M, of PA

The standard interpretation, M, of PA, is taken to be the intuitive arithmetic of the natural numbers, as expressed by Dedekind's semi-axiomatic formulation of the Peano Postulates, where:

(i)      the integer 0 is the interpretation of the PA-symbol “ 0 ”;

(ii)     the successor operation (addition of 1) is the interpretation of the PA-symbol “ ' ”;

(iii)    ordinary addition and multiplication are the interpretations of the PA-symbols “ + ” and “ * ”;

(iv)    the interpretation of the PA-symbol “ = ” is the identity relation.

References

[Ch36]    Church, A. 1936. An unsolvable problem of elementary number theory. Am. J. Math., Vol. 58, pp. 345-363. Also in M. Davis (ed.). 1965. The Undecidable. Raven Press, New York.

[Cook]    Cook, S. The P versus NP Problem. Official description provided for the Clay Mathematical Institute, Cambridge, Massachusetts.

<http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf>

 [Go31]   Gödel, Kurt. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. Translated by Elliott Mendelson. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York.

 [Me64]  Mendelson, Elliott. 1964. Introduction to Mathematical Logic. Van Norstrand, Princeton. 

[Ra02]    Raz, Ran. 2002. P ≠ NP, Propositional Proof Complexity, and Resolution Lower Bounds for the Weak Pigeonhole Principle. ICM 2002, Vol. III, 1–3.

[Se91]     Shelah, Saharon. 1991. The Future of Set Theory. Proceedings, Israel Mathematical Conference, 6.

<http://shelah.logic.at/future.html>

[Tu36]     Turing, Alan. 1936. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, ser. 2. vol. 42 (1936-7), pp.230-265; corrections, Ibid, vol 43 (1937) pp. 544-546.

<http://www.abelard.org/turpap2/tp2-ie.asp - index>


 

[1] The author is an independent scholar. E-mail: re@alixcomsi.com; anandb@vsnl.com. Postal address: 32, Agarwal House, D Road, Churchgate, Mumbai - 400 020, INDIA. Tel: +91 (22) 2281 3353. Fax: +91 (22) 2209 5091.

 

Created: Saturday, 25th March 2006, 8:21:29 AM IST. Updated Wednesday, 27th June 2007, 11:14:41 AM IST by re@alixcomsi.com.

 

[2] In his reasoning ([Go31], Theorem VI, p25, eqn.12), Gödel only refers to the formula [R(x)] indirectly as the “CLASS EXPRESSION r”, where r is the Gödel-number of the PA-formula [R(x)].

 

[3] We use square brackets to indicate when the expression within the brackets is intended to be viewed purely as a syntactical string of mathematical symbols, devoid of any meaning whatsoever. In other words, when it is not to be seen as representing any concept under an intuitive interpretation of the symbols.

 

[4] A formal proof in a system of, say, Peano Arithmetic, is a sequence of well-formed formulas of PA, each of which is either an axiom of PA, or which can be shown to be an immediate consequence - by the mechanical application of the rules of deduction of PA - of any one, or more, of the preceding formulas of the sequence.

 

[5] We note that, although Turing-decidability (which is, essentially, constructive verifiability in the classical sense) of a number-theoretic relation necessarily implies Turing-computability, the converse need not hold unless we assume the standard formulation of the Church-Turing Thesis [Ch36], [Tu36].

 

However, the arguments of this paper suggest that CT may need to be weakened from a strong identity - between intuitively computable functions (and relations) and recursive (Turing-computable) functions (and relations) - to an instantiational equivalence only.

 

[6] The reason, in this case, that R(x) may be Turing-decidable as always TRUE in M, but not Turing-computable as always TRUE in M, lies in the fact that Gödel’s peculiar, but constructive, definition of the arithmetical relation R(x) - more accurately, R(x, p) - is in terms of a primitive recursive relation Q(x) - more accurately, Q(x, p) - and involves a circularity.

 

This follows from Gödel’s definition of Q(x, y), a primitive recursive relation whose domain includes the Gödel-number of the PA-formula [R(x, y)]. Hence, the definition of Q(x, y) implicitly references the range of values of R(x, y).

 

As a consequence, there may be some value of n such that, when computing R(n, p), any Turing-machine that computes R(x, p) does not halt, but goes into a perpetual (machine-generated, but not program-generated) loop, on the input n since, as in the case of Turing's Halting function, an instantaneous tape description repeats itself.

 

[7] This follows only on a strict interpretation of the SAT problem as expressed by Raz’s assertion, since, in this case, R(x) is instantiationally equivalent to a Turing-computable primitive recursive relation. We assume that this interpretation follows from [Cook].

 

[8] We define a non-standard model, say M', of first-order Peano Arithmetic as one in which there is some s in the domain of M' that is not a successor of 0; hence s is not a natural number.

 

[9] This follows since, if [R(x)] is unprovable in PA, but Turing-computable as always TRUE in M, then, by Gödel’s Completeness Theorem ([Me64], p68), there is some M' such that ~R(s) must hold for some s in the domain of M' that is not a natural number.

 

[10] The word “interpretation” may be used both in its familiar, linguistic, sense, and in a mathematically precise sense; the appropriate meaning is usually obvious from the context.

 

Mathematically, following Tarski ([Me64], §2, p49): “An interpretation consists of a non-empty set D, called the domain of the interpretation, and an assignment to each predicate letter Ajn of an n-place relation in D, to each function letter fjn of an n-place operation in D (i.e., a function from Dn into D), and to each individual constant ai of some fixed element of D. Given such an interpretation, variables are thought of as ranging over the set D, and ¬, →, and quantifiers are given their usual meaning. (Remember that an n-place relation in D can be thought of as a subset of Dn, the set of all n-tuples of elements of D.)”

 

Loosely speaking, the interpreted relation R'(x) is obtained from the formula [R(x)] of a formal system P by replacing every primitive, undefined, non-logical, symbol of P in the formula [R(x)] by an interpreted mathematical symbol. So the P-formula [(∀x)R(x)] interprets as the sentence (∀x)R'(x), and the P-formula [¬(∀x)R(x)] as the sentence ¬(∀x)R'(x).

 

[11] Note that, by virtue of axiom S4, x can only be a ‘successor’ of a unique element in the interpretation. It follows that an ordinal such as the first infinite ordinal, ω, is not the ‘successor’ of any ordinal in the sense required by the PA axioms.

 

[12] “In any first-order predicate calculus, the theorems are precisely the logically valid wfs.” ([Me64], p68).

 

[13] As would be required if there were a non-standard model of PA in, say, ZF, in which all the elements in the domain of the interpretation, except the ordinal 0, are ‘successors’, but not necessarily the ‘successors’ of the ordinal 0.