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 Pf=PSAT.
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⊆Pf⊆PH.
A good solution to these conjectures might help us settle the checkability of SAT.
Post a Comment