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.

## No comments:

## Post a Comment