Talk:Interactive proof system

Untitled

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!

Bolding of abbreviations

I admit I know nothing about the subject of the article, but I think there may be a tad too many boldings in this article.--Rockfang (talk) 10:15, 26 July 2008 (UTC)

The lead forgets to explain...

The lead does not give enough context. Only after reading on I infer the following context, but I am not an expert.

Real machines can only produce text by following mechanical procedures, possibly involving random choices from finite sets, and otherwise relying on given inputs and built-in constants.

In the abstract machine of an interactive proof, the prover is trying to convince the verifier about a statement, and the question is if there are messages that the prover can supply to the verifier to convince it. In order to give a proof of anything, the proof must be found, provided it exists at all, and that may require a very long search. If the proof does not exist, a search for it may never end. We assume the prover is all-powerful in the sense that it is able to find a message that achieves the goal if such a message exists, and is able to avoid being stuck in an infinite search if the proof does not exist. In other words, we are not really concerned about how the prover works. We are studying the verifier. Cacadril (talk) 07:32, 22 April 2010 (UTC)

Origin year

The current article says, "Although NP may be viewed as using interaction, it wasn't until 1985 that the concept of computation through interaction was conceived by two independent groups of researchers." It is well known that Goldwasser-Micali-Rackoff existed by the middle of 1983; for instance, I heard their work expounded during lunches at the FCT'83 conference in late August in Borgholm, Sweden. It was rejected from three previous STOC/FOCS'es. Not sure how to revise the article, so I'll leave it as a discussion point. KWRegan (talk) 02:29, 23 June 2011 (UTC)