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,- If P(x)≠L(x) then with high probability M
^{P}(x) outputs "P incorrectly computes x on some input", and - If P=L then with high probability M
^{P}(x) outputs "P(x)=L(x)".

^{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

- L is checkable.
- Both L and L have FRIPs.

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

_{k}P 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.

--

Posted by Lance Fortnow to My Computational Complexity Web Log at 3/23/2004 06:25:58 AM- If P(x)≠L(x) then with high probability M