# Why I believe P ≠ NP

## The HAMCYCLE problem

If a graph $G\left(V, E\right)$ contains a Hamiltonian cycle, we can pick a subset $E’ ⊆ E$ of edges in the graph such that:

- All vertices in $G$ appear in the resulting subgraph and,
- Starting at any vertex, we are able to visit each vertex exactly once, except for the starting vertex, which is also the last vertex in the cycle.

The Hamiltonian cycle problem asks if a graph $G$ contains a Hamiltonian cycle – i.e., a cycle on which each vertex appears exactly once, except for the first (and the last) vertex of the cycle.

The problem is NP-Complete. It is in NP because while no polynomial
time algorithm is known to solve it, given a graph and a “certificate” which
consists of a set of vertices claimed to constitute a Hamiltonian cycle, one can
decide in polynomial time if the certificate is bogus. Additionally, *any*
problem in NP can be reduced in polynomial time to an instance of the
Hamiltonian cycle problem, hence making it NP-Complete. Here is such an
example reduction, which works on the related Hamiltonian Path problem,
which in turn can be reduced in polynomial time to the Hamiltonian Cycle
problem.

## The formal language described by HAMCYCLE

This problem describes a language which is in NP. Here, the notation represents a suitable binary encoding of the graph G (i.e., a string over ).

## Co-HAMCYCLE

Consider the complement of problem: Finding if a graph is *not* Hamiltonian.
This problem is at least as hard as the original problem, since if there was
a polynomial time algorithm to tell us whether a given graph G is
non-Hamiltonian, we could just use this to solve the original problem of
deciding whether G is Hamiltonian.

This complement is in the co-NP class by definition, and it is an open problem whether co-NP = NP. Since P ⊆ NP, and P is closed under the complement, P ⊆ NP ∩ co-NP. And if P = NP, co-NP = NP (but the inverse does not hold), but if co-NP ≠ NP, then P ≠ NP.

The figure above shows that if NP and co-NP are different, P has to be different than NP, since it must be a subset of both NP and co-NP.

## What if co-NP = NP?

Again, proving that co-NP = NP does not show that P = NP (although it does address an important standing problem in its own right, and leaves the possibility open that P = NP).

To show that co-NP = NP, we’d have to show that all problems in co-NP are verifiable in polynomial time. Let’s see what that means in the context of the co-HAMCYLE problem.

To provide a certificate for the co-HAMCYCLE problem would require encoding the
*impossibility* of the set of edges in G to be form a Hamiltonian graph. In
other words, the certificate would have to provide a badge for a claim that the
graph G is not Hamiltonian. An example certificate would be the enumeration of
all possible cycles in the graph. The verification algorithm would then have to
check each cycle for being non-Hamiltonian, and also check that the set of
cycles in the certificate is exhaustive (because there might be a Hamiltonian
cycle that the certificate simply does not contain).

However, for this certificate to be verified in polynomial time, its length must
be polynomial in the size of the graph, and the check for exhaustiveness of the
certificate also needs to be carried out in polynomial time. I think this is
pretty hard, if not impossible to do. I don’t know how to prove this of course,
but if we prove that there can exist no certificate of length polynomial in the
size of the input graph, we’d have proven that co-HAMCYCLE is *not* in NP, i.e.,
NP ≠ co-NP, and by extension, since P must be contained in NP ∩ co-NP, P ≠ NP.