We can have #P functions hard for the polynomial-time hierarchy (Toda) or very easy but can they capture exactly the power of NP?

*Conjecture*: There exists an f in #P such that
P^{f}=P^{SAT}.

There is some precedence: counting the number of graph isomorphisms is equivalent to solving graph isomorphism.

The conjecture is true if NP=UP, NP=PP or if GI is NP-complete. I don't believe any of these. Does the conjecture follow from some believable assumption or perhaps no assumption at all? We don't know if there exists a relativized world where the conjecture does not hold.

Even the following weaker conjecture is open:
There exists an f in #P such that
NP⊆P^{f}⊆PH.

A good solution to these conjectures might help us settle the checkability of SAT.

## No comments:

## Post a Comment