Seja um programa P que pede ao usuário que entre com o tamanho

P ≠ NP Proof

André Luiz Barbosa

http://www.andrebarbosa.eti.br

Non-commercial projects: SimuPLC – PLC Simulator & LCE – Electric Commands Language

Abstract. This paper demonstrates that P ≠ NP. The way was to construct an artificial problem (a generalization to SAT: The XG-SAT, much more difficult than the former) and then to demonstrate that it is in NP but not in P. The demonstration consists of:

1. Definition of Restricted Type X Program

2. Definition of the General Extended Problem of Satisfiability of a Boolean Formula – XG-SAT

3. Demonstration that the XG-SAT is in NP

4. Demonstration that the XG-SAT is not in P

5. Demonstration that the Baker-Gill-Solovay Theorem does not refute the proof

6. Demonstration that the Razborov-Rudich Theorem does not refute the proof

The paper demonstrates three new revolutionary ideas in the foundations of Computational Complexity Theory, against the established theory in the area:

1. Language Incompleteness: There are computational decision problems that are not languages (cannot be modeled as string acceptance testing to languages);

2. NP-Completeness Incompleteness: The Cook-Levin Theorem cannot in general be applied on an instance of the XG-SAT to reduce it to an instance of the SAT, since a restricted type X program does not necessarily halt for all inputs; and

3. SAT's weakness: The complexity class of the SAT maybe does not decide P versus NP question (if SAT is not in P then NP ≠ P; on the other hand, SAT in P doesn’t imply NP = P).

The objective of the paper is just help the complexity theorists about their main question: If I am right, then the P versus NP Clay Mathematics Institute Prize must be canceled and replaced by the correct problem intended by them: "Is SAT in P?"

Mathematics Subject Classification (2009). Primary 68Q15; Secondary 68Q17.

Keywords. P, NP, Computational Complexity, Formal Languages, Automata Theory.

1 Introduction 02

2 Definition of Restricted Type X Program 03

3 Definition of the Extended General Problem of Satisfiability – XG-SAT 04

3.1 Definition of well-formed string 04

3.2 Definition of the XG-SAT as well-formed string acceptance testing to a language L 04

3.3 Class of the language L and class of the L_z-language L 05

3.3.1 More general definitions for NP and P and definition for L_z-language 05

3.3.2 L_z-languages and Promise Problems 09

3.4 More general definition for Computational Decision Problem 09

3.4.1 The falseness of Cook-Levin Theorem upon L_z-languages 09

3.4.1.1 How can a Theorem be false? 10

4 Old demonstration that the XG-SAT is in NP 11

4.1 The SAT as particular case of the XG-SAT 11

5 Demonstration that the XG-SAT is not in P 12

5.1 Running time of the functions into programs 19

5.2 Example of construction of an instance of the XG-SAT 20

6 Baker-Gill-Solovay Theorem and the Proof 20

7 Razborov-Rudich Theorem and the Proof 21

8 Related Work 21

9 References 21

1. Introduction

I am a very ambitious person: I have restated the P versus NP question on my own terms, and this fact is confused with a supposed lack of rigor in the paper. But this restating is not arbitrary or nonsense thing. I have not invented a new one or distorted the problem: I have just generalized it in order to hold all computational decision problems that can be constructed in the real world – the set of the L_z-languages –, not only the set of the languages, a small proper subset of the former, as stated in Section 3.3.1.

I have succeeded where better Math warriors in the area failed before me because I have seen that the Complexity Theory was incomplete, treating languages as if they would represent all the computational decision problems. Then, to solve the problem, I simply have generalized the theory in order to really include into it all the possible decision problems that can be decided by computers, not only the languages.

Hence, as Mathematics loves generalizations (since the concepts, notation, generality, power and applicability of the more general mathematical constructs are clearer and stronger than of the less general ones), I think I should not be considered so crank or crackpot by this “heresy”. Here, in its generalized form, the profoundest question in Complexity Theory is settled – and, in addition, new and marvelous paths for original and relevant researches are glanced; like the generalization in these terms of all Computation Theory (we can call it The Barbosa’s Program). This Program, in fact, was already started in [13], with a P ≠ RP proof (leading to P ≠ BPP, P ≠ ZPP, and others great related results), in [19], with an NP Ë P/poly proof (leading to NEXP Ë P/poly, NEXP ≠ MA, NEXP ≠ BPP, and others great related results), and in [15], with the wonder and astoundingly (wrong, unfortunately) conclusion that this Proof on my own terms leads to P ≠ NP on traditional ones (where the uniformity polynomial time bounds blindness in the technical report in [15] makes the errors in all its main conclusions, obliterating the fact that the XG-SAT is a single problem, even though its polynomial time bound is not uniform – see Def. 3.7, where this wide misconception is fixed). So, I so hope that the Computer Science community is ready to this stunning inflection point, originating deeper understanding on machine-based computation.

(Note: This paper of mine has a little non-technical comments, and its writing style is manifestly unusual, written in first person singular number at some places, which is not expected at all in technical works. But it is needed that I just do it in this way. I claim huge breakthroughs: If I am right, enormous stones will roll deeply into Science of Computation, whence this little paper can either be my eternal humiliation, or the glory of independent and fearless thinking, inspiring everlastingly the new generations of the Science thinkers. Thus, appreciating your precious time, I beg for your mercy and for your [unconventional] reading.)

Accordingly, in Sections 2 and 3 the restricted type X programs and the XG-SAT problem are formally defined, and some notes are included to avoid the traps in these definitions. In order to define the XG-SAT, computational decision problem and poly-time DTM are redefined on more general form, where then the Cook-Levin Theorem is disproved. So, it is proved that the XG-SAT is in NP, with concepts of poly-time verifier and certificate of membership. In Section 4, this demonstration is repeated with the old kind, using decider poly-time NTM. Then, in Section 5 it is proved that this problem is not in P (therefore, P ≠ NP, naturally), by demonstrating that it is impossible that any poly-time deterministic computation solves the XG-SAT. In this proof, is no assumed anything about type, structure, form, code, nature, shape or kind of computation, neither structure (or lack thereof) of data, eventually used into any DTM that tries to decide the problem in polynomial time. Otherwise, my proof exploits properties of computation that are specific to the real world computers (without oracles, infinite TMs and other supernatural devices). In Sections 6, 7 and 8, it is demonstrated that the theoretical barriers against possible attempts to solve the P vs. NP question are not applicable to refute my proof. Finally, in Sections 8 and 9 there are some comments about related work (or lack thereof) to really solve this question, and references, respectively.

Shortly, in order to this P ≠ NP proof of mine be accepted, it is sufficient that the fact if there is an L_z-language (promise problem) separating complexity classes, then they are truly distinct, and the Def. 3.7 are both accepted. On scientific revolution/paradigm shifts, see [17].

Please: If possible, read the paper without preconceptions. Remember that, compared to proper Mathematics, immortality, fame, money and so on are vain things, silly concepts and bullshits that blow in the wind. The true happiness to an actual mathematician is to find the light into the darkest night.

2. Definition of Restricted Type X Program

Definition 2.1. Let S be a deterministic computer program, let n be a finite positive integer and let time P(n) be a poly(n) upper bounded number of deterministic computational steps (where time P(n) is not previously fixed for all possible programs S, but it is fixed for every one). Sis a restricted type X program if and only if the following three conditions are satisfied:

1. S allows as input any n-bit word (member of arbitrary length n from {0, 1}⁺).

2. The S behavior must be for each input one of the following:

i. S returns 0;

ii. S returns 1; or

iii. S does not halt (never returns any value).

3. The total S behavior must be for each n one of the following:

i. S returns in time P(n) 0 for all the 2ⁿ possible inputs of length n; or

ii. S returns in time P(n) 1 for at least one possible input of length n.

Note 1: The presence of S is not to be decided – see Section 3.3.1. Testing whether a computer program is a restricted type X program will not be necessary to the proof. S will be given as an absolute assumption: It IS a restricted type X program, and this fact will NOT be under consideration: This is not a contradiction, definitely, since we can easily create innumerous programs of this type and – without deciding them at all – produce a myriad of instances of the XG-SAT problem with them – see Sections 5.1 and 5.2, for details.

Note 2: There is no need that the polynomial running times involved in a proof must be previously fixed in order to be defined: For example, what is the fixed polynomial that upper bounds the running time of the reducer concerned in the Cook-Levin Theorem? There is no such a fixed polynomial, since this running time depends on the NP problem whose instance is to be reduced to a Boolean formula, but the running time of this reducer is (and must be) polynomial, it is not undefined, of course, otherwise there would be no NP-Completeness. (This insight is formalized in the Def. 3.7.) Notice that does not matter at all that we have a different time bound for each NP problem, but the same time bound for each instance of a fixed one, since for this reducer any instance from every NP problem is like just a mere input to a deterministic computer program: which is important here, in fact, is that that polynomial time bound is NOT uniform, whereas it is – without any contestation – considered very well defined. (Anyway, see Section 3.4.1 for a surprisingly claim about this issue.)

3. Definition of the Extended General Problem of Satisfiability of a Boolean Formula – XG-SAT

Definition 3.1. Let S be a restricted type X program and let n be a finite positive integer. The Extended General Problem of Satisfiability of a Boolean Formula (XG-SAT) is the question “Does S return a value 1 for at least one input of length n?”. Thus, in the XG-SAT question, the input is the pair áS,1ⁿñ, clearly, where 1ⁿ is just n in unary form. Note that the specific and fixed time P(n) related to S is NOT given.

Be careful with a possible confusion made about the XG-SAT and the Bounded Halting problem (BH), defined over triples w = áM,x,1^kñ, where M is a nondeterministic machine, x is a binary string, k is an integer, and w Î BH if and only if there exists a computation of M on input x that halts within k steps ^[12]: The XG-SAT is a very different problem, since the time P(n) is not given, and the program S into the pair áS,1ⁿñ always halts for at least one input of length n, but maybe S does not halt for all the other ones. Furthermore, the XG-SAT cannot be reduced in polynomial time to BH (– See Section 4.1).

3.1 Definition of well-formed string

Definition 3.2. Let w be a string from {0, 1}⁺. w is a well-formed string if and only if w has the form 1⁺0s – where 1⁺ is a finite positive integer n encoded in unary form and s is the binary representation of the DTM (deterministic Turing Machine) that simulates a restricted type X program S. For n = 13, a well-formed string w would be, for instance, 111111111111101001000101001110010010101100100101011001001011110010010110...1.

3.2 Definition of the XG-SAT as well-formed string acceptance testing to a language L

Definition 3.3. Let L be a formal language over the alphabet S = {0, 1}. A well-formed string w Î L if and only if the DTM encoded into w returns 1 for at least one input of length n. The XG-SAT is the well-formed string acceptance testing to L.

Note that as the size of a restricted type X program S is constant on n (|S|(n) = c), the length of the DTM that simulates S is constant too on n (|s|(n) = k), and then |w| = n + 1 + k. Thus, time P(n) is the same as time P(|w|) and time exp(n) is the same as time exp(|w|).

3.3 Class of the language L and Class of the L_z-language L

L is a nonrecursively enumerable (non-RE or non-Turing-recognizable) language ^[1], since it is undecidable whether or not an eventual result 1 from a computer program occurs in polynomial time ^[18], besides the undecidability even whether just it halts for some input ^[4].

(Note: The undecidability of the language L does NOT contradict the proof. The XG-SAT is not the undecidable decision problem w Î? L, but just the decidable one well-formed string w Î? L, as explained in Section 3.3.1, since a well-formed string w is given as an absolute assumption: w IS well-formed string, and this fact is NOT under consideration. See that exactly the same kind of statement holds to traditional formal languages, where the absolute assumption is that the strings to be tested are members from $Σ*$ ^[1] $.$ )

Language Incompleteness – The computer theorists generally make a mistake on definition of computational decision problem: They think that ones is the same thing that languages, as if all decision problems could be modeled as string acceptance testing to formal languages, like in [1, 5, 6]; however, there exist computational decision problems that can only be modeled as string acceptance testing to L_z-languages (as defined in Section 3.3.1), not to languages, like the XG-SAT. (See Def. 3.8.)

Thus, all computer theorists generally say 'problem' to mean 'language' and vice versa. See below an excerpt of text of a preeminent Professor in the area, in [10]:

"By Savage's theorem, any PROBLEM in P has a polynomial size family of circuits. Thus, to show that a PROBLEM is outside of P it would suffice to show that its circuit complexity is superpolynomial." [The words PROBLEM are lowercased in the original]

However, the set of all languages is a mere proper subset of the stronger and more powerful set of all L_z-languages (all the computational decision problems), as established below.

3.3.1 More general definitions for NP and P and definition for L_z-language

Definition 3.4. Let L_z be a language over a finite alphabet, $Σ$ $, and let$ $L$ Í L_z. We will call L an L_z-language. If L_z = $Σ*$ , then L is a $Σ*$ -language, a trivial L_z-language, which is the same as language ( $Σ*$ -language = language). The complement of an L_z-language A is another L_z-language Ā = L_z – A. Thus, L_z-language is simply a generalization to language and a string acceptance testing to L is a computational decision problem where the string to be tested is necessarily member from L_z. If language is a set, L_z-language is a set into another.

Observe that a string acceptance testing to L is a computational decision problem, but L, rigorously, is not only a language, because L Í L_z, which is more restrict than simply L Í Σ*, which should hold if L was only a language ^[6]. Thus, all the computational decision problems can be modeled as string acceptance testing to L_z-languages, for to accept a string from any determined subset of $Σ$ * is much more general than do it just from $Σ$ *, of course.

The point here is that the central relevance of the languages is originated in the fact that they model problems, not the inverse. Hence, great part of the Theory of Computation is about languages because of the mistake referred in Section 3.3. When this error – that it is said as error because it leaves legitimate problems out of the definition – is fixed, the Theory of Computation will certainly study the generalization to language: The richer and stronger concept of L_z-language.

A language over $Σ$ is a subset of $Σ*$ , and an L_z-language is a subset of the language L_z over $Σ$ $.$ However, as L Í L_z and L_z Í $Σ*$ , then L Í $Σ*,$ which implies that all L_z-languages are $Σ*-$ languages, or simply languages, too, naturally. Any language L is also an L-language, and any L_z-language L is also a language L. In fact, if L_y Ê L_z then any L_z-language L is an L_y-language L, too. But $the great advantage of the$ L_z-languages is that string acceptance testing to ones can be much easier than to languages, because the strings x to be tested are in special form: x Î L_z (this is an absolute assumption). Hence, if we know that all the strings to be tested are from a fixed language L_z, then it is worth to model this problem as an L_z-language; but if we do not know it, we must model it as a simple language, of course.

Consequently, the concept of L_z-language allows the insertion of previous knowledge about the form of the strings to be tested – when they were already constructed in special form or previously accepted by another machine – into traditional concept of language.

(Note: If the machine M that decides an L_z-language L is fed a string x that is in L_z, then M must decide whether or not x is in L, anyway returning correct answer to x Î? L; on the other hand, if M is fed any string that is not in L_z, it may do whatever, returning anything, even incorrect answer to x Î? L [ $Σ*$ -language L, in this case], or even not halting at all.)

For instance, the language {0ⁿ1ⁿ | n > 0} over {0, 1} is not regular, but verify that if L_z = {0ⁿ1ⁿ | n > 0} U {1ⁿ0ⁿ | n > 0}, for example, then the L_z-language L₁ = {0ⁿ1ⁿ | n > 0} is regular and can be decided by the NFA M = ({q₀, q₁, q₂}, {0, 1}, δ, q₀, {q₂}), where δ(q₀, 0) = {q₂}, δ(q₀, 1) = {q₁}, δ(q₁, 0) = Ø, δ(q₁, 1) = Ø, δ(q₂, 0) = {q₂}, δ(q₂, 1) = {q₂}, and there are not ε-moves.

Verify that this NFA M recognizes the language L = 0{0, 1}* and {0ⁿ1ⁿ | n > 0} = 0{0, 1}* ∩ ({0ⁿ1ⁿ | n > 0} U {1ⁿ0ⁿ | n > 0}). In fact, this is not coincidence:

Theorem 3.1. If a machine M (DFA, NFA, PDA, DTM, NTM, etc.) recognizes a language L, then M recognizes any L_z-language L₁ = L ∩ L_z.

Proof. Suppose that a string x Î L_z-language L₁ was accepted by a machine M: Then, x Î L_z (this is an absolute assumption: All the strings to be tested must be member from L_z) and x Î L (the language that M recognizes, regardless of the special form of x), which implies that x Î L ∩ L_z; on the other hand, if x Î L ∩ L_z, then x will be accepted by M, because x Î L_z (x can be tested) and x Î L (x will be accepted by definition of string acceptance testing to languages), which implies that the L_z-language recognized by M L₁ = L ∩ L_z. ¾

See, thus, the proposed fix and generalization to the traditional formal definition for the class NP (Nondeterministic Polynomial Time) ^[14]:

Definition 3.5. Let L be an L_z-language. $L$ Î NP if and only if there is a binary relation R Í L_z × $Σ*$ and a finite positive integer $p$ such that the following two conditions are satisfied:

1. For all x Î L_z, x Î L Û $y Î $Σ*$ $such that$ $(x, y)$ Î R and |y| Î O(|x|^p); and

2. The language L_r = {x#y : $(x, y)$ Î R} over $Σ$ U {#} is decidable by a poly-time DTM.

A DTM that decides L_r is called a verifier for $L$ and a $y$ such that $(x, y)$ Î R is called a certificate of membership or witness of $x$ in $L$ . Note that – as x Î L_z (this is an absolute assumption, by Def. 3.4) – we do not need to describe what language L_z is allowed here. Hence, condition 2 does NOT require any knowledge about how to decide L_z in order to decide whether x#y is in L_r, plainly.

Verify that when L_z = $Σ*$ and the traditional definition for poly-time DTM there is utilized, the formal definition above is equivalent to the traditional one for the class NP – a set of mere languages –, which implies that this one is just a particular case of the proposed fixed definition. Consequently, we can name the traditional class NP as class NP-SAT (or, shortly, SNP), where the Cook-Levin Theorem (with the hidden assumption refered in Section 3.4.1) and all the other mathematical truths on the traditional class NP continue holding in (replacing “P ≠ NP” and “P = NP” by “SAT is not in P” and “SAT is in P”, respectively, etc.).

Alternatively, we could call the true class NP defined above – an actual set of computational decision problems, or L_z-languages – as class NP-XG-SAT (or, shortly, XNP), for example, but this naming method would be a mistake: A subset would have the name of the set and the set would have a derived name of the subset, which is hard to explain, confuse and damages the clearness of the notation.

Proposition 3.1. XG-SAT is in class NP.

Proof. Into the Def. 3.5, for L modeling the XG-SAT, S = {0, 1}, L_z is the set of all well-formed strings (as defined in Section 3.1), $p$ = 1, y is an n-bit word and $(x, y)$ Î R if and only if the program S encoded into the well-formed string x returns in polynomial time (poly(n), hence poly(|x#y|)) 1 for y as its input (a DTM that on áx#yñ decodes and simulates S running having y as input is, in fact, the apt verifier for L). Hence, L (XG-SAT) is in NP. ¾

Note that although the deterministic polynomial time T(n) = O(nⁱ) that the witness predicate is decided is a different polynomial for each input x, XG-SAT is a single problem (it is false that any recursive decision problem is poly-time reducible to it, since T(n) is not previously fixed for all S, but it is fixed for every one, by Def. 2.1 – See the note below, for details), where i does not depend on n, even though it does on x. Consequently, $(x, y)$ Î? R is really decidable in deterministic polynomial time, by Def. 3.7, and the proof above is wholly correct: the XG-SAT is in NP, undoubtedly.

See that XG-SAT has strings of the form 1ⁿ0s, where s is a DTM simulating a restricted X program S that accepts in polynomial time some string of length n (returning 1 for some n-bit input). Notice that we do NOT need to check whether S is a restricted X program, by Def. 3.4.

(Note: Suppose that someone says that the XG-SAT is not in NP, since its complexity class is really undefined, and it can be, for example, EEXP-Hard (for double exponential time), reasoning as below:

“Let L be an EEXP problem, M be the deterministic Turing Machine that solves L in time t(n) = 2^{2^{poly(n)}}. Then we can reduce L to XG-SAT as follows: Given an input x for the problem L, we construct a program S that ignores its input and simulates M on input x. The promise is satisfied by the constant polynomial p(n') = t(|x|), and clearly (S,1) is an instance of XG-SAT if and only if M accepts x.”

Fortunately, constructions like above cannot disprove that XG-SAT is in NP, since they do not take into account that time P(n) is not previously fixed for all possible programs S, but it is fixed for every one, as stated in Def. 2.1 – hence, as 2^{2^{poly(|x|)}} is not upper bounded by any fixed poly(n), that program S is not a restricted type X program, and clearly (S,1) is NOT an instance of the XG-SAT.

Finally, see also that the function 2^{2^{poly(|x|)}} = t(|x|) is not constant, but depends on |x|. However, if x is fixed into that TM M simulated by S, then this function is a constant (and then M halts on x within only O(1) steps, since M and x are fixed independent of n); nonetheless, in this case, M does not solve L, of course, and then the disproof above fails.)

Note that even the language L_r in item 2 above is, in fact, an L_z-language, where L_z is the set of all strings of the form x#y.

In fact, all complexity classes can be generalized with the concept of L_z-language, like this new definition proposed for the class P:

Definition 3.6. Let L be an L_z-language $. L$ Î P if and only if for all x Î L_z, x Î? L is decidable by a poly-time DTM. Be careful with the traps: For example, all L_z-languages L_z are trivially in P (where L_z can be any language, even non-Turing-recognizable ones), which does NOT mean that all languages L_z ( $Σ*$ -languages) are in P, noticeably.

Notice that the proper definition of deterministic polynomial-time computation is more general here, without losing its more important characteristic: To be understood loosely as “feasible in practice”:

Definition 3.7: Poly-time DTM. A DTM is said to be polynomial time if its running time T(n) = O(n^k), for some finite nonnegative k either that does not depend on n or that it is upper bounded by a positive constant (where n = |input|).

Into the traditional definition, k must be a fixed constant (that does not depend on n, obviously), but this stronger restriction is not essential to the vital matter: To maintain the character of vaguely practicable for deterministic poly-time computations. In XG-SAT, the T(n) of its verifier Î O(n^k), where k depends on the S encoded into w, but not on |w| – and k cannot be computed ^[1] neither is given, but it is a fixed constant for each fixed S, by Def. 2.1.

See that if T(n) = O(2^poly(n)), for example, then T(n) = O(n^k), where k (poly(n) log_n 2) depends on n, evidently (for non-constant poly(n), of course), and is upper unbounded: hence, in this case T(n) is not polynomial at all. The same happens with T(n) = O(n^{log n}). On the other hand, if T(n) = O(2^c), where c is a positive constant, then k (c log_n 2) depends on n yet, but now it is upper bounded by c: hence, in this latter case T(n) is polynomial (constant, really).

3.3.2 L_z-languages and Promise Problems

An L_z-language L can be considered as a promise problem ∏, as introduced by Alan L. Selman [Information and Computation, Vol. 78, Issue 2, (1988), pp. 87-98] and defined in [9], where the promise (∏_YES U ∏_NO) = L_z, ∏_YES = L, ∏_NO = L_z – L, and its restricted alphabet {0, 1} is generalized to any finite alphabet $Σ$ . Nonetheless, notice that the concepts, notation, generality, power and applicability of the L_z-languages are clearer, richer, simpler, conciser, more elegant, aesthetic and stronger than ones of the promise problems.

3.4 More general definition for Computational Decision Problem

Note yet that the definition of computational decision problem used here is also more general, without losing its more essential attribute: To model all real computer-based questions – not only a small part of them – having one and only one answer from two alternatives ^[16]:

Definition 3.8: A computational decision problem is any arbitrary Yes-or-No (True-or-False) question on a finite or infinite set of inputs (strings of any finite length over a finite alphabet $Σ$ ), where these ones are necessarily member from another determined set (or consistently the set of inputs of obligatory specified form for which the problem returns Yes (True)). Equivalently, decision problems are completely isomorphic to L_z-languages of strings, and can always be modeled as string acceptance testing to L_z-languages.

Into the traditional definition for computational decision problem ^{[1, 16]}, using plain languages, the inputs for a problem are simply from $Σ*$ , whereas for this more general definition they are from any arbitrary subset of $Σ*$ . So, we can consider a traditional problem (language) as a set, and a more general one (L_z-language) as a subset of a set. Hence, the set of all languages (L_z = $Σ*$ ) is just a little proper subset of the set of all L_z-languages (L_z = any subset of $Σ*$ ). So, only one set characterizes language, but we need two sets for L_z-language.

See yet that, for this generalization, the strings to be tested (into a string acceptance testing to an L_z-language) are necessarily (must be) member from L_z (whatever L_z is), where this fact IS an absolute assumption and IS NOT under consideration. Verify that exactly the same kind of statement holds to traditional formal languages, where the absolute assumption is that the strings to be tested (into a string acceptance testing to a language) are necessarily (must be) members from $Σ*.$

3.4.1 The falseness of Cook-Levin Theorem upon L_z-languages

Thus, with the more general definitions for decision problems and poly-time DTM, the central theorem from traditional Computational Complexity Theory crumbles to the ground (even though we refuse to see…):

Theorem 3.2. The Cook-Levin Theorem (CLT) is false upon L_z-languages (on more general computational decision problems and poly-time DTM).

Proof. The CLT is valid only into the traditional definition for computational decision problem and poly-time DTM, since in order to all its proofs work a fundamental – but in general neglected – input (information) is absolutely essential and supposed to be known (or can be computed in deterministic poly-time) in their scope ^[1]: a fixed polynomial p(n) that upper bounds the running time of some NTM that decides in nondeterministic poly-time the problem to be reduced into the reduction to the SAT that it is the heart of all these proofs. With such a p(n) anyway provided (which can be considered a hidden assumption or axiom), a poly-time DTM that reduces any instance of the original problem to an instance of Boolean formula (or of poly-size Boolean circuit that simulates the problem) can always be constructed within deterministic poly-time (where the size of this generated Boolean formula (or circuit) is in O(log(n) p(n)²)).

However, if such a p(n) is not known (or is not even fixed at all) neither can be computed in deterministic poly-time, then all these proofs shall fail. They stop working, consequently, upon more general decision problems (Def. 3.8) and poly-time DTM (Def. 3.7), since for L_z-languages, contrarily to languages, in general there is not such a fixed poly-time for all their instances, neither it can be computed in deterministic poly-time on a specific one, as proved in the Proposition below:

Proposition 3.2. Computing in deterministic polynomial time a polynomial n^k that upper bounds the running time of an arbitrary poly-time DTM M is impossible. (Hence, computing in deterministic polynomial time a polynomial that upper bounds the running time of a poly-time NTM – information that it is essential in order to Cook-Levin Theorem works upon more general problems (L_z-languages) – is impossible too).

Proof. Assume that there is a poly-time DTM B that returns k on the description of any arbitrary DTM A promised to be poly-time, where the polynomial n^k must upper bound the running time of A. Then, let A be the poly-time DTM (computer program) below – note that, as the DTM B is supposed to be poly-time, the DTM A is a restricted type X program:

01. A(input) {

02. n := length(input);

03. k := B(áAñ); // the DTM B runs on the proper description (or code) of A and returns k

04. execute n^(k+1) arbitrary steps; // this diagonalization makes the DTM B always wrong

05. if (k < 8) return(0); else return(1);

06. }

Thus, as it is easily seen above, the diagonalization makes that the running time of the DTM A is at least Θ(n^k+1), whereas the DTM B answers that this running time is only O(n^k). Hence, cannot exist a poly-time DTM that on the description of an arbitrary poly-time DTM computes a finite k where n^k upper bounds its polynomial running time: The CLT is false. ¾

3.4.1.1 How can a Theorem be false?

Since a theorem is an absolute mathematical truth, how can the Cook-Levin Theorem be false? I am so sorry, but the answer is unavoidable: this “theorem”, in fact, is not a genuine theorem, for its proofs are incorrect, since into them is used the hidden non-proved (faulty, really) assumption (or hidden axiom, contradictory with ZFC ^[20]) – by Proposition 3.2 –, that states that a polynomial p(n) that upper bounds the running time of some NTM that decides in nondeterministic polynomial time the problem to be reduced into that reduction to the SAT can be always anyway provided (either that p(n) is known a priori or can be computed by a poly-time DTM). We have seen above (Proposition 3.2) that this is not always accurate.

This hidden assumption was a big flaw into all the known “proofs” of the CLT, unknown for almost four decades, which demonstrates how much the Computer Theory is an extraordinary marvelous land, and, at same time, a very dangerous mathematical territory.

To illustrate the danger, suppose that A has written a poly-time computer program (DTM) that correctly decides the SAT. Then, B gives to A a problem Y that is proven to be decidable within n^k nondeterministic steps (hence, Y is an NP problem), and then solicits to A another poly-time computer program that correctly decides the problem Y (the CLT assures absolutely that, given a poly-time DTM that decides the SAT, this required program can be written). A, on the other hand, asks to B what is the value of k. B answers to A that it is unknown: the proof that Y is in NP does not determine k at all, even though it states that k is some fixed finite constant. Thus, A responds to B that the demanded task is impossible without knowing k. Whence, as to know a priori or compute k in deterministic polynomial time is in general unfeasible (by Proposition 3.2, for instance), B (the entire World, actually) concludes that the CLT is false, lamentably.

Why did the proofs of the CLT be considered true? Because that polynomial p(n) was supposed to be a fully-known part of all NP problems, which this paper has proved to be in general a false statement.

4. Old demonstration that the XG-SAT is in NP

Given n and a restricted type X program S, the question “Does S return a value 1 for at least one input of length n?” can be decided in nondeterministic poly-time (time NP(n): as time P(n), using nondeterminism), since can be constructed a universal NTM (nondeterministic TM) that simply simulates the running of S and tests it for all 2ⁿ possible inputs of length n at the same time (“on parallel”) and verifies in time NP(n) the returns: If they are 0 for all the inputs, then the NTM will answer “No” after the conclusion of the last computation path (branch); on the other hand, if at least one return is 1, then the NTM will answer “Yes” at the end of the first path that returns 1, regardless of whether the others are yet running. One and only one of these two events must happen in time NP(n), by Def. 2.1.

4.1 The SAT as particular case of the XG-SAT

Any Boolean formula E with n variables can be simulated in polynomial time by a simple restricted type X program S (where each bit from input represents one variable) where the returns from S for all 2ⁿ possible inputs of length n represent the results from E for all assignment of truth values to the variables (0 represents False and 1 represents True). For instance, if E has two variables and E(F,F) = F, E(F,T) = F, E(T,F) = T, E(T,T) = F then S(00) returns 0, S(01) returns 0, S(10) returns 1, S(11) returns 0; finally, S returns 0 for all inputs of length different from n.

Let S be the restricted type X program below, an example of such a simulator:

01. S(string input) // input is an n-bit word where each bit from it represents one variable from // a Boolean formula E with n variables.

02. {

03. string E := “x1 Ù ((Øx1 Ù x10) Ú Ø(x1 Ù Ø(x10 Ú x11) Ù Øx1))”; // any Boolean formula of length m can be placed here and the number of variables in it can be determined in time P(m), naturally, where m = O(n log n) – which implies that time P(n) is the same as time P(m).

04. return(Satisfier(E, input)); // Satisfier is a simple function that returns 1 if the assignment of the input’s truth values to the variables of E, as above, satisfies it; otherwise it returns 0. If the length of input is different from the number of variables in the E, then it returns 0, too. Satisfier can (and must) run in time P(n), of course, and must not use short circuit logic in order to its running time be the same for any input of length n.

05. }

Thus, if there exists a P(n)-time decider for XG-SAT, then it can decide the SAT in polynomial time (time P(n)) too: It’s enough to place the Boolean formula E to be tested into the code S above, to construct, setting n as the number of variables in E, an instance w of the XG-SAT with S, and to decide in time P(n) whether w is in the language L defined in Section 3.2, which is the same as E to be satisfiable, naturally. See that, in fact, this process constructs a different restricted type X program for each different E to be tested.

On the other hand, if a restricted type X program S returns in time P(n) 0 or 1 for all 2ⁿ possible inputs of length n (where its running time is the same for any one), and 0 for all inputs of length different from n, then S can be considered a simple simulation of a Boolean formula with n variables, as above, which implies that the SAT is just a particular case of the XG-SAT.

Moreover, given an instance of the XG-SAT constructed with a program S that returns in time P(n) 0 or 1 for all 2ⁿ possible inputs of length n and a running time (upper bounded by a poly(n), naturally) that bounds the entire running time of the NTM that decides in time NP(n) this instance, this NTM can be reduced to a Boolean formula that represents its entire processing, by means of the Cook-Levin Theorem (Cook’s Theorem) ^[1].

Verify that the running time of this NTM is equal to a fixed value more the running time of running the simulation of S, that can be determined by way of running the simulation of S for some input of length n and counting the running time in order to it returns the result 0 or 1, because if it is simulating a Boolean formula with n variables, then its running time is the same for any input of length n. Notice that if S is not simulating a Boolean formula, then this way of determining its running time for some input – and then the running time of the NTM that solves the instance of the XG-SAT constructed with this S – does not work in general, for S, in this case, can never halt for some inputs, or its running time can be different for different inputs, even though ones of same length.

NP-Completeness Incompleteness – Thus, as a restricted type X program does not necessarily halt for all the 2ⁿ possible inputs of length n and the running time of the universal NTM that decides in time NP(n) any instance of the XG-SAT cannot be upper bounded by any fixed poly(n) – by Def. 2.1 –, the Cook-Levin Theorem cannot in general be used on an instance of the XG-SAT to reduce it in polynomial time to an instance of the SAT. In fact, the SAT is very easy compared to the XG-SAT, and the speed of the nondeterministic computation is much greater than we have believed it. (See Sections 3.4, 3.4.1 and 3.4.1.1.)

Notice that, despite the time P(n) cannot be upper bounded by any fixed poly(n), it is neither vague, undefined, nor undetermined: For each restricted type X program S, there is exactly one specific and fixed polynomial on n that bounds the necessary number of deterministic computational steps in order to S returns 0 for all inputs of length n, or 1 for at least one, where n is an arbitrary positive integer, but this polynomial on n is fixed.

5. Demonstration that the XG-SAT is not in P

Theorem 5.1. P ≠ NP.

Proof. As demonstrated in Sections 3.3.1 and 4, any instance of the XG-SAT can be recognized in nondeterministic polynomial time. However, can it be recognized in deterministic polynomial time?

By hypothesis, consider that it can: In this case, must exist a DTM Q that – given a positive integer n and a restricted type X program S into w – answers correctly in polynomial time the question “Does S return a value 1 for at least one input of length n?”. (If w is in XG-SAT, then Q(w) = “Yes”, else Q(w) = “No”). Note: all the inputs for the program S in this Section are of length n.

Proposition 5.1. The DTM Q is, in fact, a real computer program. Although it may work entirely in a different way from someone would expect from the method that the XG-SAT was defined, Q cannot be a magical or dream machine, since it must be an actual machine. Thus, in order to answer the question, there are no miracles: Q can act into only four possible ways (where simulation is considered here a step-by-step process running S into Q):

1. Q simulates the running of S for:

i. All the possible inputs;

ii. All the inputs from an arbitrary nonempty proper subset of all them; or

iii. Only one input (or all from a nonempty proper subset of all them) previously computed whose return decides the question.

2. Q does not simulate the running of S at all.

Proof. These ways are exhaustive: Either Q simulates the running of S or not; and, if Q simulates the running of S, then it can test on it all the possible inputs (1.i); arbitrarily less than all ones (1.ii); or just one (or all from a nonempty proper subset of all them) that was anyway previously computed whose return decides the question (1.iii). Unfortunately, there are no more alternatives besides that ones. (Note: Into ways (1.ii) and (1.iii), the number of inputs to be tested must be polynomial in n in order to Q can decide the XG-SAT in deterministic polynomial time.)

As well, the running time of a universal NTM that decides in time NP(n) the XG-SAT – as in Section 4 – cannot be upper bounded by any fixed poly(n). Moreover, a program S does not necessarily halt for all its possible inputs. Furthermore, the time P(n) in Def. 2.1 cannot be upper bounded by any fixed poly(n), too. Thus, in general, cannot exist any fixed poly(n) number of TM configurations that represents the entire processing of S.

Additionally, as to find the input whose return decides the question and simulate the running of S only for this input is impossible (see in Way 1.iii below), the particular fixed running time P(n) of a specific restricted type X program cannot be computed in any fixed poly(n) upper bounded number of deterministic computational steps. Hence, an instance of the XG-SAT cannot be reduced in polynomial time into another one of a P(n)-time decidable problem, because the reducer machine must run in polynomial time in this case, but it cannot previously know or compute what upper bounds that time P(n). ¾

Suppose that someone claims, with the following argument, that the P ≠ NP proof of mine fails:

“– The author assumes that the 4 ways mentioned are the only way to solve the problem. Why can't the DTM Q decide the question some other way?”

The answer is so easy: Q cannot decide the question by some other way because there is no another possible way to decide the XG-SAT besides the four ones mentioned above: These ways do not specify type, structure, form, code, nature, shape or kind of computation, neither structure (or lack thereof) of data – but just the number and kind of inputs (arbitrary or computed) tested in eventual simulated running of S –, into any running of any DTM that tries to decide the XG-SAT: (1) all inputs; (2) arbitrary ones less than all; (3) computed ones less than all; or (4) none (there is no simulating S at all).

Can there be some other way? No, by a reasoning similar to pigeonholes from pigeonhole principle: Either Q simulates S or not. And simulating S for more than all inputs – or for any subset with exponential number of them – leads to exp(n) running time, as explained in the Way 1.i; less than none go to negative number of inputs, which makes no sense in actual computations; and between these limits the number and kind of inputs for eventual simulated running of S must be one from the four mentioned above. Consequently, all the possible deterministic computations to decide the XG-SAT are really into one from these four ways.

Can we create new ways to decide in deterministic polynomial time the XG-SAT combining the four ones? Unfortunately, no way: The way 1.i is useless to decide in deterministic polynomial time the question; the way 1.ii is useless to decide in any time the XG-SAT; and the combination of the ways 1.iii and 2 results simply in the way 1.iii – when none result from the simulation is used by Q in order to answer the question, which is a case treated below in the way 1.iii.

Hence, claims like above do not go to refute this P ≠ NP proof.

Note, yet, that the method utilized in this proof cannot be adapted to decide whether SAT is in P, because if a program S is simulating a Boolean formula with n variables, it must always halt for all the possible inputs, and its running time must be the same for any input; however, these additional restricted conditions cannot be held in general restricted type X programs, like ones in the proofs of the Props. 5.2 and 5.3 below. Hence, to decide whether an arbitrary general deterministic computer program computes determined output for determined input (which is undecidable, by the Rice's Theorem^[11]) cannot be reduced to SAT as it does to XG-SAT (as demonstrated in these proofs), and then any attempt to adapt my proof to solve whether SAT is in P is condemned to fault.

See that if S is simulating a Boolean formula with n variables, then the Rice's Theorem cannot be applied to the S behavior for any input, since it is restricted for all the possible ones.

Finally, suppose that else one tries to refute the proof saying:

“This proof follows a common theme: Defines an NP problem with a certain structure, argues that any algorithm that solves that problem must work in a certain way and any algorithm that works that way must examine an exponential number of possibilities. But we can't assume anything about how an algorithm works. Algorithms can ignore the underlying semantic meaning of the input and focus on the syntactic part, the bits themselves.”

As in the previous “refutation” of my proof, the answer is also very easy: If the DTM Q ignores the underlying semantic meaning of w and focus on its syntactic part, the bits themselves, considering w just a series of bits, this approach only places Q into the Way 2, where the proof continues to hold, naturally.

Shortly, the spirit of the proof is very simple: the XG-SAT is decidable by brute-force search because whether S returns 1 for at least one input from all the 2ⁿ possible ones is decidable, whereas whether S returns 1 for at least one from a nonempty proper subset of them is in general undecidable (since S can even not halt for any input from such a subset), by Def. 2.1, which does that all the other ways to decide the XG-SAT (without brute-force searching) be absolutely hopeless.

Consequently, we can say that the profoundest question in Complexity Theory was solved by this plain ingenious characterization, the Def. 2.1!

Be brave and see below that all these four exhaustive ways to decide in deterministic polynomial time the XG-SAT fail:

Way 1.i Q simulates the running of S for all the possible inputs:

The obvious way to implement the DTM Q is to construct a universal DTM that simulates the running of S and submits to it each one of the 2ⁿ possible inputs, verifying whether it returns 1 for at least one (in a breadth-first search, to avoid running forever in a computation path that does not halt): If all returns are 0, then w is not in XG-SAT; otherwise, then it is.

Nevertheless, this brute-force method, on worst case, can decide the problem only at the end of testing all the 2ⁿ possible inputs, in time exp(n).

Way 1.ii Q simulates the running of S for all the inputs from an arbitrary nonempty proper subset of all them:

Note that to simulate the running of S only for a polynomial number of arbitrary inputs (or just for a number of them less than all the possible ones – for instance: n^{log n}) does not work: Even the test of 2ⁿ – 2 inputs on the simulation cannot help to decide whether S returns 1 for some from the two not simulated ones (in fact, this simulation cannot help to decide even whether S simply halts for a specified input from these two ones).

Moreover, even the simple question whether S halts for at least one input from an arbitrary nonempty proper subset of the set of all the 2ⁿ possible inputs is undecidable, of course, by Def. 2.1. (Obs.: This question is only decidable for the set of all the 2ⁿ possible inputs: The answer is always “True”, by Def. 2.1.)

Way 1.iii Q computes anyway the input whose return decides the question and simulates the running of S only for this input:

Proposition 5.2. A DTM Q cannot compute, without simulating the running of S for all the 2ⁿ possible inputs, a nonempty proper subset of ones, where the return from S for one of them decides the question, and then to simulate the running of S only for these inputs to decide the XG-SAT.

Proof. Let a well-formed string f be constructed with an arbitrary n, and let the restricted type X program F be below, where Q was, by the Turing-Church Thesis, translated into a computer program where was included the instruction Simulated_by_Q[e] := True; just before any instruction of this program that starts the simulation of F for any input e (Simulated_by_Q is a global variable of type dynamic array or vector of Booleans values that was initialized with False in all its positions).

We call Q’ to this program derived from Q. Verify that if Q runs in polynomial time, then Q’ also do it, of course, and the behaviors and results from Q’ and Q are the same.

01. F(string input) // F is a restricted type X program, since Q’ and R are supposed poly-time // DTMs, and F will either return only 0’s or at least one 1

02. { n := length(input);

03. if (R(input) = “Yes”) return(0); // R returns always in polynomial time “Maybe”

04. if (R(input) = “No”) return(1); // Thus, R does not matter to the behavior of F

// But Q does not know it: see its work is hard!

05. concurrent_ifs // only one of the returns can close the concurrent instructions block

06. { // below, where the two ifs run concurrently

07. { if (Simulated_by_Q[input]) return(0); }

08. { if (Q’(f) = “Yes”) return(0); else return(1); }

09. }

10. }

Now, if Q does not simulate the running of F for all the 2ⁿ possible inputs, then it will unavoidable answer incorrectly “No”, after F returns 0 for all the simulated inputs, since F will in this case return 1 for all the non-simulated inputs (there is at least one, by Proposition 5.2), because for these ones there will be chance for the second concurrent_if (line 08) to detect at some moment the answer “No” from Q’, and then to return 1. Note that Q’ cannot answer “Yes”, because F will always return 0 for all the simulated inputs, by the first concurrent_if (line 07), and the answer from Q’ is based in the returns from F for all the simulated inputs. See that the contents of the global variable Simulated_by_Q (line 07) is known into F, because Q’ is concurrently running (line 08).

On the other hand, if Q simulates the running of F for all the 2ⁿ possible inputs, then it answers correctly “No”, after F returns 0 for all inputs, since F, in this case, returns 0 for all ones because the return of all 0 is by the first concurrent_if, when then there is no chance for the second concurrent_if to detect the answer “No” from Q’, and then to return 1. Unfortunately, Q can, by this way, decide the XG-SAT just in time exp(n), as was treated in Way 1.i.

See that if Q does not simulate the running of S for any input at all – or if none result from the simulation is used by Q in order to answer the question –, then it will inevitably answer incorrectly at some moment, by diagonalization that exists into string f, on the second concurrent_if of F.

Finally, suppose that Q could decide whether there is diagonalization into string f. In this case, Q could stay running forever, without simulating the running of F (or simulating it and no using the results 0 from this simulation to answer “No”) and no returning anything at all, which would imply that f is not a well-formed string, and then Q would not be incorrect. Alternatively in this case, Q could attempt to decide the question either without simulating the running of S for any input at all, or simulating it for some inputs and ignoring the results 0 from this simulation (there is no result 1, of course), either considering thereby w just a bit string, or engaging in more indirect reasoning about the code of S, as in the Way 2 below. However, Q’ can in general be any arbitrary deterministic program and can compute using or not the value of input for F, besides its proper input (the string f). Here, if Q’(f) runs in polynomial time either returning always “Yes” for all values of input not simulated by Q, or returning another result for at least one, then f is a well-formed string (independently of the behavior of Q(f)), and there is no diagonalization into it. Consequently, there is diagonalization into string f if and only if Q(f) = Q’(f) independently of the value of input.

Hence, if Q can decide whether there is diagonalization into string f, without simulating the running of S for all the 2ⁿ possible inputs, then Q can decide whether the language of a given arbitrary TM (Q’) has a particular nontrivial property (Q’ accepts f if and only if itself (Q) does it; in other words, Q(f) = Q’(f) independently of the value of input). However, this problem is undecidable, by the Rice's Theorem (reflect: Q’ could be any computer program). Hence, Q cannot decide it; thus, Q is condemned to fault, too: without knowing neither computing whether there is diagonalization into string f, to answer incorrectly the question, by the diagonalization above; or to simulate the running of F for all the 2ⁿ possible inputs, in time exp(n). ¾

Note that, in general, the Rice's Theorem can be applied to the S behavior for a nonempty proper subset of all the 2ⁿ possible inputs (because this behavior is arbitrary, by Def. 2.1: in this case, S can not halt for any input from this subset), but cannot do it to the total S behavior for all ones (since this behavior is restricted, by Def. 2.1: in this case, either all results from S are 0 or at least one is 1).

Way 2. Q does not simulate the running of S at all:

If the running time of Q depends on the one of the restricted type X program S into w for some input (where if S does not halt for any input, then Q does not halt at all, too), which occurs when Q acts reducing w into instance of another problem or simulating the running of S, then the use of the diagonalization method in order to demonstrate that Q cannot decide the problem fails, since Q does not have to be as restricted as S. But, as these running times are independent ones in the special case treated here, where w is considered just a bit string, or Q decides whether S returns 1 for some input by engaging in more indirect reasoning about the code of S, without simulating it, then we can use diagonalization in order to demonstrate that Q cannot decide the XG-SAT.

Note that if the running time of Q is anyway always greater than one of the restricted type X program S into w for some input (where, remember, if S does not halt for any input, then Q does not halt at all, too), then Q is, maybe indirectly, simulating the running of S for this same input or reducing the instance of the XG-SAT constructed with S to instance of another problem, of course. In general, to reduce in polynomial time an instance of the XG-SAT is impossible, by the proof of the Proposition 5.1. We will see below that to decide the XG-SAT without simulating the running of S – or do it in a running time upper bounded by a fixed integer polynomial function of |w| – is impossible, too:

Proposition 5.3. A DTM Q cannot, without reducing or simulating the running of S for any input, decide the XG-SAT problem.

Proof. Let S encoded into w be the program:

01. S(string input)

02. {

03. n := length(input);

04. if (integer(input) = 2^n – 1) { if (T(w) = “Yes”) return(0); else return(1); } else return(0);

05. }

Where T is an arbitrary deterministic program. Hence, if Q can, without reducing or simulating the running of S for any input, decide the XG-SAT problem, then it can decide whether the language of T has a particular nontrivial property: T(w) != Q(w), since otherwise then Q cannot answer anything in polynomial time, because whatever it answers will be incorrect, by diagonalization that holds in this case (S returns 0 for all inputs of the form different from 1ⁿ, and the answer from T(w) is inverted and returned by S when it process the input of the form 1ⁿ – what is the same as integer(input) = 2^n – 1: See that there is only one input of this form for each n. Thus, if T(w) returns “Yes”, then w is not in XG-SAT, and vice versa). However, if T(w) != Q(w) and T(w) runs in polynomial time, then there is no diagonalization into S, and Q must decide what T(w) returns to decide the question. That is, before Q answers whatever in polynomial time, it must decide whether T(w) = Q(w), to avoid that the diagonalization above forces it to error (reflect: T can be any computer program).

Nevertheless, this problem is undecidable, by the Rice's Theorem; hence, the DTM Q cannot, without reducing or simulating the running of S for any input, decide the XG-SAT. ¾

Observe that if Q tries to test whether the string w above is in XG-SAT (where Q(w) can return: “Yes”; “No”; or it does not halt) simulating the running of S for all the possible inputs, then S returns in time P(n) 0 for all ones of the form different from 1ⁿ, but, if T(w) = Q(w), then the simulation of the running of S never halts and never returns any value for the input of the form 1ⁿ, by infinite regress, which implies that Q does not halt and never answer incorrectly, even though without deciding whether T(w) = Q(w), obviously, since it remains forever waiting the return from this simulation for input of the form 1ⁿ, deluded without knowing that it never does. Notice that if T answers anything in polynomial time, then w is a well-formed string; otherwise, then it is not.

Perceive that to state that Q answers whatsoever if and only if w is a well-formed string does not work, because, as demonstrated in Section 3.3, L (the set of all well-formed strings) is a non-RE language, which implies that Q cannot decide whether w is a well-formed string in order to decide accordingly whether it can answer anything without mistaking. That is, in order to Q works in this case, it must assume absolutely that w is a well-formed string, and then this assumption implies that it is really true, and that Q for the input w returns in polynomial time incorrect answer, by the diagonalization above into S.

Proposition 5.4. A DTM Q with running time upper bounded by ƒ(|w|), where ƒ is a fixed integer polynomial function of |w|, cannot decide the XG-SAT.

Proof. Let S encoded into w be the program:

01. S(string input)

02. {

03. n := length(input);

04. if (integer(input) = 2^n – 1) {

05. concurrent_ifs {

06. if (T(w) = “Yes”) return(0); else return(1);

07. if (Timer > |w|^k) return(1);

08. }

09. }

10. else return(0);

11. }

Where T is an arbitrary deterministic program, k is an arbitrary fixed finite positive integer, Timer counts (in another “thread” or “concurrent process”) the running time of S, and the two internal if are evaluated concurrently while T runs for the input w. Thus, as the functions length and integer are poly(n)-time, S is a restricted type X program, regardless of the behavior of T. See that, as S returns 0 for all inputs of the form different from 1ⁿ, if T(w) answers in running time less than |w|^k, then its answer is inverted when S process the input of the form 1ⁿ, and T is forced to the error if it tries to be a decider for XG-SAT. Therefore, as T(w) can be equal to Q(w) – (if Q and T are equivalent, for instance) – even though Q cannot decide whether it is true that T(w) = Q(w), by the Rice's Theorem (reflect: T can be any computer program) –, this implies that, for large enough k (when |w|^k > ƒ(|w|), Q fails: It cannot know or compute that it cannot in this case answer correctly the question in running time less than |w|^k, by the diagonalization above. Hence, Q is again condemned to fault: To answer incorrectly the question before |w|^k computational steps, for some large enough k. ¾

Observe again that if the DTM Q decides the XG-SAT simulating the running of S, then Q cannot run in time upper bounded by any fixed polynomial function of |w| (in fact, none TM – DTM or NTM – that decides the XG-SAT can do it), undoubtedly, by Def. 2.1.

Conclusion:

As demonstrated above, all the four exhaustive possible ways to decide in deterministic polynomial time the XG-SAT fail: Consequently, there exists a computational decision problem that can be decided in nondeterministic polynomial time, but not in deterministic polynomial time, which implies P ≠ NP, naturally, in our sad computational world. ¾

For this reason, by union of the Rice's Theorem, the diagonalization method and the complexity classes P and NP, this proof is a beautiful unification and an amazing synthesis between the Computability Theory and the Computational Complexity Theory.

Lastly, someone can say that if a fixed p(n) ³ time P(n) of the program S into w is given (see this one is not deterministic poly-time computable, by Proposition 3.2), then the instances of the XG-SAT can be reduced to Boolean formula ones by Cook-Levin Theorem, and then if the SAT is decidable in deterministic poly-time, then the XG-SAT is too. Big idea!

This conclusion is erroneous, however, since knowing a fixed polynomial p(n) ³ that time P(n) is unnecessary to decide the problem (the universal NTM in Section 4 and the universal DTM in Way 1.i decide the XG-SAT without knowing this information (or without such an input), naturally), proving that nondeterministic computation is fundamentally much more faster than deterministic computation, and that the brute-force search is unfortunately unavoidable in the real-world computations (I’m very sorry).

5.1 Running time of the functions into programs

About running in time P(n) and time greater than P(n), let the function be:

01. Poly_Function(string input)
02. {

03. int i, counter := 0, n := length(input);

04. for i := 1 to n^10 { counter := counter + 1; } // poly(n) upper bounded running time

05. if (counter > 100) return(1); else return(0);
06. }

The function above evaluated at string input is just a number, naturally. But we can decide that its running time is poly(n) upper bounded, where n = |input|. We don't need a TM to decide it. On the other hand, let the function be:

01. SuperPoly_Function(string input)

02. {

03. int i, counter := 0, n := length(input);

04. for i := 1 to 2^n { counter := counter + 1; } // exp(n) upper bounded running time
05. if (counter > 100) return(1); else return(0);
06. }

Of course, the running time of the function above is exponential in n. We know countless functions as the ones above ^[2] to use them in order to make restricted type X programs. Constructing restricted type X programs using algorithms with known running time is human work, not TM computation ^[2].

5.2 Example of construction of an instance of the XG-SAT

Let the restricted type X program S be:

01. S(string input)

02. {

03. remainder := mod(integer(input), 2); // remainder on division of input (converted into

// integer) by 2

04. if (remainder = 0) return(Fun2(input)); // returns the value returned by Fun2 and halts

05. if (remainder = 1) return(Fun1(input)); // never halts

06. }

07. Fun1(string input) {
08. do { input := “1”; } while (1 = 1); // infinite loop

09. return(1);
10. }

11. Fun2(string input) {

12. int i, counter := 0, n := length(input);

13. for i := 1 to n^10 { counter := counter + 1; } // poly(n) upper bounded running time

14. if (counter > 0) return(1); else return(0);
15. }

Thus, we can simply convert this program S into a DTM M, translate it into a binary form s, and then construct the well-formed string w = 111111110s, an instance of the XG-SAT. Here, constructing XG-SAT instances, it stands very clear that the human reasoning is much more powerful than mechanical (TM) computation.

6. Baker-Gill-Solovay Theorem and the Proof

Verify that the proof does not use the diagonalization method (except in the justified special cases in Section 5) and it is based about the difference, on worst cases, between running times from a DTM and an NTM that recognize the L_z-language L, as demonstrated in Way 1.i of Section 5 compared to Section 4.

Moreover, notice that the addition into the proof methods of oracles to a PSPACE-Complete language W does not imply that false statement P^W ≠ NP^W (because the proof cannot be adapted to demonstrate that P^W ≠ NP^W, since a DTM Q with an oracle to W could simulate any NTM with the same oracle using only a poly(n)-quantity of space, in an adapted Way 1.i, which would otherwise prove that P^W = NP^W).

These facts imply that the Baker-Gill-Solovay Theorem of inseparability of the classes P and NP by oracle-invariant methods (techniques that are conserved under the addition of oracles, like the pure diagonalization method without algebraic oracle^[8]) does not refute this P ≠ NP proof. In other words, my proof technique does not relativize^[4].

7. Razborov-Rudich Theorem and the Proof

SAT's weakness – The proof does not try to prove any lower bounds on the circuit complexity of a Boolean function, because it does not try to solve the still open question whether SAT is in P, since to prove P ≠ NP it was not necessary to solve the SAT question (for the proof, different from the wrong conclusion in [3, 6], it is irrelevant whether SAT is in P), whereas it was enough to prove that XG-SAT is in NP but not in P: Thus, the Razborov-Rudich Theorem of the Natural Proofs does not refute this proof. In other words, my proof technique does not naturalize^[7].

8. Related Work

There is no relevant related work on the goal to really solve the P versus NP question. From important papers upon the matter, there are only some “negative” results, like the referred ones in Sections 6 and 7 and, more recently, as an extension of the relativization in Section 6, the proof that techniques that are conserved under the addition of an oracle and a low-degree extension of it over a finite field or ring cannot work on this question too, by the concept of algebrization, explained in [8].

Remember, however, that my proof does not use the pure diagonalization method (as referred in Section 6), but it exploits properties of computation that are specific to the real world computers, and then this new barrier is not valid to refute it, too.

9. References

[1] J. E. Hopcroft, J. D. Ullman, and R. Motwani, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading MA, 2001.

[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (Second Edition), The Mit Press, Cambridge MA, 2001.

[3] K. J. Devlin, The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time, Basic Books, New York NY, 2002.

[4] M. Sipser, Introduction to the Theory of Computation – Second Edition, Thomson Course Technology, Boston MA, 2006.

[5] Adapted from the appendix of the paper Uniformly Hard Sets by L. Fortnow and R. Downey, unpublished, available: http://weblog.fortnow.com/media/ladner.pdf

[6] Cook S.A., “P versus NP problem”, unpublished, available: http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf

[7] From Wikipedia, the free encyclopedia, “Natural Proof”, unpublished, available: http://en.wikipedia.org/wiki/Natural_proof

[8] S. Aaronson and A. Wigderson, Algebrization: A New Barrier in Complexity Theory, Electronic Colloquium on Computational Complexity, Report No. 5 (2008), available: http://eccc.hpi-web.de/eccc-reports/2008/TR08-005/Paper.pdf

[9] O. Goldreich, On Promise Problems (in memory of Shimon Even (1935-2004)), unpublished, available: http://www.wisdom.weizmann.ac.il/~oded/PS/prpr.ps

[10] M. Sipser, Cambridge MA 02139, in The History and Status of the P Versus NP Question, p. 606, unpublished, available: http://www.seas.harvard.edu/courses/cs121/handouts/sipser-pvsnp.pdf

[11] From Wikipedia, the free encyclopedia, “Rice's Theorem”, unpublished, available: http://en.wikipedia.org/wiki/Rice's_theorem

[12] O. Goldreich, Notes on Levin’s Theory of Average-Case Complexity, unpublished, available: http://www.wisdom.weizmann.ac.il/~oded/COL/lnd.pdf

[13] A. L. Barbosa, P != RP Proof, unpublished, available: http://www.andrebarbosa.eti.br/P_different_RP_Proof_Eng.pdf

[14] From Wikipedia, the free encyclopedia, “P versus NP Problem”, unpublished, available: http://en.wikipedia.org/wiki/P_versus_NP_problem

[15] L. A. Hemaspaandra, K. Murray, and X. Tang, Barbosa, Uniform Polynomial Time Bounds, and Promises, Technical Report, unpublished, available: http://arxiv.org/abs/1106.1150

[16] From Wikipedia, the free encyclopedia, “Decision Problem”, unpublished, available: http://en.wikipedia.org/wiki/Decision_problem

[17] T. S. Kuhn, The Structure of Scientific Revolutions, University of Chicago Press, Chicago IL, 1962.

[18] From StackExchange (cstheory), cc-wiki, “Are runtime bounds in P decidable? (answer: no)”, unpublished, available: http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no

[19] A. L. Barbosa, NP Ë P/poly, unpublished, available: http://www.andrebarbosa.eti.br/NP_is_not_in_P-Poly_Proof_Eng.pdf

[20] From Wikipedia, the free encyclopedia, “Zermelo Set Theory”, unpublished, available: http://en.wikipedia.org/wiki/Zermelo_set_theory

André Luiz Barbosa – Goiânia - GO, Brazil – e-Mail: webmaster@andrebarbosa.eti.br – July 2009

Site....….. : www.andrebarbosa.eti.br

Blog...….. : blog.andrebarbosa.eti.br

This Paper : www.andrebarbosa.eti.br/P_different_NP_Proof_Eng.htm

PDF……. : www.andrebarbosa.eti.br/P_different_NP_Proof_Eng.pdf

arXiv…… : http://arxiv.org/ftp/arxiv/papers/0907/0907.3965.pdf

Contents

2 Definition of Restricted Type X Program 03

3.4.1.1 How can a Theorem be false?

4. Old demonstration that the XG-SAT is in NP