Certificate (complexity)

Last updated December 06, 2024

In computational complexity theory, a certificate (also called a witness) is a string that certifies the answer to a computation, or certifies the membership of some string in a language. A certificate is often thought of as a solution path within a verification process, which is used to check whether a problem gives the answer "Yes" or "No".

Use in definitions

The notion of certificate is used to define semi-decidability:^[1] a formal language $L$ is semi-decidable if there is a two-place predicate relation $R\subseteq \Sigma ^{*}\times \Sigma ^{*}$ such that $R$ is computable, and such that for all $x\in \Sigma ^{*}$ :

   x ∈ L ⇔ there exists y such that R(x, y)

Certificates also give definitions for some complexity classes which can alternatively be characterised in terms of nondeterministic Turing machines. A language $L$ is in NP if and only if there exists a polynomial $p$ and a polynomial-time bounded Turing machine $M$ such that every word $x\in \Sigma ^{*}$ is in the language $L$ precisely if there exists a certificate $c$ of length at most $p(|x|)$ such that $M$ accepts the pair $(x,c)$ .^[2] The class co-NP has a similar definition, except that there are certificates for the words not in the language.

The class NL has a certificate definition: a problem in the language has a certificate of polynomial length, which can be verified by a deterministic logarithmic-space bounded Turing machine that can read each bit of the certificate once only.^[3] Alternatively, the deterministic logarithmic-space Turing machine in the statement above can be replaced by a bounded-error probabilistic constant-space Turing machine that is allowed to use only a constant number of random bits.^[4]

Examples

The problem of determining, for a given graph $G$ and number $k$ , if the graph contains an independent set of size $k$ is in NP. Given a pair $(G,k)$ in the language, a certificate is a set of $k$ vertices which are pairwise not adjacent (and hence are an independent set of size $k$ ).^[5]

A more general example, for the problem of determining if a given Turing machine accepts an input in a certain number of steps, is as follows:

 L = {<<M>, x, w> | does <M> accept x in |w| steps?}  Show L ∈ NP.  verifier:    gets string c = <M>, x, w such that |c| <= P(|w|)    check if c is an accepting computation of M on x with at most |w| steps    |c| <= O(|w|³)    if we have a computation of a TM with k steps the total size of the computation string is k²    Thus, <<M>, x, w> ∈ L ⇔ there exists c <= a|w|³ such that <<M>, x, w, c> ∈ V ∈ P

Related Research Articles

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and only if for every no-instance we have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate.

In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete.

<span class="mw-page-title-main">PSPACE</span> Set of decision problems

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover is assumed to possess unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can—unlike a deterministic Turing Machine—have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution.

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 computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof, as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way.

In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any function $,$

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm.

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.

In computational complexity theory, an Arthur–Merlin protocol, introduced by Babai (1985), is an interactive proof system in which the verifier's coin tosses are constrained to be public. Goldwasser & Sipser (1986) proved that all (formal) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins.

In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time $.$

In computational complexity theory, NL is the complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.

In computational complexity theory, L is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space. Formally, the Turing machine has two tapes, one of which encodes the input and can only be read, whereas the other tape has logarithmic size but can be read as well as written. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of Boolean flags, and many basic logspace algorithms use the memory in this way.

In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size. These two different definitions make P/poly central to circuit complexity and non-uniform complexity.

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length.

In computational complexity theory, the padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal.

References

↑ Cook, Stephen. "Computability and Noncomputability" (PDF). Retrieved 7 February 2013.
↑ Arora, Sanjeev; Barak, Boaz (2009). "Definition 2.1". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
↑ Arora, Sanjeev; Barak, Boaz (2009). "Definition 4.19". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
↑ A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness," Logical Methods in Computer Science, Vol. 10(3:6)2014, pp. 1-17.
↑ Arora, Sanjeev; Barak, Boaz (2009). "Example 2.2". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

External links

Buhrman, Harry; de Wolf, Ronald (2002), Complexity Measures and Decision Tree Complexity:A Survey.
Computational Complexity: a Modern Approach by Sanjeev Arora and Boaz Barak

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Cook, Stephen. "Computability and Noncomputability" (PDF). Retrieved 7 February 2013.

[2] Arora, Sanjeev; Barak, Boaz (2009). "Definition 2.1". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

[3] Arora, Sanjeev; Barak, Boaz (2009). "Definition 4.19". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

[4] A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness," Logical Methods in Computer Science, Vol. 10(3:6)2014, pp. 1-17.

[5] Arora, Sanjeev; Barak, Boaz (2009). "Example 2.2". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

[1]

[2]

[3]

[4]

[5]