Recently, I have been thinking on-and-off about the following problem and variants thereof. Fix a function . When is it easier to verify that a pair satisfies then to compute from scratch? (One can always verify by computing , so it can never be harder.) Without being given any additional information along with , verification can never be much easier than computation (proof: given a verification procedure we can compute as follows: if then output 0, else output 1), so to make things interesting we allow verification to additionally take as input a “proof string” .
Let’s define what we want more formally. There are various possibilities here, but to keep things clean let’s say we want an algorithm such that:
- For all there exists a such that .
- For all and all , we have .
The reader can easily see that this is nothing more than a question about when non-deterministic computation is “better” than deterministic computation. Assuming , there are several interesting functions (e.g., the characteristic function for 3SAT) for which verification is faster than computation.
All very well and good, but here are some things I really want to know:
- For what functions can we prove, without assumptions, that verification is “better” than computation?
- Even allowing reasonable complexity-theoretic assumptions, is verification faster than computation for every poly-time computable function ? For a concrete question, is for every ?
Related to the first question, Lance has a recent post that shows, in particular, that any function in can be verified by an verifier. Rather than reduce to 3SAT, let’s prove this directly. Fix a function and a machine that computes it. Given an input , the proof will be the complete tableau of ‘s computation on the input . A tableau can be checked for correctness by some polynomial number of local computations, each looking at only a constant number of bits. An unbounded fan-in AND gate at the bottom can thus be used to express correctness of all the local checks.
Since parity is in but not in , this gives a provable example of where verification is easier than computation.
What’s the crypto connection? Well, say we have a low-power clinet that wants to compute . One thing it can do is to outsource computation of to a more-powerful server. But since the client may not trust the server, it will also request the server to provide proof that the computation was done correctly. Of course ,we would like the process of verification to be cheaper than simply having the client compute itself.