{"history":[],"article":{"id":"c81b1e77-2270-43b1-8aed-33478a408a7d","title":"Certificate (complexity)","slug":"certificate-complexity","content":":::summary\n:::\n\n# \nIn [computational complexity theory](https://bliptext.com/articles/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.\nA 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\".\nIn the [decision tree model](https://bliptext.com/articles/decision-tree-model) of computation, certificate complexity is the minimum number of the n input variables of a [decision tree](https://bliptext.com/articles/decision-tree) that need to be assigned a value in order to definitely establish the value of the [Boolean function](https://bliptext.com/articles/boolean-function) f.\n\n# Use in definitions\nThe notion of certificate is used to define [semi-decidability](https://bliptext.com/articles/semi-decidability): a [formal language](https://bliptext.com/articles/formal-language) L is semi-decidable if there is a two-place predicate [relation](https://bliptext.com/articles/relation-mathematics) such that R is [computable](https://bliptext.com/articles/computability), and such that for all :\nx ∈ L ⇔ there exists y such that R(x, y)\nCertificates also give definitions for some complexity classes which can alternatively be characterised in terms of [nondeterministic Turing machines](https://bliptext.com/articles/nondeterministic-turing-machine).\nA language L is in **[NP](https://bliptext.com/articles/np-complexity)** if and only if there exists a polynomial p and a [polynomial-time](https://bliptext.com/articles/polynomial-time) bounded [Turing machine](https://bliptext.com/articles/turing-machine) M such that every word 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).\nThe class **[co-NP](https://bliptext.com/articles/co-np)** has a similar definition, except that there are certificates for the words not in the language.\nThe class **[NL](https://bliptext.com/articles/nl-complexity)** 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.\nAlternatively, 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.\n\n# Examples\nThe problem of determining, for a given graph G and number k, if the graph contains an [independent set](https://bliptext.com/articles/independent-set-graph-theory) of size k is in **NP**.\nGiven 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).\nA 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:\nL = {<, x, w> | does accept x in |w| steps?}\nShow L ∈ NP.\n**verifier:**\ngets string c = , x, w such that |c| <= P(|w|)\ncheck if c is an accepting computation of M on x with at most |w| steps\n|c| <= O(|w|3)\nif we have a computation of a TM with k steps the total size of the computation string is k2 Thus, <, x, w> ∈ L ⇔ there exists c <= a|w|3 such that <, x, w, c> ∈ V ∈ P","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T10:19:44.267Z","updated_at":"2025-01-26T10:19:44.267Z","search_vector":"'certif':1 'complex':2","search_content":" \n \n\n# \nIn [computational complexity theory](https://bliptext.com/articles/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.\nA 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\".\nIn the [[decision tree](https://bliptext.com/articles/decision-tree) model](https://bliptext.com/articles/decision-tree-model) of computation, certificate complexity is the minimum number of the n input variables of a [decision tree](https://bliptext.com/articles/decision-tree) that need to be assigned a value in order to definitely establish the value of the [Boolean function](https://bliptext.com/articles/boolean-function) f.\n\n# Use in definitions\nThe notion of certificate is used to define [semi-decidability](https://bliptext.com/articles/semi-decidability): a [formal language](https://bliptext.com/articles/formal-language) L is semi-decidable if there is a two-place predicate [relation](https://bliptext.com/articles/relation-mathematics) such that R is [computable](https://bliptext.com/articles/computability), and such that for all :\nx ∈ L ⇔ there exists y such that R(x, y)\nCertificates also give definitions for some complexity classes which can alternatively be characterised in terms of [nondeterministic Turing machines](https://bliptext.com/articles/nondeterministic-turing-machine).\nA language L is in **[NP](https://bliptext.com/articles/np-complexity)** if and only if there exists a polynomial p and a [polynomial-time](https://bliptext.com/articles/polynomial-time) bounded [Turing machine](https://bliptext.com/articles/turing-machine) M such that every word 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).\nThe class **[co-NP](https://bliptext.com/articles/co-np)** has a similar definition, except that there are certificates for the words not in the language.\nThe class **[NL](https://bliptext.com/articles/nl-complexity)** 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.\nAlternatively, 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.\n\n# Examples\nThe problem of determining, for a given graph G and number k, if the graph contains an [independent set](https://bliptext.com/articles/independent-set-graph-theory) of size k is in **NP**.\nGiven 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).\nA 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:\nL = { , x, w> | does accept x in |w| steps?}\nShow L ∈ NP.\n**verifier:**\ngets string c = , x, w such that |c| , x, w> ∈ L ⇔ there exists c , x, w, c> ∈ V ∈ P","revisionCount":0},"hasMore":false,"nextCursor":null}

History