Hacker News Reader

Comment by jandrese | Hacker News Reader

From what I remember:

NP: Finding the solution takes more than polynomial time, but you can verify the answer is correct in polynomial time.

NP-Hard: Finding the solution takes more than polynomial time, and it also takes more than polynomial time to verify that the solution is correct.

NP-Complete: NP-Hard, but it can be transformed into any other NP-Complete problem in polynomial time. This is special because it means if you find a solution for any NP-Complete problem, you have found a solution for all of them. Finding an NP-Complete solution always seemed rather rather optimistic to me, but computer science professors obsessed over these problems.

Caveat: It has been more than 20 years since I was quizzed on this stuff, so it might be wrong.

View on HN

NP: Checking a solution takes polynomial time.

NP-Hard: "The problem is at least as hard as any problem in NP." Basically, if X is an NP hard problem and you are given an oracle to solve X, you can solve any problem in NP by first transforming it to an instance of X and then solving it.

NP Complete: The problem is NP Hard & in NP.

To add to this NP can also refer to the more formal idea of a non-deterministic turing machine being able to compute the problem in polynomial time. We learned NP as "Non-deterministic Polynomial (time)". I think the more practical definition is "not polynomial"...lol.

> To add to this NP can also refer to the more formal idea of a non-deterministic turing machine being able to compute the problem in polynomial time.

Yes. This definition is equivalent to the one about being verifiable in polynomial time, since your non-deterministic TM can just have a different branch for every possible verification "oracle".

> I think the more practical definition is "not polynomial"...lol.

Well, there are non-polynomial algorithms harder than NP. If a solution can't even be verified efficiently, for example.

“Not polynomial” is an easy trap to fall into (and one I have fallen into) but it’s really not correct. All polynomial-time problems are also NP problems (P=NP is about whether the converse is true, and if P=NP, all problems in NP are actually polynomial-time). So even if talking to a layman, saying that NP is non-polynomial is really missing the point of the question.

Following more or less directly from this:

- If you walk backwards from where the non-deterministic Turing machine halted, the list of taken state machine transitions is polynomial in length (naturally, as the machine stopped in polynomial time).

- Walking that polynomial length list of actually-taken edges forward through the Turing machine constitutes a polynomial time verification of the solution.

This is the essence of the equivalence between being able to solve problems in NP in polynomial time on a (hypothetical) non-deterministic Turing machine and being able to deterministically verify a solution to those problems in polynomial time.

> - If you walk backwards from where the non-deterministic Turing machine halted, the list of taken state machine transitions is polynomial in length (naturally, as the machine stopped in polynomial time).

> - Walking that polynomial length list of actually-taken edges forward through the Turing machine constitutes a polynomial time verification of the solution.

These are really great explanations that would've saved me so much trouble in graduate school. Connecting the automata itself to the term "nondeterministic turing machine" is something that is sorely missed is most CS programs I think. It's usually handwaved in automata theory in order to give you enough to head to compilers. Then you run into it again in graduate school algorithms where it is once again handwaved (because not even the professor fully understands it).

I don't think the downvotes here are fair given the corrections this person has received. These misconceptions are wildly common. I'm sure 90% of the downvoters couldn't even accurately identify this stuff.

^ The most common misconceptions about NP/NP-Complete/NP-Hard, packed in one comment!

But seriously for anyone reading this, please refer to the other sibling comments.

--Edit: this was wrong, see reply comment--

NP: you can verify the answer is correct in polynomial time. (and no other clauses)

Anything in P is in NP

I think it's worth saying what NP stands for.

Nondeterministic Polynomial. Where "nondeterministic" basically means you get to try every single polynomial solution in parallel.

Not wrong, just a different criterion that describes the same complexity class.

> --Edit: this was wrong, see reply comment--

You're not wrong tho. NP problems can be verified in polynomial time.

Nondetermisitic turnig machine is like a turing machine that has multiple "next steps" instead of one at a given time, and can migically choose the correct next step.

You can think it as "taking all the possible paths at the same time (but at the end only the correct one matters)". But you can also think it as "given all the 'choices' it made, check if there is actually such a path", in other words, verifying a certification.

Reply on news.ycombinator.com