Tagged Questions
1
vote
1answer
300 views
The Relationship between P^NP and the Permanent
In the lecture notes Introduction to Complexity Theory by Goldreich, there is a section called "How close is $\#P$ is to $NP$". It is stated there that a $P^{NP}$ machine would approximate $\#P$ in ...
