page_title: Complexity class
section_title: Interactive proof systems
hierarchical_section_title: Complexity class / Other models of computation / Interactive proof systems
context_page_description: In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
  In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems and using other models of computation.
  The study of the relationships between complexity classes is a major area of research in theoretical computer science. There are often general hierarchies of complexity classes; for example, it is known that a number of fundamental time and space complexity classes relate to each other in the following way: NLPNPPSPACEEXPTIMEEXPSPACE.
context_section_description: A number of complexity classes are defined using interactive proof systems. Interactive proofs generalize the proofs definition of the complexity class NP and yield insights into cryptography, approximation algorithms, and formal verification.
  Interactive proof systems are abstract machines that model computation as the exchange of messages between two parties: a prover  and a verifier . The parties interact by exchanging messages, and an input string is accepted by the system if the verifier decides to accept the input on the basis of the messages it has received from the prover. The prover  has unlimited computational power while the verifier has bounded computational power (the standard definition of interactive proof systems defines the verifier to be polynomially-time bounded). The prover, however, is untrustworthy (this prevents all languages from being trivially recognized by the proof system by having the computationally unbounded prover solve for whether a string is in a language and then sending a trustworthy "YES" or "NO" to the verifier), so the verifier must conduct an "interrogation" of the prover by "asking it" successive rounds of questions, accepting only if it develops a high degree of confidence that the string is in the language.
caption: General representation of an interactive proof protocol.