| rdfs:comment
| - في علم التعقيد الحسابي co-NP هي المجموعة المُكملة ل-NP أي: co-NP={0,1}* \ NP . (ar)
- In der Komplexitätstheorie bezeichnet Co-NP eine Komplexitätsklasse. In ihr sind genau die Sprachen enthalten, deren Komplement in der Klasse NP liegt. Die Klasse Co-NP besteht demnach aus den Sprachen, für die ein Beweis, dass ein Wort nicht zur Sprache gehört, in Polynomialzeit durch eine nichtdeterministische Turingmaschine überprüft werden kann. (de)
- En informatique théorique, co-NP (ou coNP) est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision au sens de la théorie de la complexité. C'est la classe complémentaire (au sens de la complexité) de la classe NP. (fr)
- co-NPとは計算量理論における問題クラスの一つである。 (ja)
- Klasa Co-NP – klasa złożoności dopełniająca dla problemów decyzyjnych NP. Przykładowo dopełnieniem problemu typu „czy wszystkie elementy zbioru X spełniają warunek Y” jest „czy istnieje element zbioru X niespełniający warunku Y”. Nie wiadomo czy dopełnienie każdego problemu NP jest NP. Wydaje się bowiem, że czasem łatwiej pokazywać kontrprzykłady (weryfikować negatywnie) niż udowodnić prawdziwość jakiegoś twierdzenia (weryfikować pozytywnie). Wykazano, że jeżeli NP ≠ Co-NP, to P ≠ NP. Jednak implikacja w drugą stronę nie została udowodniona. (pl)
- В теории алгоритмов часто рассматривается класс, тесно связанный с P и NP, — класс дополнений языков из NP, называемый co-NP. (ru)
- 在計算複雜度理論上，反NP類是複雜度類的其中一類。 (zh)
- En complexitat computacional, co-NP és la classe de complexitat que conté els problemes de decisió complementaris de la classe NP. Per problema complementari s'entén aquell que te les respostes invertides. També es pot dir que els la classe co-NP és el conjunt de problemes de decisió que una màquina de Turing no determinista respon «no» (o rebutja) en un temps polinòmic. (ca)
- 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 X is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely if only no-instances have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate. (en)
- En teoría de la complejidad computacional, la clase de complejidad co-NP es el conjunto de los problemas de decisión complementarios a los de la clase NP. Por problema complementario se entiende aquel que cuyas respuestas positiva o negativa están invertidas. La clase de complejidad P es un subconjunto tanto de NP como de co-NP y se piensa que la inclusión es estricta en ambos casos. Se piensa también que NP y co-NP son diferentes. De ser cierto esto, ningún problema de NP-completo podría estar en co-NP y ningún problema de co-NP-completo podría estar en NP.
* Datos: Q955748 (es)
- Nella teoria della complessità computazionale, è la classe di problemi complementari a quelli della classe . In maniera più formale si ha che se è un problema su un alfabeto allora esso è un problema della classe se e solo se è un problema di classe . Per quanto riguarda l'uguaglianza non ci si può esprimere. Ecco perché non si può dire nulla a proposito dell'uguaglianza ed . (it)
- 계산 복잡도 이론에서 co-NP는 복잡도 종류이다. 문제 가 co-NP에 들어 있다는 것은 그 문제인 가 NP에 속한다는 것과 동치이다. 간단히 말하면, co-NP는 아니오 보기(반례라고도 한다)에 대해 효율적으로 검증할 수 있는 증명이 있는 문제의 집합이다. NP-완전 문제 중 부분집합 합 문제가 있다. 이 문제는 정수 유한집합이 있을 때, 이 집합의 공집합이 아닌 부분집합 중 원소를 다 더하면 0이 되는 것이 있는지를 묻는 문제이다. 이 문제의 보완 문제는 co-NP에 들어가는데, 정수 유한집합이 주어질 때, 공집합이 아닌 부분집합은 모두, 원소를 다 더했을 때 0이 아닌지를 묻는 문제가 된다. "아니오" 보기에 대한 증명을 하려면, 합이 0이 되고 공집합이 아닌 부분집합을 찾아야 한다. 그렇게 하면 이 증명은 검증하기 쉬워진다. 어떤 문제가 NP와 co-NP 둘 다 된다는 것을 보였다면, 이는 그 문제가 NP-완전이 아닐 것이라는 강력한 증거가 된다. (NP-완전이라면 NP = co-NP이기 때문) (ko)
- Na Teoria da complexidade, co-NP é uma Classe de complexidade. Um problema é membro de co-NP se e somente se seu complemento esta na classe de complexidade NP. Em outras palavras, co-NP é a classe de problemas para qual existe a prova, de forma eficiente, para não existência de instância, os chamados contra-exemplos. Se um problema pode ser apresentado com sendo tanto em NP quanto em co-NP, isso serve de evidência de que esse problema provavelmente não é NP-completo,caso contrário NP = co-NP. (pt)
- В теорії складності обчислень, co-NP — клас складності. Задача належить класу co-NP тоді і тільки тоді, коли компланарна до неї задача належить класу NP. Неформально, co-NP — клас задач, для яких існують ефективні (поліноміальної складності) перевірювачі для відповіді «Ні». (uk)
|
| has abstract
| - En complexitat computacional, co-NP és la classe de complexitat que conté els problemes de decisió complementaris de la classe NP. Per problema complementari s'entén aquell que te les respostes invertides. També es pot dir que els la classe co-NP és el conjunt de problemes de decisió que una màquina de Turing no determinista respon «no» (o rebutja) en un temps polinòmic. La classe de complexitat P és un subconjunt tant de NP com de co-NP i es pensa que la inclusió és estricta en tots dos casos. Es pensa també que NP i co-NP son diferents. Si això fos cert, cap problema NP-complet podria estar a co-NP i cap problema de co-NP-complet podria estar a NP. Un exemple de problema que se sap que és NP i co-NP és la factorització d'enters: donat dos nombres positius i enters m i n determinar si m té un factor menor que n i més gran que 1. Que pertany a NP és clar: si m te dit factor, llavors el propi factor és un certificat. Que pertanyi a la classe co-NP és també evident: es pot obtenir la llista de factors primers de m, tots més grans o iguals a n, que el verificador pot comprovar si és vàlid per multiplicacions i el . No es coneix cap algorisme per factoritzar en temps polinòmic, i per tant se sap que aquest problema està a NP i co-NP però no se sap si està també a P. (ca)
- في علم التعقيد الحسابي co-NP هي المجموعة المُكملة ل-NP أي: co-NP={0,1}* \ NP . (ar)
- In der Komplexitätstheorie bezeichnet Co-NP eine Komplexitätsklasse. In ihr sind genau die Sprachen enthalten, deren Komplement in der Klasse NP liegt. Die Klasse Co-NP besteht demnach aus den Sprachen, für die ein Beweis, dass ein Wort nicht zur Sprache gehört, in Polynomialzeit durch eine nichtdeterministische Turingmaschine überprüft werden kann. (de)
|
![[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)