From: kramsay@aol.commangled (Keith Ramsay)
Subject: Re: Checkable computations
Date: 16 Dec 2001 00:35:42 GMT
Newsgroups: sci.math
Summary: Categories of decision problems, including Interactive Proof Protocol

In article <1f4epus.18rof0m1bpy6awN%eijkhout@cs.utk.edu>,
eijkhout@cs.utk.edu (Victor Eijkhout) writes:
|Is there a branch of math / theory of computation that deals with the
|following: what computations can be checked easily whether the result is
|correct?

Yes, depending upon what sort of checking is involved, this may
correspond to what is called "nondeterminism", or a proof protocol,
in computing complexity.

The class P is the set of decision problems on strings (problems
whose instances are strings, and requiring a yes or no answer) that
can be solved in O(n^k) time for some k. The class NP is the set of
decision problems on strings where there's an answer (yes or no, with
evidence appended) that can be verified in O(n^k) time for some k, if
the answer is "yes". The corresponding class if we require a
verification if the answer is "no" is called "co-NP" (just reverse
the roles of "yes" and "no"). If you require both, then that's of
course "NP intersect co-NP".

|Example one way: solving a linear system Ax=b takes O(n^3) ops, checking
|Ax-b O(n^2).

So this is both in P and NP, of course, with different bounds.

|Example other way: traveling salesman problem. If you give me the
|solution I can not simply see whether you've given me indeed the
|minimum, or just something close to it. (Or can I?)

If all you are given is the solution, then no, you presumably can't
tell. There's a decision problem variation on it: given a network and
a bound, does there exist a route requiring less than the bound? That
variation is in NP, because a "yes" answer can always be validated in
such a way as to be checkable in polynomial time, just giving the
route.

The problems in NP that are "hardest", in the sense that all other
problems in NP can be reduced to them, are called "NP-complete", and
the travelling salesman problem in this decision form is NP-complete.
It's generally assumed that there aren't efficient algorithms for
NP-complete problems.

|Context: distributed computing. I give my computations to some remote
|machine and I don't know if I can trust that machine or the channels in
|between me and it.

In this case you may be also interested in interactive proof
protocols.

One of the famous results from a few years ago was an answer to the
following problem. Suppose that you have a genuine random number
generator, and are in contact with someone having unlimited computing
power. For what class of decision problems can they demonstrate the
answers to you, interactively, within a polynomial time bound? The
idea is that you get to query them repeatedly, using your random
number generator to make your questions unpredictable, and then check
whether their answers are consistent. A protocol is considered working
if you can ensure with high probability that they don't trick you.
That class was being denoted "IP".

The answer was somewhat of a surprise; any decision problem for which
there's a solution algorithm needing only polynomial-bounded storage
space has an interactive proof protocol (IP=PSPACE). So if some
powerful alien (who you are sure isn't able to control your random
number generator) claims to you to know how to play a perfect chess
game, there's a protocol for you to put their claim to the test, and
enable them to provide suitable evidence as to what optimal moves in
various positions are, without yourself having to be exceptionally
good at chess.

For P and NP, a standard reference is a book by Garey and Johnson. For
the interactive proof protocols, I don't have any references handy,
but you might look for references to "zero knowledge proofs" and
related topics in computing complexity.

Keith Ramsay