Search code examples
algorithmcomplexity-theory

If a polynomial time algorithm for an NP-Complete problem is found, does this imply that it is the same time complexity for all NP problems?


If a polynomial time algorithm for an NP-Complete problem is found, lets say its O(n^2) hypothetically, does this imply that there is an O(n^2) solution for all NP problem? I know this would imply that there is a polynomial solution for all NP-problems, but would it necessarily be O(n^2)?


Solution

  • Not necessarily

    A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x.

    Therefore an algorithm that solves one NP-Complete problem means we can solve any other problem in NP by transforming it to an instance of that problem and solving it. But the transformation could be any complexity as long as its polynomial we satisfy the condition.

    So the answer to your question in no, an O(N^2) algorithm to solve an NP-Complete problem does not imply all NP problems can be solved in O(N^2) time, it only guarantees there exists a polynomial time algorithm to solve it.

    ie O(N^2) + T(N) where T(N) is the complexity to transform the problem instance