New answers tagged

4 votes
Accepted

What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?

Regarding the title of the question: What is the reason to believe that quantum heuristic [algorithms] can solve NP-Complete problems? and in particular the statement in the body: There is an ever [...
Mark S's user avatar
  • 957
8 votes

Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable

The answer to the second question is no. Here is an example when the integer-output optimization problem is polynomial-time solvable, yet its fractional relaxation is NP-complete: In complements of ...
Andras Farago's user avatar

Top 50 recent answers are included