New answers tagged complexity-classes
7
votes
Accepted
What can we do with a generic oracle (as opposed to a random one)?
In fact, GenericallyP = P:
Proposition. The following are equivalent for any language $L$:
$L\in\mathbf P$.
$L\in\mathbf{GenericallyP}$.
$\{A\in\{0,1\}^\mathbb N:L\in\mathbf P^A\}$ is not meager.
...
Top 50 recent answers are included
Related Tags
complexity-classes × 668cc.complexity-theory × 497
reference-request × 65
counting-complexity × 48
np-hardness × 47
time-complexity × 41
circuit-complexity × 37
quantum-computing × 31
oracles × 30
polynomial-hierarchy × 27
ds.algorithms × 26
big-picture × 22
reductions × 22
conditional-results × 22
logspace × 22
sat × 21
computability × 18
np × 18
randomness × 15
p-vs-np × 14
relativization × 14
approximation-hardness × 13
dc.parallel-comp × 13
interactive-proofs × 13
advice-and-nonuniformity × 13