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
Why is this conjecture believed? What is the reference for this? Is there a converse such as "if there is an f in #P satisfying P^f=P^SAT then PP=NP or PP=UP?"
ReplyDeleteThe connection link https://blog.computationalcomplexity.org/2004/03/is-satisfiability-checkable.html is broken.
(This is Bill, not Lance)
Delete1) I can't speak for Lance but I view this conjecture as saying: This is an interesting question, rather than having an opinion of its truth.
2) I clicked on the link in the email I get when someone posts, and it worked. I then put the link into this post as an experiement and it worked. So it seems to not be broken. Which surprises me- this is the first time ever (and this blog has been gonig for over 20 years) that a report of broken link was not true.
"A good solution to these conjectures might help us settle the checkability of SAT. "
ReplyDeleteIt landed in https://fortnow.com/lance/complog/archive/2004_03_21_archive.html#108004475815397466
I see the confusion.. I posted the correct link to the broken link in previous comment.
ReplyDeleteEmail me DIRECTLy so we can resolve QUICKLY which links are broken or misdircted or what, and I can respond quickly, rather than commuicating through these comments.
DeleteSpan-L is believed strictly in #P and P^SpanL =P^#P and P^GapL is believed strictly in P. So such an f seems to be strictly in SpanL and outside GapL+ ( defined as {g in GapL: g>=0}) if we want P^f=P^SAT. Seems like f would be 'between' GapL+ and SpanL but GapL is not known to be comparable to SpanL. Is GapL+ (may be defined by computing determinants which are non-negative?? Not sure) in SpanL known?
ReplyDelete