New answers tagged optimization
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 [...
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 ...
Top 50 recent answers are included