The NP vs coNP question is about a proof?
The NP vs coNp question is about a mathematical construct. What would be the certificate for the no answer for a NP-complete problem? The construct is not enought, so the question is undecided because the lack of proof.
The undirected Hamiltonian cycle's non existence can be show: Given a graph, there exist a set of nodes selected from the graph's nodes (the size of the set must be > 0, so not an empty set), remove the selected nodes from the graph (and the connecting edges), then count the connected parts. The number of the connected components is greater than the number of the removed nodes, then no Hamiltonian cycle exist in the graph.
The construct needs two proofs (both directions) to be correct:
- If a Hamiltonian cycle contained in the graph, then there is no certificate for the non-existence.
- If there is no Hamiltonian cycle contained in the graph, then the certificate has to exists. This part is missing.
If the graph contains a Hamiltonian cycle, then that would not allow the graph to split into more parts. A cycle breaks up in a predictable way:
- 1 node removed -> stays in 1 part,
- 2 node removed -> splits into at most 2 parts,
- 3 nodes removed -> splits at most 3 parts,
- ... The extra edges that the graph can have only reduce the number of components, can’t increase it.
Posted Apr 3, 2022, 9:24 AM UTC
Your argument that there is a short certificate for Hamiltonian cycle non-existence is false: the petersen graph does not have a Hamiltonian cycle, but since if you delete any vertex it does have a Hamiltonian cycle there cannot be a set of vertices which you delete that will give you your certificate.
Thank you, you are right.