Talk:Interactive proof system

From Wikipedia, the free encyclopedia

Hmmm. I'm certainly not an expert in computational complexity theory, but I'm unfamiliar with this idea, and the article at the moment sounds overly enthusiastic.

Could we have full references for the papers you mention, so I can check where else they have been cited? Has the concept been used to prove anything else of interest? --Robert Merkel 04:58, 30 Jul 2003 (UTC)

OK, it's real, and there are papers in the area. Still not sure how important it is, though. --Robert Merkel 05:02, 30 Jul 2003 (UTC)

It's responsible for at least two of the most important theorems in complexity theory, the IP=PSPACE theorem and the PCP Theorem. Both of these are widely cited and held in high regard because of their difficulty, how surprising they are, and how they link interactive proof systems together with traditional machines. They've also been valuable in proving other things like the lower bounds on approximation algorithms. This stuff should be covered in any second-semester course on complexity, at least in passing. I provided 10 references, most of which have received many hundreds of citations and are seminal works. Some you can read for free, have a look. Deco 09:26, 27 May 2005 (UTC)

If that still matters, it's a fairly popular concept in complexity theory. You can look the references up in, for example, this survey and they get cited a lot (hundreds of citations for each of them). Andris 20:49, May 19, 2004 (UTC)

My written english is not so well, but there is no Entry in German for this one, so I strived through the english version. You should Include a remarkt that class IP and PSPACE are equivalent!