This HTML5 document contains 114 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-cahttp://ca.dbpedia.org/resource/
dbpedia-kohttp://ko.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
n32https://global.dbpedia.org/id/
dbpedia-hehttp://he.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
dbpedia-arhttp://ar.dbpedia.org/resource/
owlhttp://www.w3.org/2002/07/owl#
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-vihttp://vi.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbr:Co-NP
rdf:type
yago:State100024720 yago:Condition113920835 yago:WikicatUnsolvedProblemsInComputerScience yago:Abstraction100002137 yago:Problem114410605 yago:Difficulty114408086 yago:Collection107951464 yago:WikicatComplexityClasses yago:Attribute100024264 yago:Group100031264 yago:Class107997703
rdfs:label
Co-NP Co-NP Co-NP Co-NP Co-NP Co-NP Co-NP (Complexitat) Co-NP Клас складності co-NP 反NP كو-إن بي Klasa Co-NP Класс co-NP Co-NP
rdfs:comment
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. 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. В теорії складності обчислень, co-NP — клас складності. Задача належить класу co-NP тоді і тільки тоді, коли компланарна до неї задача належить класу NP. Неформально, co-NP — клас задач, для яких існують ефективні (поліноміальної складності) перевірювачі для відповіді «Ні». 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. 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. في علم التعقيد الحسابي co-NP هي المجموعة المُكملة ل-NP أي: co-NP={0,1}* \ NP . 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 . 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. co-NPとは計算量理論における問題クラスの一つである。 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. В теории алгоритмов часто рассматривается класс, тесно связанный с P и NP, — класс дополнений языков из NP, называемый co-NP. 在計算複雜度理論上，反NP類是複雜度類的其中一類。 계산 복잡도 이론에서 co-NP는 복잡도 종류이다. 문제 가 co-NP에 들어 있다는 것은 그 문제인 가 NP에 속한다는 것과 동치이다. 간단히 말하면, co-NP는 아니오 보기(반례라고도 한다)에 대해 효율적으로 검증할 수 있는 증명이 있는 문제의 집합이다. NP-완전 문제 중 부분집합 합 문제가 있다. 이 문제는 정수 유한집합이 있을 때, 이 집합의 공집합이 아닌 부분집합 중 원소를 다 더하면 0이 되는 것이 있는지를 묻는 문제이다. 이 문제의 보완 문제는 co-NP에 들어가는데, 정수 유한집합이 주어질 때, 공집합이 아닌 부분집합은 모두, 원소를 다 더했을 때 0이 아닌지를 묻는 문제가 된다. "아니오" 보기에 대한 증명을 하려면, 합이 0이 되고 공집합이 아닌 부분집합을 찾아야 한다. 그렇게 하면 이 증명은 검증하기 쉬워진다. 어떤 문제가 NP와 co-NP 둘 다 된다는 것을 보였다면, 이는 그 문제가 NP-완전이 아닐 것이라는 강력한 증거가 된다. (NP-완전이라면 NP = co-NP이기 때문) 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
dcterms:subject
dbc:Complexity_classes
dbo:wikiPageID
6184
dbo:wikiPageRevisionID
1069392707
dbo:wikiPageWikiLink
dbr:Complexity_class dbr:Turing_machine dbr:Boolean_satisfiability_problem dbr:Decision_problem dbr:Polynomial-time_reduction dbr:Co-NP-complete dbr:NP_(complexity) dbr:Computational_complexity_theory dbr:Non-deterministic_Turing_machine dbr:Complement_(complexity) dbr:Integer_factorization dbr:P_(complexity) dbr:Propositional_logic dbr:Tautology_(logic) dbr:Certificate_(complexity) dbr:AKS_primality_test dbr:NP-complete dbc:Complexity_classes
owl:sameAs
dbpedia-pl:Klasa_Co-NP wikidata:Q955748 dbpedia-uk:Клас_складності_co-NP yago-res:Co-NP dbpedia-fr:Co-NP dbpedia-ar:كو-إن_بي dbpedia-vi:Co-NP dbpedia-sr:Co-NP dbpedia-zh:反NP dbpedia-it:Co-NP freebase:m.01v72 dbpedia-he:Co-NP dbpedia-pt:Co-NP dbpedia-es:Co-NP dbpedia-ja:Co-NP dbpedia-ko:Co-NP dbpedia-ru:Класс_co-NP dbpedia-ca:Co-NP_(Complexitat) n32:56MV4 dbpedia-de:Co-NP
dbp:wikiPageUsesTemplate
dbt:Tmath dbt:Main dbt:Lowercase dbt:Clarify dbt:Overline dbt:Expand_section dbt:Reflist dbt:Cn dbt:ComplexityClasses dbt:CZoo dbt:Citation_needed dbt:Mathcal dbt:Further dbt:Unsolved
dbp:with
examples of duals for decision/optimization problems in NP and co-NP
dbp:date
June 2021
dbp:reason
how complex is such a certificate?
dbo:abstract
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. في علم التعقيد الحسابي co-NP هي المجموعة المُكملة ل-NP أي: co-NP={0,1}* \ NP . 在計算複雜度理論上，反NP類是複雜度類的其中一類。 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. В теорії складності обчислень, co-NP — клас складності. Задача належить класу co-NP тоді і тільки тоді, коли компланарна до неї задача належить класу NP. Неформально, co-NP — клас задач, для яких існують ефективні (поліноміальної складності) перевірювачі для відповіді «Ні». Візьмемо приклад NP-повної задачі про суму підмножин: «Дана скінченна множина цілих чисел. Чи є у неї хоч одна непорожня підмножина, сума елементів якої рівна нулю?» Комланарною до цієї задачі буде така: «Дана скінченна множина цілих чисел. Чи кожна непорожня має ненульову суму елементів?» Щоб довести відповідь «Ні», маємо надати якусь непорожню підмножину, сума елементів якої рівна нулю. Таке доведення легко перевірити за поліноміальний час. P, клас задач, розв'язних за поліноміальний час, є підмножиною як NP, так і co-NP.NP і co-NP вважаються (хоч це не доведено) нерівними. Якщо для якої-небудь NP-повної задачі довести, що вона належить класу co-NP, то це означало б рівність цих класів. Оскільки будь-яка NP-задача (за означенням) зводиться до NP-повної за поліноміальний час.Задача, що належить як до NP, так і до co-NP, досить ймовірно(за припущенням про нерівність цих класів) не є NP-повною. Прикладом задачі, що належить як до NP, так і до co-NP, є факторизація числа: "дано натуральні числа m та n. Визначити, чи m має простий дільник, менший за n. Належність до NP очевидна: якщо m має такий дільник, то він і є підтвердженням відповіді. Доведення належності до co-NP складніше: для перевірки відповіді маємо перелічити прості дільники m та довести для кожного, що він є простим. Інша задача з перетину NP ∩ co-NP — перевірка чи є число простим. co-NPとは計算量理論における問題クラスの一つである。 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. Esto se demuestra como sigue: Si hubiera un problema en NP-completo y en co-NP al mismo tiempo, todo problema de NP se reduciría en él, se deduce que para todo problema en NP se podría construir una máquina de Turing no determinista que decidiera el problema complementario en tiempo polinómico, es decir, NP sería un subconjunto de co-NP y, por tanto los complementos de NP serían subconjunto de los complementos de co-NP, es decir, co-NP sería un subconjunto de NP, Por tanto NP y co-NP serían el mismo conjunto. De forma simétrica se demuestra que ningún problema en co-NP-completo puede estar en NP. * Datos: Q955748 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. Infatti per vedere se un certo input sia tale da essere di o di non esserlo si dovrebbe attendere che tutte le possibili computazioni della macchina di Turing non deterministica che accetta facciano il loro corso; ossia per avere la certezza che nessuna computazione si dovrebbe arrestare mentre se allora almeno una di tali computazioni si dovrebbe arrestare.Per far ciò non si impiega però un tempo polinomiale. Ecco perché non si può dire nulla a proposito dell'uguaglianza ed . 계산 복잡도 이론에서 co-NP는 복잡도 종류이다. 문제 가 co-NP에 들어 있다는 것은 그 문제인 가 NP에 속한다는 것과 동치이다. 간단히 말하면, co-NP는 아니오 보기(반례라고도 한다)에 대해 효율적으로 검증할 수 있는 증명이 있는 문제의 집합이다. NP-완전 문제 중 부분집합 합 문제가 있다. 이 문제는 정수 유한집합이 있을 때, 이 집합의 공집합이 아닌 부분집합 중 원소를 다 더하면 0이 되는 것이 있는지를 묻는 문제이다. 이 문제의 보완 문제는 co-NP에 들어가는데, 정수 유한집합이 주어질 때, 공집합이 아닌 부분집합은 모두, 원소를 다 더했을 때 0이 아닌지를 묻는 문제가 된다. "아니오" 보기에 대한 증명을 하려면, 합이 0이 되고 공집합이 아닌 부분집합을 찾아야 한다. 그렇게 하면 이 증명은 검증하기 쉬워진다. 다항 시간에 풀 수 있는 문제인 P는 NP와 co-NP 모두의 부분집합이다. P는 두 경우 모두 진부분집합일 것으로 추측하고 있다. (한쪽만 진부분집합이고, 다른 쪽은 아닌 경우는 불가능함을 보일 수 있다.) NP와 co-NP 역시, 같은 집합이 아닐 것이다. 만약 그렇지 않다면, NP-완전 문제가 co-NP에 들어갈 수 있고, co-NP-완전 문제가 NP에 들어갈 수 있기 때문이다. 이는 다음과 같이 보일 수 있다. co-NP에 들어가는 NP-완전 문제가 있다고 하자. 모든 NP 문제는 이 문제로 환산할 수 있기 때문에, 각 NP문제에 대해서 그 보완 문제를 다항 시간에 판정할 수 있는 비결정적인 튜링 기계를 만들 수 있다. 다시 말해서, NP가 co-NP의 부분집합이 된다. 따라서 NP 문제의 보완을 모은 집합이 co-NP 문제의 보완을 모은 집합의 부분집합이 된다. 곧, co-NP가 NP의 부분집합이 된다. 앞에서 NP가 co-NP의 부분집합임을 보였으므로, 이는 두 집합이 같다는 뜻이 된다. co-NP-완전 문제가 NP일 수 없음을 보이는 증명은 이 증명과 대칭을 이룬다. 어떤 문제가 NP와 co-NP 둘 다 된다는 것을 보였다면, 이는 그 문제가 NP-완전이 아닐 것이라는 강력한 증거가 된다. (NP-완전이라면 NP = co-NP이기 때문) 정수의 소인수 분해 문제는 NP와 co-NP에 모두 들어가는, 유명한 문제이다. 양의 정수 m과 n이 있을 때 m에 n보다 작고 1보다 큰 약수가 있는지를 묻는다. 있는 경우를 보이는 쪽은 쉽다. m에 그런 약수가 있다면, 그 약수로 나누어 보면 된다. 반대쪽은 좀 어려운데, 그런 약수가 없다는 것을 보이려면 일일이 나누어 보아야 한다. 소인수 분해 문제를 소수 문제와 헷갈리는 사람이 많다. 소수 문제도 소인수 분해 문제처럼 NP와 co-NP 둘 다에 들어간다. 그러나 아직 확실치 않은 소인수 분해와는 달리, 소수 문제는 P이다. 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. Um exemplo de um problema NP-Completo é o Problema da soma dos subconjuntos: dado um conjunto finito de números inteiros, existe um subconjunto não vazio cuja soma é zero? Para dar a prova de que existe uma instância, primeiro é necessário especificar um subconjunto não vazio que tenha como soma zero. O problema complementar esta em co-NP e pergunta: "dado um conjunto finito de inteiros, cada um dos subconjuntos não tem soma zero?". Para provar a não existência de uma instância você precisa especificar um subconjunto não vazio que tenha soma zero, que é facilmente verificável.P, a classe dos problemas resolvíveis em tempo polinomial, é um subconjunto de tanto NP quanto co-NP. P é considerado estritamente um subconjunto de ambas classes (e comprovadamente não pode ser rigoroso em um caso, e não em outro). NP e co-NP são também considerados iguais. Caso seja, então um problema que não seja NP-completo pode ser NP e um problema que não seja co-NP-completo pode ser NP. Isso pode ser demonstrado como se segue. Assumindo que existe um problema NP-completo que esta em co-NP. Já que todos os problemas em NP podem ser reduzidos para esse problemas, então para todos os problemas em NP nos podemos construir a Máquina de Turing não determinística que decide o complemento desse problema em tempo polinomial,ou seja, NP é um subconjunto de co-NP. Visto que o conjunto de complementos dos problemas NP é subconjunto do conjunto de complementos dos problemas em co-NO, ou seja, co-NP é um subconjunto de NO.Uma vez que já sabia que NP é subconjunto de co-NP, então eles são iguais. A prova para o fato de que nenhum problema co-NP-completo pode ser em NP é simétrica. 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. Um exemplo de problema que sabe-se estar em NP e em co-NP é a Fatoração de inteiros: dado números inteiros positivos m e n determine se m tem um fator menor que n e maior que um. A participação em NP é clase; se m tem um fator, entao o fator é a prova. Participação em co-NP é mais sutil; primeiro é preciso lista os fatores primos de m e fornecer uma certificado de primariedade para cada um. Fatoração de inteiros é muitas vezes confundido com o problema da primariedade. Ambos testes de primariedade e fatoração são conhecidos como problemas No e Co-NP. O Teste de primalidade AKS, publicado em 2002, prova que o teste de primariedade também esta em P, enquanto que fatoração pode ou não ter um algoritmo em tempo polinomial. 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. 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. 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. That is, co-NP is the set of decision problems where there exists a polynomial p(n) and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by p(n), the Turing machine M accepts the pair (x, c). В теории алгоритмов часто рассматривается класс, тесно связанный с P и NP, — класс дополнений языков из NP, называемый co-NP.
prov:wasDerivedFrom
wikipedia-en:Co-NP?oldid=1069392707&ns=0
dbo:wikiPageLength
5795
foaf:isPrimaryTopicOf
wikipedia-en:Co-NP