New NAE Members

Dear Professor,

Is $$P$$ equal to $$NP$$?

We pretend to show the answer of the $$P$$ versus $$NP$$ problem. Our principal argument is based in a technique that has been used throughout history in both formal mathematical and philosophical reasoning, as well as informal debate: The Reductio ad absurdum. Reductio ad absurdum is a common form of argument which seeks to demonstrate that a statement is true by showing that a false, untenable, or absurd result follows from its denial, or in turn to demonstrate that a statement is false by showing that a false, untenable, or absurd result follows from its acceptance.

We start assuming the hypothesis of $$P = NP$$ that will lead us to a contradiction. The argument is supported by a Theorem that states if $$P = NP$$, then the problem SUCCINCT HAMILTON PATH would be in $$P$$. In this Theorem, we take an arbitrary succinct representation $$C$$ of a graph $$G_{C}$$ with $$n$$ nodes, where $$n = 2^{b}$$ is a power of two and $$C$$ will be a Boolean circuit of $$2 \times b$$ input gates. Interestingly, if $$C$$ is a “yes” instance of SUCCINCT HAMILTON PATH, then there will be a linear order $$Q$$ on the nodes of $$G_{C}$$, that is, a binary relationship isomorphic to “<" on the nodes of $$G_{C}$$, such that consecutive nodes are connected in $$G_{C}$$. This linear order $$Q$$ must require several things:

* All distinct nodes of $$G_{C}$$ are comparable by $$Q$$,
* next, $$Q$$ must be transitive but not reflexive,
* and finally, any two consecutive nodes in $$Q$$ must be adjacent in $$G_{C}$$.

Any binary relationship $$Q$$ that has these properties must be a linear order, any two consecutive elements of which are adjacent in $$G_{C}$$, that is, it must be a Hamilton path.

On the other hand, the linear order $$Q$$ can be actually represented as a graph $$G_{Q}$$. In this way, the succinct representation $$C_{Q}$$ of the graph $$G_{Q}$$ will represent the linear order $$Q$$ too. We can define a polynomially balanced relation $$R_{Q}$$, where for all succinct representation $$C$$ of a graph: There is another Boolean circuit $$C_{Q}$$ that will represent a linear order $$Q$$ on the nodes of $$G_{C}$$ such that $$(C, C_{Q})$$ is in $$R_{Q}$$ if and only if $$C$$ is in SUCCINCT HAMILTON PATH.

It is easy to see, the graphs $$G_{C}$$ and $$G_{Q}$$ will comply with $$|G_{Q}| < |G_{C}|^{3}$$ when $$(C, C_{Q})$$ is in $$R_{Q}$$, since both graphs would have the same number of nodes and $$G_{C}$$ would contain a Hamilton path. Consequently, we obtain the same property for their succinct representations, that is, $$C_{Q}$$ should be polynomially bounded by $$C$$. Indeed, for a sufficiently large $$n$$, the Boolean circuits $$C$$ and $$C_{Q}$$ will be exponentially more succinct than $$G_{C}$$ and $$G_{Q}$$ respectively. Hence, if the graph $$G_{Q}$$ is polynomially bounded by the graph $$G_{C}$$ when $$(C, C_{Q})$$ is in $$R_{Q}$$, then $$\log_{2} |G_{Q}|$$ will be polynomially bounded by $$\log_{2} |G_{C}|$$.

We finally show $$R_{Q}$$ would be polynomially decidable if $$P = NP$$. For this purpose, we use the existential second-order logic expressions, used to express this graph-theoretic property (the existence of a Hamilton path), that are described in Computational Complexity book of Papadimitriou: Chapter "5.7 SECOND-ORDER LOGIC" in Example "5.12" from page "115". Indeed, we just simply replace those expressions with Universal quantifiers into equivalent Boolean tautologies.

Certainly, a language $$L$$ is in class $$NP$$ if there is a polynomially decidable and polynomially balanced relation $$R$$ such that $$L = \{x: (x, y) in R for some y\}$$. In this way, we show that SUCCINCT HAMILTON PATH would be in $$NP$$ if we assume our hypothesis, because the relation $$R_{Q}$$ would be polynomially decidable and polynomially balanced when $$P = NP$$. Moreover, since $$P$$ would be equal to $$NP$$, we obtain that SUCCINCT HAMILTON PATH would be in $$P$$ too.

But, we already know if $$P = NP$$, then $$EXP = NEXP$$. Since SUCCINCT HAMILTON PATH is in NEXP–complete, then it would be in EXP–complete, because the completeness of both classes uses the polynomial-time reduction. But, if some EXP–complete problem is in $$P$$, then $$P$$ should be equal to $$EXP$$, because $$P$$ and $$EXP$$ are closed under reductions and $$P$$ is a subset of $$EXP$$. However, as result of the Hierarchy Theorem the class $$P$$ cannot be equal to $$EXP$$. To sum up, we obtain a contradiction under the assumption that $$P = NP$$, and thus, we can claim that $$P$$ is not equal to $$NP$$ as a direct consequence of applying the Reductio ad absurdum rule.

You could see the details in:

https://hal.archives-ouvertes.fr/hal-01270398/document

Regards,
Frank.