5 ms·

NP = Set of problems for which candidate solutions can be checked for correctness in polynomial time in the length of the input. P = Set of problems for which

NP = Set of problems for which candidate solutions can be checked for correctness in polynomial time in the length of the input. P = Set of problems for which we can find a solution in polynomial time in the length of the input. Clearly, P \subseteq NP. Proving P = NP would require proving NP \subseteq P, something which most people would believe to be a) highly unlikely b) difficult.

z3t4 11y ago
So basically I have to find a problem that categories as P but not NP!? Kinda like the Planck constant in quantum theory. f(2) = 4, f(3) = ? /brainstorming
- Ar-Curunir 11y ago
  Well no, every problem in P is in NP trivially. To prove P = NP, you would have to prove that one of the many NP-Complete problems has a polytime algorithm. Well that's not the only way to prove P = NP, but that's one approach.
  - nsnick 11y ago
    To prove that P does not equal NP you would have to prove that a problem thought to be NP Complete was in fact NP Intermediate. That is, the problem meets the conditions of NP, but NP Complete problems cannot be reduced to it.
    - Ar-Curunir 11y ago
      No, not really. There are many NP-Complete problems, and there are many NP problems that are thought to be neither NPC nor in P. In fact, if P != NP, there are infinitely many such problems. So proving P != NP could proceed by finding some problem in NP that is not also in P.
      - nsnick 11y ago
        Which problem do you think is NP but is not NP Complete?
        Ar-Curunir 11y ago
        See: https://en.wikipedia.org/wiki/NP-intermediate https://en.wikipedia.org/wiki/NP-intermediate
        nsnick 11y ago
        Great link I particularly like the part that says, "P = NP if and only if NPI is empty." seems to indicate that if there are any NP Intermediate problems P would be proven not to equal NP.
        mnarayan01 11y ago
        That's pretty far from your original statement. Which isn't to say that's not what you _meant_ in your original statement; just that it's not how I (and minimally the GP) read it.
- deleted 11y ago
  [deleted]

z3t4 11y ago

So basically I have to find a problem that categories as P but not NP!? Kinda like the Planck constant in quantum theory. f(2) = 4, f(3) = ? /brainstorming

Ar-Curunir 11y ago
Well no, every problem in P is in NP trivially. To prove P = NP, you would have to prove that one of the many NP-Complete problems has a polytime algorithm. Well that's not the only way to prove P = NP, but that's one approach.
- nsnick 11y ago
  To prove that P does not equal NP you would have to prove that a problem thought to be NP Complete was in fact NP Intermediate. That is, the problem meets the conditions of NP, but NP Complete problems cannot be reduced to it.
  - Ar-Curunir 11y ago
    No, not really. There are many NP-Complete problems, and there are many NP problems that are thought to be neither NPC nor in P. In fact, if P != NP, there are infinitely many such problems. So proving P != NP could proceed by finding some problem in NP that is not also in P.
    - nsnick 11y ago
      Which problem do you think is NP but is not NP Complete?
      - Ar-Curunir 11y ago
        See: https://en.wikipedia.org/wiki/NP-intermediate https://en.wikipedia.org/wiki/NP-intermediate
        nsnick 11y ago
        Great link I particularly like the part that says, "P = NP if and only if NPI is empty." seems to indicate that if there are any NP Intermediate problems P would be proven not to equal NP.
        mnarayan01 11y ago
        That's pretty far from your original statement. Which isn't to say that's not what you _meant_ in your original statement; just that it's not how I (and minimally the GP) read it.
deleted 11y ago
[deleted]