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.
...
- 16.9k
Top 50 recent answers are included