0
$\begingroup$

I just newly started looking into computational complexity.

Since we don’t know if P = NP, we would like to have a way of saying “This problem is in NP and is really hard unless P = NP.”

This is made more formal by the notion of NP-completeness.

Therefore, we say a problem A is NP-complete if

(a) it is in NP, and (b) every problem B in NP is polynomial-time reducible to A.

Using a graph $G$ and an edge $e$ in $G$ as an example, how do I determine whether or not there is a Hamiltonian cycle that includes $e$?

With this, I could show that the problem is NP-complete and use the same approach for similar problems.

$\endgroup$

2 Answers 2

1
$\begingroup$

There is no known efficient way to determine whether or not there is a Hamiltonian cycle that includes $e$. That is a NP-complete problem. (If you could determine that, you could use that as a subroutine to test whether the graph contains any Hamiltonian cycle, and even to find a Hamiltonian cycle if one exists; so it's not reasonable to expect there to be an efficient algorithm to do that.)

$\endgroup$
3
0
$\begingroup$

A problem is in NP if every instance with the answer “yes” can be solved in polynomial time if you get a clever hint.

A problem X is NP complete if it is in NP (and not harder), and some NP-complete problem can be solved by solving X. That means if I take an instance Y of this other NP-complete problem then I can construct a problem X so a solution of X allows me to solve Y. That doesn’t require that X is easy to solve.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.