computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

, 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". In the

decision tree model In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of ''queries'' or ''tests'' that are done adaptively, so the outcome of the pre ...

of computation, certificate complexity is the minimum number of the

n

input variables of a

decision tree A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm that only contains condit ...

that need to be assigned a value in order to definitely establish the value of the

Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...

f

Use in definitions

The notion of certificate is used to define

semi-decidability In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Zeroth-order logic (propositional logic) is decidable, whereas first-order and higher-order logic are not. Logical systems ar ...

: a

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...

''L'' is semi-decidable if there is a two-place predicate

relation Relation or relations may refer to: General uses *International relations, the study of interconnection of politics, economics, and law on a global level *Interpersonal relationship, association or acquaintance between two or more people *Public ...

R ⊆ Σ∗ × Σ∗ such that R is

computable Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...

, and such that for all x ∈ Σ∗: 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 machine In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

s. A language ''L'' is in NP if and only if there exists a polynomial ''p'' and a

polynomial-time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

bounded

Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...

''M'' such that every word ''x'' 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''). The class

co-NP 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 is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...

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. 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.

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''). 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 = Show L ∈ NP. verifier: gets string c = , 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, <, x, w> ∈ L ⇔ there exists c <= a, w, ³ such that <, x, w, c> ∈ V ∈ P

References

External links

* {{Citation , last1 = Buhrman , first1=Harry , last2=de Wolf , first2=Ronald , title=Complexity Measures and Decision Tree Complexity:A Survey , year=2002.
Computational Complexity: a Modern Approach by Sanjeev Arora and Boaz Barak
Computational complexity theory

Use in definitions

Examples

See also

References

External links