3 ms·
>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 reduc
by 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.