Certificate (complexity) (original) (raw)
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 input variables of a decision tree that need to be assigned a value in order to definitely establish the value of the Boolean function .
| Property | Value |
|---|---|
| dbo:abstract | 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 input variables of a decision tree that need to be assigned a value in order to definitely establish the value of the Boolean function . (en) En informatique théorique, plus précisément en théorie de la complexité des algorithmes, un certificat est, de façon simplifiée, une information permettant de certifier que l'entrée est correcte. (fr) Na teoria da complexidade computacional, um certificado (também chamado de witness ou testemunha) é uma string que certifica a resposta a um cálculo, ou garante a relação de alguma string em um idioma. Um certificado é muitas vezes visto como um ramo de solução dentro de um processo de verificação, que é usado para verificar se um problema dá a resposta "Sim" ou "Não". No modelo de árvore de decisão da computação, a complexidade do certificado é o número mínimo de variáveis de entrada de uma árvore de decisão que precisam ser atribuído um valor, a fim de estabelecer definitivamente o valor da função booleana . (pt) У теорії складності обчислень, сертифікат (також називається ) певної задачі — це рядок, який підтверджує (засвідчує, сертифікує) розв'язок цієї задачі; тест, який перевіряє відповідь на цю задачу. Приклади * Задача. Чи вірно, що серед чисел (-2, -3, 15, 14, 7, -10, …) є такі, що їхня сума дорівнює 0? Відповідь: так. Сертифікат. -2 -3 + 15 -10 = 0. * Задача. Скільки існує варіантів розкладення числа у суму натуральних чисел. Відповідь: варіантів. Сертифікат: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1. * Задача. Знайти корені рівняння Відповідь 1. Сертифікат. Відомо, що , отже, Відповідь 2. Сертифікат. далі див. відповідь 1. (uk) |
| dbo:wikiPageExternalLink | http://www.cs.princeton.edu/theory/complexity/dectreechap.pdf |
| dbo:wikiPageID | 14933760 (xsd:integer) |
| dbo:wikiPageLength | 4708 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097816561 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:Nondeterministic_Turing_machine dbr:Relation_(mathematics) dbr:Decision_tree dbr:Decision_tree_model dbr:Independent_set_(graph_theory) dbr:Computability dbr:Co-NP dbr:NL_(complexity) dbr:Computational_complexity_theory dbr:Formal_language dbc:Computational_complexity_theory dbr:Witness_(mathematics) dbr:Boolean_function dbr:Turing_machine dbr:Polynomial-time dbr:Semi-decidability |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Reflist |
| dct:subject | dbc:Computational_complexity_theory |
| rdfs:comment | 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 input variables of a decision tree that need to be assigned a value in order to definitely establish the value of the Boolean function . (en) En informatique théorique, plus précisément en théorie de la complexité des algorithmes, un certificat est, de façon simplifiée, une information permettant de certifier que l'entrée est correcte. (fr) У теорії складності обчислень, сертифікат (також називається ) певної задачі — це рядок, який підтверджує (засвідчує, сертифікує) розв'язок цієї задачі; тест, який перевіряє відповідь на цю задачу. Приклади * Задача. Чи вірно, що серед чисел (-2, -3, 15, 14, 7, -10, …) є такі, що їхня сума дорівнює 0? Відповідь: так. Сертифікат. -2 -3 + 15 -10 = 0. * Задача. Скільки існує варіантів розкладення числа у суму натуральних чисел. Відповідь: варіантів. Сертифікат: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1. * Задача. Знайти корені рівняння Відповідь 1. Сертифікат. Відомо, що , отже, Відповідь 2. Сертифікат. далі див. відповідь 1. (uk) Na teoria da complexidade computacional, um certificado (também chamado de witness ou testemunha) é uma string que certifica a resposta a um cálculo, ou garante a relação de alguma string em um idioma. Um certificado é muitas vezes visto como um ramo de solução dentro de um processo de verificação, que é usado para verificar se um problema dá a resposta "Sim" ou "Não". (pt) |
| rdfs:label | Certificate (complexity) (en) Certificat (complexité) (fr) Certificado (complexidade) (pt) Сертифікат (складність обчислень) (uk) |
| owl:sameAs | freebase:Certificate (complexity) wikidata:Certificate (complexity) dbpedia-fr:Certificate (complexity) dbpedia-pt:Certificate (complexity) dbpedia-uk:Certificate (complexity) https://global.dbpedia.org/id/2jPry |
| prov:wasDerivedFrom | wikipedia-en:Certificate_(complexity)?oldid=1097816561&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Certificate_(complexity) |
| is dbo:wikiPageDisambiguates of | dbr:Certificate |
| is dbo:wikiPageRedirects of | dbr:Certificate_complexity dbr:Certificate_(math) dbr:Witness_(complexity) |
| is dbo:wikiPageWikiLink of | dbr:NP_(complexity) dbr:Decision_tree_model dbr:♯P dbr:QMA dbr:Co-NP dbr:NLTS_Conjecture dbr:NL_(complexity) dbr:Constructive_set_theory dbr:Complexity_class dbr:Probabilistically_checkable_proof dbr:Witness_(mathematics) dbr:Certificate dbr:Certificate_complexity dbr:Polynomial_creativity dbr:P_versus_NP_problem dbr:Certificate_(math) dbr:Witness_(complexity) |
| is foaf:primaryTopic of | wikipedia-en:Certificate_(complexity) |