3 ms·

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 a

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.

zer8k 3y ago
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.
- Tainnor 3y ago
  > 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.
- Skeime 3y ago
  “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.
- jsolson 3y ago
  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.
  - zer8k 3y ago
    > - 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).

zer8k 3y ago

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.

Tainnor 3y ago
> 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.
Skeime 3y ago
“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.
jsolson 3y ago
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.
- zer8k 3y ago
  > - 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).