Talk:Interactive proof system

From Wikipedia, the free encyclopedia
Jump to: navigation, search
          This article is of interest to the following WikiProjects:
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
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.
Mathematics rating:
Start Class
Mid Importance
 Field: Discrete mathematics
WikiProject Computer science (Rated Start-class, Mid-importance)
WikiProject icon 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.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 
WikiProject Cryptography / Computer science  (Rated Start-class, High-importance)
WikiProject icon 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.
Start-Class article Start  This article has been rated as Start-Class on the quality scale.
 High  This article has been rated as High-importance on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science (marked as High-importance).
 


Untitled[edit]

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[edit]

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...[edit]

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[edit]

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)