Certificate (complexity)

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

In the decision tree model of computation, certificate complexity is the minimum number of the n input variables of a decision tree that need to be assigned a value in order to definitely establish the value of the Boolean function f.

References

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

P ≟ NP

This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Computational complexity theory Theoretical computer science stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем написать реферат Francis Blondet Pascale Paradis Look at other dictionaries: Certificate — may refer to: Public key certificate, an electronic document used in cryptography Certificate of deposit, or CD, a financial product commonly offered to consumers by banks, thrift institutions, and credit unions Certificate (complexity), a string …   Wikipedia Certificate of pharmaceutical product — The certificate of pharmaceutical product (abbreviated: CPP or CoPP) is a certificate issued in the format recommended by the World Health Organization (WHO), which establishes the status of the pharmaceutical product and of the applicant for… …   Wikipedia NP (complexity) — Diagram of complexity classes provided that P ≠ NP. The existence of problems outside both P and NP complete in this case was established by Ladner.[1] In computational complexity theory, NP is one of the most fundamental complexity classes. The… …   Wikipedia Online Certificate Status Protocol — The Online Certificate Status Protocol (OCSP) is an Internet protocol used for obtaining the revocation status of an X.509 digital certificate. It is described in RFC 2560 and is on the Internet standards track. It was created as an alternative… …   Wikipedia Tasmanian Certificate of Education — The Tasmanian Certificate of Education, or TCE, is the main credential awarded to secondary school students who successfully complete senior high school level studies (years 11 and 12 or equivalent) in Tasmania, Australia. It was introduced in… …   Wikipedia UP (complexity) — In complexity theory, UP ( Unambiguous Non deterministic Polynomial time ) is the complexity class of decision problems solvable in polynomial time on a non deterministic Turing machine with at most one accepting path for each input. UP contains… …   Wikipedia Decision tree model — In computational complexity and communication complexity theories the decision tree model is the model of computation or communication in which an algorithm or communication process is considered to be basically a decision tree, i.e., a sequence… …   Wikipedia Interactive proof system — In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to… …   Wikipedia P = NP problem — The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field – the Clay Mathematics Institute has offered a $1 million US prize… …   Wikipedia P versus NP problem — Unsolved problems in computer science Is P = NP ? …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”