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

 

6 comments:

  1. 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?"

    The connection link https://blog.computationalcomplexity.org/2004/03/is-satisfiability-checkable.html is broken.

    ReplyDelete
    Replies
    1. (This is Bill, not Lance)
      1) 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.

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

    It landed in https://fortnow.com/lance/complog/archive/2004_03_21_archive.html#108004475815397466

    ReplyDelete
  3. I see the confusion.. I posted the correct link to the broken link in previous comment.

    ReplyDelete
    Replies
    1. Email 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.

      Delete
  4. Span-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