Computational Complexity

Tuesday, March 23, 2004

 
Is Satisfiability Checkable?

Posted by Lance

Time for another of my favorite open questions: Is Boolean Formula Satisfiability (SAT) checkable?

The best notion of program checking comes from a paper by Manuel Blum and Sampath Kannan. Let P be a program claiming to compute a language L. A program checker M for L is a probabilistic polynomial-time Turing machine with access to P as an oracle that outputs either "P(x)=L(X)" or "P incorrectly computes x on some input."

We say L is checkable if for all oracle P and inputs x,

1. If P(x)≠L(x) then with high probability M^P(x) outputs "P incorrectly computes x on some input", and
2. If P=L then with high probability M^P(x) outputs "P(x)=L(x)".

If P is correct on x and incorrect somewhere else, M^P(x) can output either answer.

Blum and Kannan show a nice connection to interactive proofs. We say a language L has a function-restricted interactive proof (FRIP) if there is a PCP for L where the proof for x in L is computable with an oracle for L. We have the following equivalence for all languages L

1. L is checkable.
2. Both L and L have FRIPs.

Checkable languages include Graph Isomorphism, the Permanent and all of the PSPACE-complete and EXP-complete sets.

Back to whether SAT is checkable. SAT has a FRIP by using self-reduction. So whether SAT is checkable is equivalent to whether SAT has a FRIP.

All of the known PCPs for SAT seem to require counting, a prover hard for #P or at least Mod_kP for some k. Whether one can find a PCP for SAT that is even in the polynomial-time hierarchy remains open.

Perhaps one can show some consequence of the checkability of SAT perhaps that the polynomial-time hierarchy collapses. Bogdanov and Trevisan have the best result in this direction; they show that if SAT has a non-adaptive self-corrector then PH collapses to third level. Though many checking results use self-correction there still could be some completely different way to show SAT is checkable.

6:25 AM # 0 comments

Comment Feeds: This Post All