NP-completeness (original) (raw)
En complexitat computacional, el conjunt de problemes NP-complet, que son els problemes que pertanyen tant a NP com a NP-hard. En aquest context, NP vol dir "temps polinòmic no determinista". Els problemes NP-complets estan a NP, el conjunt de problemes de decisió la solució dels quals es pot verificar en temps polinòmic en una màquina de Turing no determinista. Un problema p de NP és NP-complet si cada tot altre problema de NP es pot transformar a p en temps polinòmic.
| Property | Value |
|---|---|
| dbo:abstract | En complexitat computacional, el conjunt de problemes NP-complet, que son els problemes que pertanyen tant a NP com a NP-hard. En aquest context, NP vol dir "temps polinòmic no determinista". Els problemes NP-complets estan a NP, el conjunt de problemes de decisió la solució dels quals es pot verificar en temps polinòmic en una màquina de Turing no determinista. Un problema p de NP és NP-complet si cada tot altre problema de NP es pot transformar a p en temps polinòmic. (ca) في الرياضيات صنف التعقيد، تعرف المسائل كثيرة الحدود غير القطعية الكاملة (NP-complete problems)، بأنها كل ما يحقق الشرطين الآتيين: * لكل لغة،L, موجودة في NP يوجد دالة بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها، بحيث ان f : إذا وإذا * المسألة A من صنف NP أي يمكن بناء آلة تورنغ غير حتمية تقرر اللغة A. أول لغة عرفت بانها NP كاملة هي SAT حيث قام كل من كوك وليفين باثبات هذا كل على حدا، ومنذ ذلك الحين كثير من المسائل عُرف انها NP كاملة. (ar) NP-úplné (NP-complete, NPC) problémy jsou takové nedeterministicky polynomiální problémy, na které jsou všechny ostatní problémy z NP. To znamená, že třídu NP-úplných úloh tvoří v jistém smyslu ty nejtěžší úlohy z NP. Pokud by byl nalezen polynomiální deterministický algoritmus pro nějakou NP-úplnou úlohu, znamenalo by to, že všechny nedeterministicky polynomiální problémy jsou řešitelné v polynomiálním čase, tedy že třída NP se „zhroutí“ do třídy P (NP = P). Otázka, zda nějaký takový algoritmus existuje, zatím nebyla rozhodnuta, předpokládá se však, že NP ≠ P (je však zřejmé, že P ⊆ NP). Více o tomto problému najdete v článku Problém P versus NP. Vztah mezi P a NP je jedním ze sedmi problémů tisíciletí, které vypsal Clayův matematický ústav 24. května 2000. Za rozhodnutí vztahu nabízí 1 000 000 dolarů. (cs) In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt als auch NP-schwer ist. Dies bedeutet umgangssprachlich, dass es sich vermutlich nicht effizient lösen lässt. Formal wird NP-Vollständigkeit nur für Entscheidungsprobleme definiert (mögliche Lösungen nur „ja“ oder „nein“), während man bei anderen Problemtypen von NP-Äquivalenz spricht (etwa bei Suchproblemen oder Optimierungsproblemen). Umgangssprachlich wird diese Unterscheidung jedoch oft nicht vollzogen, so dass man ganz allgemein von „NP-vollständigen Problemen“ spricht, unabhängig davon, ob ein Entscheidungsproblem vorliegt oder nicht. Dies ist möglich, da verschiedene Problemtypen ineinander überführbar (aufeinander reduzierbar) sind. Ein Entscheidungsproblem ist NP-vollständig, wenn es * in der Komplexitätsklasse NP liegt: Ein deterministisch arbeitender Rechner benötigt nur polynomiell viel Zeit, um zu entscheiden, ob eine vorgeschlagene Lösung eines zugehörigen Suchproblems tatsächlich eine Lösung ist, und * zu den NP-schweren Problemen gehört: Alle anderen Probleme, deren Lösungen deterministisch in polynomieller Zeit überprüft werden können, können auf das Problem derart zurückgeführt werden, dass diese Rückführung auf einem deterministischen Rechner höchstens polynomielle Zeit in Anspruch nimmt. Man spricht von einer Polynomialzeitreduktion. Die Klasse aller NP-vollständigen Probleme wird mit NP-C (complete) bezeichnet. Die Eigenschaften dieser und anderer Klassen werden in der Komplexitätstheorie erforscht, einem Teilgebiet der theoretischen Informatik. NP-vollständige Probleme lassen sich vermutlich nicht effizient lösen, da ihre Lösung auf realen Rechnern viel Zeit in Anspruch nimmt. In der Praxis wirkt sich dies nicht in jedem Fall negativ aus, das heißt, es gibt für viele NP-vollständige Probleme Lösungsverfahren, anhand deren sie für in der Praxis auftretende Größenordnungen in akzeptabler Zeit lösbar sind. Viele in der Praxis auftauchende und wichtige Probleme sind NP-vollständig, was NP-Vollständigkeit zu einem zentralen Begriff der Informatik macht. Weiter verstärkt wird diese Bedeutung durch das sogenannte P-NP-Problem: 1. * Für kein NP-vollständiges Problem konnte bisher nachgewiesen werden, dass es in polynomieller Zeit lösbar wäre. 2. * Falls nur ein einziges dieser Probleme in polynomieller Zeit lösbar wäre, dann wäre jedes Problem in NP in polynomieller Zeit lösbar, was große Bedeutung für die Praxis haben könnte (jedoch nicht notwendigerweise haben muss). Seit der Einführung der NP-Vollständigkeit durch Cook wurde die Vollständigkeit zu einem allgemeinen Konzept für beliebige Komplexitätsklassen ausgebaut. (de) En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico. Si se demostrase que un problema NP-completo, llamémoslo A, no se pudiese resolver en tiempo polinómico, el resto de los problemas NP-completos tampoco se podrían resolver en tiempo polinómico. Esto se debe a que si uno de los problemas NP-completos distintos de A, digamos X, se pudiese resolver en tiempo polinómico, entonces A se podría resolver en tiempo polinómico, por definición de NP-completo. Ahora, pueden existir problemas en NP y que no sean NP-completos para los cuales exista solución polinómica, aun no existiendo solución para A. Como ejemplo de un problema NP-completo encontramos el problema de la suma de subconjuntos que se puede enunciar como sigue: dado un conjunto S de enteros, ¿existe un subconjunto no vacío de S cuyos elementos sumen cero? Es fácil verificar si una respuesta es correcta, pero no se conoce mejor solución que explorar todos los 2n-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición. (es) In computational complexity theory, a problem is NP-complete when: 1. * it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. 2. * the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search. "Complete" refers to the property of being able to simulate everything in the same complexity class. More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly (in polynomial time), such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called NP, an abbreviation for "nondeterministic polynomial time". A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it even though it may not be in NP. Conversely, a problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If some NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC. Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the fundamental unsolved problems in computer science today. While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms. (en) En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : * il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; * tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP. Un problème NP-difficile est un problème qui remplit la seconde condition, et donc peut être dans une classe de problème plus large et donc plus difficile que la classe NP. Bien qu'on puisse vérifier rapidement toute solution proposée d'un problème NP-complet, on ne sait pas en trouver efficacement. C'est le cas, par exemple, du problème du voyageur de commerce ou de celui du problème du sac à dos. Tous les algorithmes connus pour résoudre des problèmes NP-complets ont un temps d'exécution exponentiel en fonction de la taille des données d'entrée dans le pire des cas, et sont donc inexploitables en pratique même pour des instances de taille modérée. La seconde propriété de la définition implique que s'il existe un algorithme polynomial pour résoudre un quelconque des problèmes NP-complets, alors tous les problèmes de la classe NP peuvent être résolus en temps polynomial. Trouver un algorithme polynomial pour un problème NP-complet ou prouver qu'il n'en existe pas permettrait de savoir si P = NP ou P ≠ NP, une question ouverte qui fait partie des problèmes non résolus en mathématiques les plus importants à ce jour. En pratique, les informaticiens et les développeurs sont souvent confrontés à des problèmes NP-complets. Dans ce cas, savoir que le problème sur lequel on travaille est NP-complet est une indication du fait que le problème est difficile à résoudre, donc qu'il vaut mieux chercher des solutions approchées en utilisant des algorithmes d'approximation ou utiliser des heuristiques pour trouver des solutions exactes. (fr) NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP의 형태로 풀리게 된다. 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 P≠NP의 형태로 풀리게 된다. (ko) Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP (" in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP. La classe di complessità che contiene tutti i problemi NP-completi è spesso indicata con NP-C. Un esempio di problema NP-completo è il problema delle somme parziali, cioè: dato un insieme finito di numeri interi, determinare se esiste un sottoinsieme tale che la somma dei suoi elementi sia zero. È evidente che è facile verificare velocemente se un sottoinsieme è o meno una soluzione del problema, ma non è noto alcun metodo per trovare una soluzione che sia sensibilmente più veloce di provare tutti i possibili sottoinsiemi tranne i due che contengono tutti numeri concordi (tutti negativi o tutti positivi), quelli formati da un solo numero negativo e da tutti numeri positivi maggiori in valore assoluto al numero negativo e quelli formati da un solo numero positivo e da tutti numeri negativi maggiori in valore assoluto al numero positivo. (it) NP完全（な）問題（エヌピーかんぜん（な）もんだい、NP-complete problem）とは、(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) クラスNPに属する任意の問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明され、R. M. カープの定義した多項式時間還元によって多くの計算量的に困難な問題が NP 完全であることが示された。 (ja) NP-volledigheid is een concept uit de complexiteitstheorie. Het is een beschrijving van het inzicht uit de jaren 70 dat er een bepaald verband is tussen de complexiteit van een groot aantal problemen die in de wiskunde en informatica als "moeilijk" worden beschouwd. In formele zin is een probleem NP-volledig (ook soms NP-compleet genoemd) als en slechts als * het probleem tot de NP behoort. * elk ander probleem in NP in polynomiale tijd naar dit probleem kan worden gereduceerd. (nl) Problem NP-zupełny (NPC, ang. NP-Complete) – w klasie NP, ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w takim czasie wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności). Pierwszym problemem, którego NP-zupełność wykazano, był problem SAT, czyli problem spełnialności formuł zdaniowych. Udowodnił to w 1971 roku Stephen Cook. Pytanie, czy problemy NP-zupełne można rozwiązywać w czasie wielomianowym, jest największą zagadką informatyki teoretycznej. Ciągle nie udowodniono tego, iż (nie udowodniono także przeciwnie, że ), która jednoznacznie stwierdzałaby, że jest to niemożliwe. Rozwiązanie tego problemu znalazło się na liście problemów milenijnych. Mimo ufundowania miliona dolarów za rozwiązanie tak postawionego problemu, nikomu się to nie udało. Problem nie może być jednocześnie NP-zupełny i CoNP-zupełny, chyba że (pl) NP-fullständiga problem (på engelska NP complete ibland NPC, från nondeterministic polynomial) är en klass av matematiska problem för vilka effektiva lösningar saknas. Den enda lösningen man funnit på ett godtyckligt NP-fullständigt problem är i princip att gå igenom alla tänkbara lösningar och jämföra dem, vilket är ogörligt för andra än små probleminstanser. (sv) Na teoria da complexidade computacional, a classe de complexidade é o subconjunto dos problemas NP de tal modo que todo problema em NP se pode reduzir, com uma redução de tempo polinomial, a um dos problemas NP-completo. Pode-se dizer que os problemas de NP-completo são os problemas mais difíceis de NP e muito provavelmente não formem parte da classe de complexidade P. A razão é que se conseguisse encontrar uma maneira de resolver qualquer problema NP-completo rapidamente (em tempo polinomial) , então poderiam ser utilizados algoritmos para resolver todos problemas NP rapidamente. Como exemplo de um problema NP-completo está o problema da soma dos subconjuntos que pode ser enunciado conforme segue: dado um conjunto S de inteiros, determine se há algum conjunto não vazio de S cujos elementos somem zero. É fácil de verificar se uma resposta é correta, mas não se conhece uma solução significativamente mais rápida para resolver este problema do que testar todos os subconjuntos possíveis, até encontrar um que cumpra com a condição.Na prática, o conhecimento de NP-completo pode evitar que se desperdice tempo tentando encontrar um algoritmo de tempo polinomial para resolver um problema quando esse algoritmo não existe. (pt) NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных). Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». (ru) NP完全或NP完备 （NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中，決定性問題的等級之一。NP完备是NP与NP困难問題的交集，是NP中最難的決定性問題，所有NP問題都可以在多項式時間內被歸約（reduce to）為NP完備問題。倘若任何NP完備問題得到多項式時間內的解法，則該解法就可應用在所有NP問題上，亦可證明NP問題等於P問題，然而目前為止並未發現任何能在多項式時間內解決NP完備問題的方法。 (zh) NP-повна задача (англ. NP-complete) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/3SAT_17_svg.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.csc.kth.se/~viggo/problemlist/ http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html http://www.mathreference.com/lan-cx-np,intro.html http://www.ics.uci.edu/~eppstein/cgt/hard.html http://is.cs.nthu.edu.tw/course/2008Spring/cs431102/hmsunCh08.ppt http://www.cs.lth.se/home/Rolf_Karlsson/bk/lect8.pdf http://www.csie.ncu.edu.tw/%7Ejrjiang/alg2006/NPC-3.ppt http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf https://archive.org/details/introductiontoth00sips/page/248 https://arxiv.org/abs/cs.CC/0210020 https://arxiv.org/abs/quant-ph/0502072 https://web.archive.org/web/20061216121200/http:/for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm https://web.archive.org/web/20090419082030/http:/www.cs.lth.se/home/Rolf_Karlsson/bk/lect8.pdf https://web.archive.org/web/20090902082705/http:/is.cs.nthu.edu.tw/course/2008Spring/cs431102/hmsunCh08.ppt |
| dbo:wikiPageID | 23385892 (xsd:integer) |
| dbo:wikiPageLength | 30665 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123204053 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Scott_Aaronson dbr:NP_(complexity) dbr:Nondeterministic_Turing_machine dbr:Metaheuristic dbr:David_S._Johnson dbr:Deterministic dbr:Algorithm dbr:Approximation_algorithm dbr:University_of_Liverpool dbr:Vertex_cover_problem dbr:Decision_problem dbr:Deterministic_algorithm dbr:Information-theoretic_security dbr:Intersection dbr:Register_allocation dbr:Galley_proofs dbr:Presburger_arithmetic dbc:NP-complete_problems dbr:Concatenation dbr:Valiant–Vazirani_theorem dbr:Clay_Mathematics_Institute dbr:Clique_problem dbr:Co-NP dbr:Genetic_algorithm dbr:Monte_Carlo_method dbr:NP-hard dbr:Cook–Levin_theorem dbr:L_(complexity) dbr:Labours_of_Hercules dbr:SIAM_Journal_on_Computing dbr:Strongly_NP-complete dbr:Complement_(complexity) dbr:Complete_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computer_scientist dbr:Hamiltonian_path_problem dbr:Planar_separator_theorem dbr:Theoretical_computer_science dbr:Many-one_reduction dbc:1971_in_computing dbr:Travelling_Salesman_(2012_film) dbr:Travelling_salesman_problem dbr:Gadget_(computer_science) dbr:Karp's_21_NP-complete_problems dbr:Polynomial-time_reduction dbr:P-complete dbr:Open_problem dbr:3-satisfiability dbr:Alfred_Aho dbr:Cycle_graph dbr:Non-deterministic_Turing_machine dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Graph_theory dbr:Isomorphism dbr:Kenneth_Steiglitz dbr:List_of_NP-complete_problems dbr:Reduction_(complexity) dbr:2-satisfiability dbc:Complexity_classes dbr:Halting_problem dbr:Isomorphic dbr:Jeffrey_Ullman dbr:AC0 dbr:Abstract_machine dbc:Mathematical_optimization dbr:John_Hopcroft dbr:Lance_Fortnow dbr:Bipartite_graph dbr:Co-NP-complete dbr:Heuristic_(computer_science) dbr:Donald_Knuth dbr:Boolean_satisfiability_problem dbr:Planar_graph dbr:Greedy_coloring dbr:Polynomial_time dbr:Dominating_set_problem dbr:Graph_coloring_problem dbr:Independent_set_problem dbr:Michael_Garey dbr:Minimum_spanning_tree dbr:Brute-force_search dbr:National_Central_University dbr:National_Tsing_Hua_University dbr:Randomized_algorithm dbr:Kleene_star dbr:Knapsack_problem dbr:Turing_machine dbr:Subset_sum_problem dbr:Symposium_on_Theory_of_Computing dbr:Union_(set_theory) dbr:Universal_Turing_machine dbr:Vertex_(graph_theory) dbr:Commun._ACM dbr:Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness dbr:Subgraph_isomorphism_problem dbr:NL-complete dbr:SIGACT dbr:P_versus_NP_problem dbr:Parameterized_complexity dbr:Turing_completeness dbr:RISC dbr:Computer_programmer dbr:Unsolved_problems_of_mathematics dbr:Richard_Karp dbr:List_of_open_problems_in_computer_science dbr:Running_time dbr:P_=_NP_problem dbr:Almost_complete dbr:Superpolynomial dbr:Ladner's_theorem dbr:Logarithmic-space_many-one_reduction dbr:Logarithmic_space dbr:File:P_np_np-complete_np-hard.svg dbr:File:3SAT_17_svg.svg dbr:File:Relative_NPC_chart.svg dbr:Graph-coloring_global_register_allocation |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Cite_web dbt:Cn dbt:Confusing dbt:Div_col dbt:Div_col_end dbt:Main dbt:Refbegin dbt:Refend dbt:Reflist dbt:See_also dbt:Short_description dbt:Sic dbt:Sqrt dbt:Clarify_span dbt:ComplexityClasses |
| dcterms:subject | dbc:NP-complete_problems dbc:1971_in_computing dbc:Complexity_classes dbc:Mathematical_optimization |
| gold:hypernym | dbr:NP-complete |
| rdf:type | owl:Thing yago:WikicatComplexityClasses yago:WikicatNP-completeProblems yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Arrangement105726596 yago:Attribute100024264 yago:Class107997703 yago:Cognition100023271 yago:Collection107951464 yago:Condition113920835 yago:DataStructure105728493 yago:Difficulty114408086 yago:Event100029378 yago:Group100031264 yago:Problem114410605 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 yago:State100024720 yago:Structure105726345 yago:WikicatDataStructures |
| rdfs:comment | En complexitat computacional, el conjunt de problemes NP-complet, que son els problemes que pertanyen tant a NP com a NP-hard. En aquest context, NP vol dir "temps polinòmic no determinista". Els problemes NP-complets estan a NP, el conjunt de problemes de decisió la solució dels quals es pot verificar en temps polinòmic en una màquina de Turing no determinista. Un problema p de NP és NP-complet si cada tot altre problema de NP es pot transformar a p en temps polinòmic. (ca) في الرياضيات صنف التعقيد، تعرف المسائل كثيرة الحدود غير القطعية الكاملة (NP-complete problems)، بأنها كل ما يحقق الشرطين الآتيين: * لكل لغة،L, موجودة في NP يوجد دالة بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها، بحيث ان f : إذا وإذا * المسألة A من صنف NP أي يمكن بناء آلة تورنغ غير حتمية تقرر اللغة A. أول لغة عرفت بانها NP كاملة هي SAT حيث قام كل من كوك وليفين باثبات هذا كل على حدا، ومنذ ذلك الحين كثير من المسائل عُرف انها NP كاملة. (ar) NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP의 형태로 풀리게 된다. 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 P≠NP의 형태로 풀리게 된다. (ko) NP完全（な）問題（エヌピーかんぜん（な）もんだい、NP-complete problem）とは、(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) クラスNPに属する任意の問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明され、R. M. カープの定義した多項式時間還元によって多くの計算量的に困難な問題が NP 完全であることが示された。 (ja) NP-volledigheid is een concept uit de complexiteitstheorie. Het is een beschrijving van het inzicht uit de jaren 70 dat er een bepaald verband is tussen de complexiteit van een groot aantal problemen die in de wiskunde en informatica als "moeilijk" worden beschouwd. In formele zin is een probleem NP-volledig (ook soms NP-compleet genoemd) als en slechts als * het probleem tot de NP behoort. * elk ander probleem in NP in polynomiale tijd naar dit probleem kan worden gereduceerd. (nl) NP-fullständiga problem (på engelska NP complete ibland NPC, från nondeterministic polynomial) är en klass av matematiska problem för vilka effektiva lösningar saknas. Den enda lösningen man funnit på ett godtyckligt NP-fullständigt problem är i princip att gå igenom alla tänkbara lösningar och jämföra dem, vilket är ogörligt för andra än små probleminstanser. (sv) NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных). Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». (ru) NP完全或NP完备 （NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中，決定性問題的等級之一。NP完备是NP与NP困难問題的交集，是NP中最難的決定性問題，所有NP問題都可以在多項式時間內被歸約（reduce to）為NP完備問題。倘若任何NP完備問題得到多項式時間內的解法，則該解法就可應用在所有NP問題上，亦可證明NP問題等於P問題，然而目前為止並未發現任何能在多項式時間內解決NP完備問題的方法。 (zh) NP-повна задача (англ. NP-complete) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час. (uk) NP-úplné (NP-complete, NPC) problémy jsou takové nedeterministicky polynomiální problémy, na které jsou všechny ostatní problémy z NP. To znamená, že třídu NP-úplných úloh tvoří v jistém smyslu ty nejtěžší úlohy z NP. Pokud by byl nalezen polynomiální deterministický algoritmus pro nějakou NP-úplnou úlohu, znamenalo by to, že všechny nedeterministicky polynomiální problémy jsou řešitelné v polynomiálním čase, tedy že třída NP se „zhroutí“ do třídy P (NP = P). Otázka, zda nějaký takový algoritmus existuje, zatím nebyla rozhodnuta, předpokládá se však, že NP ≠ P (je však zřejmé, že P ⊆ NP). Více o tomto problému najdete v článku Problém P versus NP. (cs) In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt als auch NP-schwer ist. Dies bedeutet umgangssprachlich, dass es sich vermutlich nicht effizient lösen lässt. Ein Entscheidungsproblem ist NP-vollständig, wenn es Seit der Einführung der NP-Vollständigkeit durch Cook wurde die Vollständigkeit zu einem allgemeinen Konzept für beliebige Komplexitätsklassen ausgebaut. (de) En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico. (es) In computational complexity theory, a problem is NP-complete when: 1. * it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. 2. * the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. (en) Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP (" in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP. La classe di complessità che contiene tutti i problemi NP-completi è spesso indicata con NP-C. (it) En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : * il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; * tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP. (fr) Problem NP-zupełny (NPC, ang. NP-Complete) – w klasie NP, ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w takim czasie wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności). (pl) Na teoria da complexidade computacional, a classe de complexidade é o subconjunto dos problemas NP de tal modo que todo problema em NP se pode reduzir, com uma redução de tempo polinomial, a um dos problemas NP-completo. Pode-se dizer que os problemas de NP-completo são os problemas mais difíceis de NP e muito provavelmente não formem parte da classe de complexidade P. A razão é que se conseguisse encontrar uma maneira de resolver qualquer problema NP-completo rapidamente (em tempo polinomial) , então poderiam ser utilizados algoritmos para resolver todos problemas NP rapidamente. Como exemplo de um problema NP-completo está o problema da soma dos subconjuntos que pode ser enunciado conforme segue: dado um conjunto S de inteiros, determine se há algum conjunto não vazio de S cujos elemento (pt) |
| rdfs:label | مسألة كثيرة حدود غير قطعية كاملة (ar) NP-complet (ca) NP-úplnost (cs) NP-Vollständigkeit (de) NP-completeness (el) NP-completo (es) Problème NP-complet (fr) NP-completo (it) NP-완전 (ko) NP-completeness (en) NP完全問題 (ja) NP-volledig (nl) Problem NP-zupełny (pl) NP-полная задача (ru) NP-completo (pt) NP-повна задача (uk) NP-fullständig (sv) NP完全 (zh) |
| rdfs:seeAlso | dbr:P_=_NP_problem |
| owl:sameAs | freebase:NP-completeness yago-res:NP-completeness wikidata:NP-completeness dbpedia-ar:NP-completeness dbpedia-az:NP-completeness dbpedia-ca:NP-completeness dbpedia-cs:NP-completeness dbpedia-da:NP-completeness dbpedia-de:NP-completeness dbpedia-el:NP-completeness dbpedia-es:NP-completeness dbpedia-fa:NP-completeness dbpedia-fi:NP-completeness dbpedia-fr:NP-completeness dbpedia-it:NP-completeness dbpedia-ja:NP-completeness dbpedia-ko:NP-completeness dbpedia-nl:NP-completeness dbpedia-nn:NP-completeness dbpedia-no:NP-completeness dbpedia-pl:NP-completeness dbpedia-pt:NP-completeness dbpedia-ro:NP-completeness dbpedia-ru:NP-completeness dbpedia-sh:NP-completeness dbpedia-simple:NP-completeness dbpedia-sk:NP-completeness dbpedia-sr:NP-completeness dbpedia-sv:NP-completeness dbpedia-th:NP-completeness dbpedia-tr:NP-completeness dbpedia-uk:NP-completeness dbpedia-vi:NP-completeness dbpedia-zh:NP-completeness https://global.dbpedia.org/id/23jm7 |
| prov:wasDerivedFrom | wikipedia-en:NP-completeness?oldid=1123204053&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/P_np_np-complete_np-hard.svg wiki-commons:Special:FilePath/3SAT_17_svg.svg wiki-commons:Special:FilePath/Relative_NPC_chart.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:NP-completeness |
| is dbo:wikiPageRedirects of | dbr:Non-deterministic_polynomial-time_complete dbr:Non_polynomial_complete dbr:Nondeterministic_Polynomial_Complete dbr:Np-Complete dbr:NP-complete dbr:Np-complete dbr:NP-Complete dbr:NP-complete_problems dbr:Np-complete_problem dbr:Np_complete dbr:Np_completeness dbr:NP-C dbr:NP-Completeness dbr:NP-complete_language dbr:NP-complete_problem dbr:NP-incomplete dbr:NP_complete dbr:NP_completeness |
| is dbo:wikiPageWikiLink of | dbr:Bend_minimization dbr:Science_and_technology_in_Ukraine dbr:List_of_University_of_Toronto_faculty dbr:List_of_computer_scientists dbr:Non-deterministic_polynomial-time_complete dbr:MacMahon_Squares dbr:Parsimonious_reduction dbr:Non_polynomial_complete dbr:Nondeterministic_Polynomial_Complete dbr:David_S._Johnson dbr:Approximation_algorithm dbr:Jonathan_S._Turner dbr:University_of_Toronto dbr:Vertex_cover dbr:Degree_(graph_theory) dbr:Dynamic_epistemic_logic dbr:Independent_set_(graph_theory) dbr:Interchangeability_algorithm dbr:Register_allocation dbr:Universal_algebra dbr:Np-Complete dbr:Geometric_set_cover_problem dbr:Tree_spanner dbr:Quantum_algorithm dbr:Quantum_counting_algorithm dbr:Clique_problem dbr:Glossary_of_artificial_intelligence dbr:NLTS_Conjecture dbr:NP-complete dbr:Conjunctive_query dbr:Contraction_hierarchies dbr:Cook–Levin_theorem dbr:Optical_computing dbr:Lenore_Blum dbr:Leonid_Levin dbr:Combinatorial_optimization dbr:Computational_social_choice dbr:Feedback_arc_set dbr:Peg_solitaire dbr:Quantum_supremacy dbr:1971_in_science dbr:BQP dbr:Travelling_salesman_problem dbr:Tree_decomposition dbr:Treewidth dbr:Las_Vegas_algorithm dbr:Lattice_protein dbr:Minimum-weight_triangulation dbr:TFNP dbr:Daniel_J._Hulme dbr:Np-complete dbr:Frances_A._Rosamond dbr:Hitori dbr:Ising_model dbr:Asymptotic_computational_complexity dbr:Bag_(puzzle) dbr:ASR-complete dbr:Biomolecular_structure dbr:Bipartite_dimension dbr:Cobham's_thesis dbr:Real_RAM dbr:Rectangle_packing dbr:Grover's_algorithm dbr:Obliq dbr:Rainbow-independent_set dbr:Set_(card_game) dbr:Christopher_Cherniak dbr:SAT_solver dbr:Subset_sum_problem dbr:Symposium_on_Theory_of_Computing dbr:System_on_a_chip dbr:Umesh_Vazirani dbr:Eternity_II_puzzle dbr:Partial_k-tree dbr:Nanson's_method dbr:NP-Complete dbr:NP-complete_problems dbr:Simultaneous_embedding dbr:Topological_graph dbr:Seifert_surface dbr:Tatamibari dbr:PPAD_(complexity) dbr:True_quantified_Boolean_formula dbr:Tentai_Show dbr:Word-representable_graph dbr:Np-complete_problem dbr:Np_complete dbr:Np_completeness dbr:NP-C dbr:NP-Completeness dbr:NP-complete_language dbr:NP-complete_problem dbr:NP-incomplete dbr:NP_complete dbr:NP_completeness |
| is foaf:primaryTopic of | wikipedia-en:NP-completeness |
