warieth

u/warieth


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)

45

You've reached the end of this feed.