New answers tagged complexity-classes
12
votes
Accepted
Why the "balanced vs constant function" problem is not a proof that P ≠ BPP?
It is true that if the function $f$ is given by an oracle, then a randomized algorithm is exponentially faster than any deterministic algorithm. With an oracle function, however, this is not a $BPP$ ...
- 11.1k
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 ...
- 11.1k
Top 50 recent answers are included