4 ms·

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

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.

quickthrower2 3y ago
--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
- Dylan16807 3y ago
  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.
- minitech 3y ago
  Not wrong, just a different criterion that describes the same complexity class.
- raincole 3y ago
  > --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.
viknesh 3y ago
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.
raincole 3y ago
^ 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.
earth2mars 3y ago
[flagged]
- minitech 3y ago
  Is this a generated answer?
zer8k 3y ago
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.

quickthrower2 3y ago

--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

Dylan16807 3y ago
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.
minitech 3y ago
Not wrong, just a different criterion that describes the same complexity class.
raincole 3y ago
> --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.

viknesh 3y ago

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.

raincole 3y ago

^ 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.

earth2mars 3y ago

[flagged]

minitech 3y ago
Is this a generated answer?

zer8k 3y ago

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.