Determining that it's P is easy. So... If I were given a generic problem/algorithm, how would I determine whether the algorithm is NP or NP-Complete?
I'll give it a shot with my logic. Let me know if this sounds right:
I want to argue that the Hamiltonian cycle decision problem (does a Hamiltonian cycle of weight <= w exist in graph G?) is NP-Complete. I must show that:
1. It itself is NP
2. Any NP problem can be reduced to the Hamiltonian cycle decision problem.
To show 1:
The only way to solve it in polynomial time is to guess all the vertices nondeterministically, since using a deterministic approach would run in exponential time (brute force) . Verifying the result of the algorithm is possible in deterministic polynomial time, which is what makes the actual yes/no decision. For a graph of n edges and m vertices, this verification would just check to see if all traversed edges are valid/exist in the graph (loop through m edges), the total weight <= w, and make sure that no vertices are repeated, except for the first and last vertices should be the same (three loops through n vertices). Thus, the verification to decide yes/no takes O(n + m) time, which is in polynomial time.
To show 2:
The classic traveling salesman decision problem problem (TSP)... I would argue that since the problem can be reduced to a Hamiltonian cycle problem (i.e. its input can be rephrased to "vertices" instead of cities, and "weights" instead of costs) AND this reduction can be done in polynomial time (should be O(n + m) for n cities and m costs), then the TSP must be at least as complex as the Hamiltonian cycle decision problem. So we can assume that TSP is class NP. This also shows that the Hamiltonian cycle problem is NP-Complete because we were able to reduce another NP algorithm and solve generally with the Hamiltonian cycle algorithm.
How close or far am I?
Showing that something is in NP is usually easy. You just have to exhibit a method of checking the validity of the yes/no solution in non-deterministic, polynomial time, but you already know this. A lot of problems you run into will be in NP.
To show that something is NP-complete, what you suggested would work. However, 99% of the time, it will be easier to:
1) prove its in NP
2) reduce a known NP-complete problem to it
Whether by knowledge or luck, you chose to reduce from decision-TSP, which is known to be NP-complete.
Your argument for a non-deterministic algorithm is mostly ok. The one issue I have is this: "since using a deterministic approach would run in exponential time (brute force)." That is not obvious. If P=NP (likely or unlikely as that is), then the statement is false. Yes, the state-space is exponential in size. Yes, checking every state exhaustively requires exponential time. But the state-space for MST is also exponential in size. Yet the time needed to compute MST is almost linear (known to be amortized linear if randomness is allowed; amortized to somewhere btwn linear and linear*inv_ackerman otherwise). You've stated that the state-space is exponential in size, but have given no indication that a deterministic algorithm must take exponential time. As esun said, if you can pull that off, you get $1M and everlasting fame...
Either way, the performance of a determinstic polynomial checker is totally irrelevant here. You don't care at all whether a deterministic poly algo can get the job done (unless you want to show something is in NP by first showing that it is in P, since P is at least a subset of NP; but I've never seen anyone need to do that, lol).
In your reduction from TSP to Hamiltonian cycle is generally OK, but there are a few issues. Hamiltonian cycle is considered a special case of TSP. One minor technical detail to note is that TSP is usually considered on complete graphs; so to make your input to hamiltonian cycle a complete graph (if it isn't), what would you do?
Also the statement "So we can assume that TSP is class NP." is awkward. "So we can assume" indicates that something you've said implies this assumption. That is not true. The decision version of TSP has been proven to be NP-complete (the non-decision TSP is NP-hard). There's nothing to assume here.
Lastly, it is not enough that decision-TSP is in NP. If decision-TSP were only NP (not NP-complete or NP-hard), then reducing it to Hamiltonian cycle proves *nothing*
In particular, one condition for Hamiltonian cycle to be NP-complete is (as you stated) that ANY NP problem can be reduced to it. If decision-TSP was 'merely' NP, then you've only reduced ONE NP problem to Hamiltonian cycle, not any. On the other hand, reducing a known NP-complete problem (call it A, e.g., decision-TSP) to hamiltonian cycle is the same as reducing ANY NP problem to hamiltonian cycle. That is, since A is NP-complete, then any NP problem can be reduced to A. And since you've shown a reduction from A to Hamiltonian cycle, then by transitivity, any NP problem can be reduced to hamiltonian cycle. Does that make sense?
Basically you got the main ideas right, but are still missing some of the details in this NP mess.
edit: oh and mad props/respect/etc to esun. That's one of the cleanest introductory-level explanations of P, NP, NP-complete, etc. that I've run across.
Facebook
Twitter