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$ ...
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 ...
Top 50 recent answers are included
Related Tags
complexity-classes × 648cc.complexity-theory × 485
reference-request × 63
np-hardness × 45
counting-complexity × 44
time-complexity × 38
circuit-complexity × 36
quantum-computing × 31
oracles × 28
ds.algorithms × 26
polynomial-hierarchy × 26
reductions × 23
big-picture × 22
conditional-results × 22
logspace × 22
sat × 21
np × 18
computability × 15
randomness × 14
p-vs-np × 14
relativization × 14
approximation-hardness × 13
dc.parallel-comp × 13
interactive-proofs × 13
lower-bounds × 11