Co-NP-complete (original) (raw)
في علم التعقيد الحسابي مسائل co-NP كاملة هي مجموعة جزئية للمجموعة co-NP حيث انه كل أنَّ كل لغة منها يمكن اختصار كل اللغات في co-NP اليها.
| Property | Value |
|---|---|
| dbo:abstract | في علم التعقيد الحسابي مسائل co-NP كاملة هي مجموعة جزئية للمجموعة co-NP حيث انه كل أنَّ كل لغة منها يمكن اختصار كل اللغات في co-NP اليها. (ar) En teoria de la complexitat, la classe de complexitat co-NP-complet és el conjunt dels problemes de decisió més difícils de la classe co-NP, en el sentit que son els que menys s'assemblen als de la classe P. Un problema C pertany a co-NP-complet si està a co-NP i tot problema de co-NP té una transformació polinòmica cap C. Tot problema a co-NP-complet és el complementari d'un problema NP-complet. Hi ha problemes que poden estar alhora a NP i a co-NP, com tots els problemes dins la classe P o el problema de la factorització de nombres enters. Es desconeix si aquests dos conjunts son iguals, tot i que se sospita que no. Un exemple senzill de problema dins d'aquesta classe és el problema de la tautologia: determinar si una fórmula booleana és una tautologia. (ca) In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly. Each co-NP-complete problem is the complement of an NP-complete problem. There are some problems in both NP and co-NP, for example all problems in P or integer factorization. However, it is not known if the sets are equal, although inequality is thought more likely. See co-NP and NP-complete for more details. Fortune showed in 1979 that if any sparse language is co-NP-complete (or even just co-NP-hard), then P = NP, a critical foundation for Mahaney's theorem. (en) En teoría de la complejidad computacional, la clase de complejidad co-NP-completo es el conjunto de los problemas de decisión más difíciles de la clase co-NP, en el sentido de que son los que menos parecen pertenecer a la clase de complejidad P. De encontrarse una forma de resolver un problema en co-NP-completo en tiempo polinómico, el algoritmo utilizado serviría para resolver todos los problemas de co-NP con la misma complejidad. Más precisamente, un problema de decisión C pertenece a co-NP-completo si está en co-NP y si todo problema de co-NP tiene una transformación polinómica hacia él. Esto significa que para todo problema L en co-NP, existe un algoritmo que trabaja en tiempo polinómico que puede transformar una instancia de L en una instancia de C con el mismo resultado. Consecuentemente, de tenerse un algoritmo que trabajase en tiempo polinómico para C, se tendría un algoritmo en tiempo polinómico para cada uno de los problemas de co-NP. Cada problema en co-NP-completo es el complemento de uno en NP-completo. Los dos conjuntos son o iguales o disjuntos. Se supone que es lo último lo que es cierto, pero no se ha demostrado. * Datos: Q1142354 (es) 계산 복잡도 이론에서 복잡도 종류 co-NP-완전(co-NP-complete)이란 co-NP에서 가장 어려운 문제의 집합을 말한다. 여기서 어렵다는 것은, P에 들어갈 가능성이 낮다는 뜻이다. 한 co-NP-완전 문제를 빠르게 푸는 방법을 찾아낸다면, 그 방법을 써서 모든 co-NP-완전 문제를 빠르게 풀 수 있게 된다. 더 공식적인 정의: 결정 문제 C가 co-NP이고 모든 co-NP 문제가 이 문제로 다항 시간 환산 가능하면, C는 co-NP-완전이다. 이것은 모든 co-NP 문제 L에 대해서, L에 대한 어떤 예제든지 C에 대한 예제로 바꿀 수 있는 다항 시간 알고리즘이 있다는 뜻이다. 그러므로 C를 풀 수 있는 다항 시간 알고리즘이 있다면, 모든 co-NP 문제를 다항 시간에 풀 수 있게 된다. 대표적인 co-NP-완전 문제로 항진명제가 있다. 주어진 논리식이 항상 참인 명제인지 판정하는 문제이다. 다시 말해서, 식에서 변수마다 참/거짓 값을 넣을 때, 어떻게 넣어도 논리식 전체는 참이 되는 것이다. 이 문제는 충족 가능성 문제와 깊게 관련되어 있다. 불 만족 문제는 모든 변수값 할당에 대해 논리식이 참이 되는지를 판정하는 항진명제 문제와 달리, 논리식이 참이 되는 변수값 할당이 적어도 하나 있는지를 묻는 문제이다. co-NP-완전 문제 각각은 NP-완전 문제의 문제가 된다. co-NP-완전과 NP-완전은 같은 집합이거나, 전혀 겹치지 않는 집합이다. 뒤쪽이라는 설이 유력한데 아직 확실하지는 않다. 더 자세한 논의는 co-NP와 NP-완전을 참고하라. (ko) Nella teoria della complessità computazionale, i problemi computazionali che sono co-NP-completi sono i problemi più difficili in co-NP, nel senso che sono quelli che hanno le maggiori probabilità di non essere nella classe P. Se esiste un modo di risolvere rapidamente un problema co-NP-completo, allora quell'algoritmo può essere usato per risolvere rapidamente tutti i problemi co-NP. Ciascun problema co-NP-completo è il complemento di un problema NP-completo. Ci sono problemi sia in NP sia in co-NP, ad esempio tutti i problemi in P o di fattorizzazione degli interi, tuttavia non si sa se gli insiemi sono uguali, sebbene la disuguaglianza sia ritenuta più probabile. Vedi co-NP e NP-completo per maggiori dettagli. Fortune mostrò nel 1979 che se un qualsiasi è co-NP-completo (o anche solo co-NP-difficile), allora P = NP, un fondamento critico per il . (it) Co-NP-zupełność – klasa złożoności zawierająca takie problemy klasy Co-NP, że każdy inny problem klasy Co-NP może zostać do nich zredukowany, analogicznie jak dla problemów NP-zupełnych. Ponadto problem dopełniający względem problemu NP-zupełnego jest NP-trudny. (pl) Na teoria da complexidade computacional, problemas computacionais co-NP-completos são os problemas mais difíceis em co-NP, no sentido de que são os mais propensos a não serem P. Se existisse uma forma de resolver um problema co-NP-completo rapidamente, então esse algoritmo poderia ser usado para resolver todos os problemas co-NP de forma rápida. Um problema co-NP-completo é o complemento de um problema NP-completo. Existem alguns problemas que estão em NP e co-NP, contudo não se sabe se essas classes são iguais, embora a desigualdade seja o pensamento mais provável. Fortune mostrou em 1979 que se alguma sparse language é co-NP-completa (ou apenas co-NP-difícil), então P = NP, um fundamento essencial para o Mahaney's theorem. (pt) Co-NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет», принадлежащая классу co-NP, такая, что любая задача из этого класса может быть сведена к ней за полиномиальное время. Если P ≠ co-NP, то никакая co-NP-полная задача не может быть решена за полиномиальное время. Если же какая-либо co-NP-полная задача может быть решена , то быстрый алгоритм существует для любой задачи из класса co-NP. Любая co-NP-полная задача является дополнением некоторой NP-полной задачи. Существуют задачи, которые принадлежат как классу NP, так и классу co-NP, например, любая задача из класса P и задача факторизации. При этом неизвестно, совпадают ли классы NP и co-NP или, что эквивалентно, существует ли задача, одновременно являющаяся NP- и co-NP-полной. (ru) |
| dbo:wikiPageID | 54680 (xsd:integer) |
| dbo:wikiPageLength | 2840 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1021838821 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:Boolean_algebra_(logic) dbr:Decision_problem dbr:Integer_factorization dbr:Co-NP dbr:NP-complete dbr:Complement_(complexity) dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Mahaney's_theorem dbr:Sparse_language dbr:Truth_value dbc:Complexity_classes dbr:Tautology_(logic) dbr:Boolean_satisfiability_problem dbr:P_=_NP_problem dbr:Polynomial-time_many-one_reduction |
| dbp:wikiPageUsesTemplate | dbt:ComplexityClasses dbt:CZoo dbt:Lowercase |
| dct:subject | dbc:Complexity_classes |
| gold:hypernym | dbr:NP-complete |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | في علم التعقيد الحسابي مسائل co-NP كاملة هي مجموعة جزئية للمجموعة co-NP حيث انه كل أنَّ كل لغة منها يمكن اختصار كل اللغات في co-NP اليها. (ar) Co-NP-zupełność – klasa złożoności zawierająca takie problemy klasy Co-NP, że każdy inny problem klasy Co-NP może zostać do nich zredukowany, analogicznie jak dla problemów NP-zupełnych. Ponadto problem dopełniający względem problemu NP-zupełnego jest NP-trudny. (pl) En teoria de la complexitat, la classe de complexitat co-NP-complet és el conjunt dels problemes de decisió més difícils de la classe co-NP, en el sentit que son els que menys s'assemblen als de la classe P. Un problema C pertany a co-NP-complet si està a co-NP i tot problema de co-NP té una transformació polinòmica cap C. Un exemple senzill de problema dins d'aquesta classe és el problema de la tautologia: determinar si una fórmula booleana és una tautologia. (ca) In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly. (en) En teoría de la complejidad computacional, la clase de complejidad co-NP-completo es el conjunto de los problemas de decisión más difíciles de la clase co-NP, en el sentido de que son los que menos parecen pertenecer a la clase de complejidad P. De encontrarse una forma de resolver un problema en co-NP-completo en tiempo polinómico, el algoritmo utilizado serviría para resolver todos los problemas de co-NP con la misma complejidad. * Datos: Q1142354 (es) 계산 복잡도 이론에서 복잡도 종류 co-NP-완전(co-NP-complete)이란 co-NP에서 가장 어려운 문제의 집합을 말한다. 여기서 어렵다는 것은, P에 들어갈 가능성이 낮다는 뜻이다. 한 co-NP-완전 문제를 빠르게 푸는 방법을 찾아낸다면, 그 방법을 써서 모든 co-NP-완전 문제를 빠르게 풀 수 있게 된다. 더 공식적인 정의: 결정 문제 C가 co-NP이고 모든 co-NP 문제가 이 문제로 다항 시간 환산 가능하면, C는 co-NP-완전이다. 이것은 모든 co-NP 문제 L에 대해서, L에 대한 어떤 예제든지 C에 대한 예제로 바꿀 수 있는 다항 시간 알고리즘이 있다는 뜻이다. 그러므로 C를 풀 수 있는 다항 시간 알고리즘이 있다면, 모든 co-NP 문제를 다항 시간에 풀 수 있게 된다. co-NP-완전 문제 각각은 NP-완전 문제의 문제가 된다. co-NP-완전과 NP-완전은 같은 집합이거나, 전혀 겹치지 않는 집합이다. 뒤쪽이라는 설이 유력한데 아직 확실하지는 않다. 더 자세한 논의는 co-NP와 NP-완전을 참고하라. (ko) Nella teoria della complessità computazionale, i problemi computazionali che sono co-NP-completi sono i problemi più difficili in co-NP, nel senso che sono quelli che hanno le maggiori probabilità di non essere nella classe P. Se esiste un modo di risolvere rapidamente un problema co-NP-completo, allora quell'algoritmo può essere usato per risolvere rapidamente tutti i problemi co-NP. Fortune mostrò nel 1979 che se un qualsiasi è co-NP-completo (o anche solo co-NP-difficile), allora P = NP, un fondamento critico per il . (it) Na teoria da complexidade computacional, problemas computacionais co-NP-completos são os problemas mais difíceis em co-NP, no sentido de que são os mais propensos a não serem P. Se existisse uma forma de resolver um problema co-NP-completo rapidamente, então esse algoritmo poderia ser usado para resolver todos os problemas co-NP de forma rápida. Um problema co-NP-completo é o complemento de um problema NP-completo. Existem alguns problemas que estão em NP e co-NP, contudo não se sabe se essas classes são iguais, embora a desigualdade seja o pensamento mais provável. (pt) Co-NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет», принадлежащая классу co-NP, такая, что любая задача из этого класса может быть сведена к ней за полиномиальное время. Если P ≠ co-NP, то никакая co-NP-полная задача не может быть решена за полиномиальное время. Если же какая-либо co-NP-полная задача может быть решена , то быстрый алгоритм существует для любой задачи из класса co-NP. (ru) |
| rdfs:label | مسائل co-NP كاملة (ar) Co-NP-complet (ca) Co-NP-completo (es) Co-NP-complete (en) Co-NP-completo (it) Co-NP-완전 (ko) Klasa Co-NPC (pl) Co-NP-completo (pt) Класс Co-NP-complete (ru) |
| owl:sameAs | freebase:Co-NP-complete yago-res:Co-NP-complete wikidata:Co-NP-complete dbpedia-ar:Co-NP-complete dbpedia-ca:Co-NP-complete dbpedia-es:Co-NP-complete dbpedia-it:Co-NP-complete dbpedia-ko:Co-NP-complete dbpedia-pl:Co-NP-complete dbpedia-pt:Co-NP-complete dbpedia-ru:Co-NP-complete dbpedia-vi:Co-NP-complete https://global.dbpedia.org/id/C9gu |
| prov:wasDerivedFrom | wikipedia-en:Co-NP-complete?oldid=1021838821&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Co-NP-complete |
| is dbo:wikiPageRedirects of | dbr:Co-NP-Complete dbr:CoNP-complete dbr:Co-NP-hard dbr:CoNP-hard |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:Vaughan_Pratt dbr:Decision_problem dbr:Integer_factorization dbr:Co-NP dbr:Snark_(graph_theory) dbr:Co-NP-Complete dbr:CoNP-complete dbr:Sparse_language dbr:Maximin_share dbr:Automated_theorem_proving dbr:Null_(SQL) dbr:Tautology_(logic) dbr:Łukasiewicz_logic dbr:Reconfiguration dbr:Boolean_satisfiability_problem dbr:Circuit_satisfiability_problem dbr:Greedy_coloring dbr:Implicational_propositional_calculus dbr:Minesweeper_(video_game) dbr:Satisfiability dbr:List_of_unsolved_problems_in_fair_division dbr:NP-completeness dbr:P_versus_NP_problem dbr:Co-NP-hard dbr:CoNP-hard |
| is foaf:primaryTopic of | wikipedia-en:Co-NP-complete |