Talk:Interactive proof system

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Mid	This article has been rated as Mid-priority on the project's priority scale.

Computer science Mid‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Cryptography: Computer science High‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

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)[reply]

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)[reply]

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)[reply]

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)[reply]