Wednesday, April 21, 2004

Are There #P Functions Equivalent to SAT?

Help me solve this problem, write the paper with me, get an Erdös number of 3 and it won't cost you a cent.

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.

No comments:

Post a Comment