5 ms·

So at least according to this P != NP. I’ve always been skeptical of this just because if you find an efficient optimal algorithm the problem moves between the

• spiznnx 9y ago
  >if you find an efficient optimal algorithm the problem moves between the classes This hasn't ever happened. You can prove an algorithm is in NP-hard by reducing another NP-hard problem to it. You can prove an algorithm is in P by showing the algorithm. If you find and efficient algorithm to a problem in NP-hard, you show P == NP. No one has ever done this. P != NP is considered by many to be most likely true.
  • andy_ppp 9y ago
    > You can prove an algorithm is in P by showing the algorithm. Thanks for clarifying - I always though that's what the above meant but I didn't realise that the reduction side was also important.