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 .
| Attributes | Values |
|---|
| rdfs:label
| - Certificate (complexity) (en)
- Certificat (complexité) (fr)
- Certificado (complexidade) (pt)
- Сертифікат (складність обчислень) (uk)
|
| 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)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has 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)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)