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

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

Namespace Prefixes

PrefixIRI
dbthttp://dbpedia.org/resource/Template:
dbpedia-dahttp://da.dbpedia.org/resource/
dbpedia-elhttp://el.dbpedia.org/resource/
dbpedia-nohttp://no.dbpedia.org/resource/
dbpedia-svhttp://sv.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
n55http://www.ics.uci.edu/~eppstein/cgt/
n52http://www.csc.kth.se/~viggo/problemlist/
dbrhttp://dbpedia.org/resource/
dbpedia-fihttp://fi.dbpedia.org/resource/
n21https://web.archive.org/web/20090419082030/http:/www.cs.lth.se/home/Rolf_Karlsson/bk/
dbpedia-shhttp://sh.dbpedia.org/resource/
dbpedia-arhttp://ar.dbpedia.org/resource/
n19http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
dbpedia-cshttp://cs.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-azhttp://az.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n37http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
n60https://web.archive.org/web/20090902082705/http:/is.cs.nthu.edu.tw/course/2008Spring/cs431102/
n9http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/
n32https://arxiv.org/abs/quant-ph/
xsdhhttp://www.w3.org/2001/XMLSchema#
n59http://is.cs.nthu.edu.tw/course/2008Spring/cs431102/
n23http://people.cs.uchicago.edu/~fortnow/papers/
dbpedia-ukhttp://uk.dbpedia.org/resource/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-skhttp://sk.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
n48http://dbpedia.org/resource/Computers_and_Intractability:
n15http://www.mathreference.com/
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
n22http://www.csie.ncu.edu.tw/%7Ejrjiang/alg2006/
dbpedia-thhttp://th.dbpedia.org/resource/
dbpedia-rohttp://ro.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
n18http://www.cs.lth.se/home/Rolf_Karlsson/bk/
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbpedia-nlhttp://nl.dbpedia.org/resource/
yago-reshttp://yago-knowledge.org/resource/
n40https://global.dbpedia.org/id/
n35https://web.archive.org/web/20061216121200/http:/for.mat.bham.ac.uk/R.W.Kaye/minesw/
n62https://archive.org/details/introductiontoth00sips/page/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-cahttp://ca.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
dbpedia-nnhttp://nn.dbpedia.org/resource/
dbpedia-simplehttp://simple.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-kohttp://ko.dbpedia.org/resource/
dbpedia-trhttp://tr.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
n29https://arxiv.org/abs/cs.CC/
dbpedia-eshttp://es.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbr:NP-completeness
rdf:type
yago:Collection107951464 yago:Difficulty114408086 yago:Event100029378 owl:Thing yago:Condition113920835 yago:Cognition100023271 yago:WikicatComplexityClasses yago:Arrangement105726596 yago:Activity100407535 yago:WikicatSortingAlgorithms yago:DataStructure105728493 yago:Group100031264 yago:SortingAlgorithm105847658 yago:Rule105846932 yago:Abstraction100002137 yago:Algorithm105847438 yago:State100024720 yago:YagoPermanentlyLocatedEntity yago:Structure105726345 yago:Act100030358 yago:PsychologicalFeature100023100 yago:Attribute100024264 yago:Problem114410605 yago:WikicatNP-completeProblems yago:Procedure101023820 yago:Class107997703 yago:WikicatDataStructures
rdfs:label
NP-fullständig NP完全問題 مسألة كثيرة حدود غير قطعية كاملة NP-완전 NP-повна задача NP完全 NP-completeness NP-úplnost NP-completo NP-complet NP-completo NP-Vollständigkeit NP-completeness NP-completo NP-полная задача Problème NP-complet NP-volledig Problem NP-zupełny
rdfs:comment
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. 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). 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. NP完全(な)問題(エヌピーかんぜん(な)もんだい、NP-complete problem)とは、(1) クラスNP(Non-deterministic Polynomial)に属する決定問題(言語)で、かつ (2) クラスNPに属する任意の問題から多項式時間還元(帰着)可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明され、R. M. カープの定義した多項式時間還元によって多くの計算量的に困難な問題が NP 完全であることが示された。 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. 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 NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных). Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». 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. NP-повна задача (англ. NP-complete) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час. 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의 형태로 풀리게 된다. في الرياضيات صنف التعقيد، تعرف المسائل كثيرة الحدود غير القطعية الكاملة (NP-complete problems)، بأنها كل ما يحقق الشرطين الآتيين: * لكل لغة،L, موجودة في NP يوجد دالة بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها، بحيث ان f : إذا وإذا * المسألة A من صنف NP أي يمكن بناء آلة تورنغ غير حتمية تقرر اللغة A. أول لغة عرفت بانها NP كاملة هي SAT حيث قام كل من كوك وليفين باثبات هذا كل على حدا، ومنذ ذلك الحين كثير من المسائل عُرف انها NP كاملة. 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. 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. 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. 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. NP完全或NP完备 (NP-Complete,縮寫為NP-C或NPC),是計算複雜度理論中,決定性問題的等級之一。NP完备是NP与NP困难問題的交集,是NP中最難的決定性問題,所有NP問題都可以在多項式時間內被歸約(reduce to)為NP完備問題。倘若任何NP完備問題得到多項式時間內的解法,則該解法就可應用在所有NP問題上,亦可證明NP問題等於P問題,然而目前為止並未發現任何能在多項式時間內解決NP完備問題的方法。 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.
rdfs:seeAlso
dbr:P_=_NP_problem
foaf:depiction
n19:3SAT_17_svg.svg n19:P_np_np-complete_np-hard.svg n19:Relative_NPC_chart.svg
dcterms:subject
dbc:Complexity_classes dbc:Mathematical_optimization dbc:NP-complete_problems dbc:1971_in_computing
dbo:wikiPageID
23385892
dbo:wikiPageRevisionID
1123204053
dbo:wikiPageWikiLink
dbr:Brute-force_search dbr:Cook–Levin_theorem dbr:Scott_Aaronson dbr:Galley_proofs dbr:Halting_problem dbr:Labours_of_Hercules dbr:Nondeterministic_Turing_machine dbr:Subgraph_isomorphism_problem dbr:Intersection dbr:Isomorphic dbr:AC0 dbr:University_of_Liverpool dbr:National_Tsing_Hua_University dbr:NP-hard dbc:Complexity_classes dbr:Michael_Garey dbr:Theoretical_computer_science dbr:Bipartite_graph dbr:Co-NP dbr:Kenneth_Steiglitz dbr:Boolean_satisfiability_problem dbr:NP_(complexity) dbr:Heuristic_(computer_science) dbr:Computer_scientist dbr:P-complete dbr:Planar_separator_theorem dbr:Metaheuristic dbr:Concatenation dbr:L_(complexity) dbr:Monte_Carlo_method dbr:3-satisfiability dbr:SIGACT dbr:Vertex_(graph_theory) dbr:Richard_Karp dbr:Gadget_(computer_science) dbr:Polynomial_time dbc:Mathematical_optimization dbr:Decision_problem dbr:John_Hopcroft dbr:Hamiltonian_path_problem dbr:Karp's_21_NP-complete_problems dbr:Superpolynomial dbr:Alfred_Aho dbr:Almost_complete dbr:Reduction_(complexity) dbr:Clay_Mathematics_Institute dbr:David_S._Johnson dbr:Greedy_coloring n37:3SAT_17_svg.svg dbr:Independent_set_problem dbr:Algorithm dbr:Clique_problem n37:P_np_np-complete_np-hard.svg dbr:P_=_NP_problem dbr:Lance_Fortnow dbr:Complement_(complexity) dbr:Subset_sum_problem dbr:Parameterized_complexity dbr:SIAM_Journal_on_Computing dbr:Dominating_set_problem dbr:Abstract_machine dbr:Unsolved_problems_of_mathematics dbr:Open_problem dbr:Union_(set_theory) dbr:Cycle_graph n48:_A_Guide_to_the_Theory_of_NP-Completeness dbr:Graph_isomorphism dbr:Graph_coloring_problem dbr:Running_time dbr:Graph_isomorphism_problem dbr:Genetic_algorithm dbr:National_Central_University dbr:List_of_NP-complete_problems dbr:Donald_Knuth dbr:Kleene_star dbr:Graph_theory dbr:List_of_open_problems_in_computer_science dbr:Non-deterministic_Turing_machine dbr:Deterministic_algorithm dbr:Computer_programmer dbr:Minimum_spanning_tree dbr:Polynomial-time_reduction dbr:Presburger_arithmetic dbr:Isomorphism dbr:Computational_complexity_theory dbr:Planar_graph dbc:NP-complete_problems dbr:Turing_completeness dbr:Valiant–Vazirani_theorem dbr:Knapsack_problem dbr:Symposium_on_Theory_of_Computing dbr:Travelling_salesman_problem dbr:Register_allocation dbr:Logarithmic-space_many-one_reduction dbr:Universal_Turing_machine dbr:RISC dbr:Co-NP-complete dbr:Ladner's_theorem dbr:Travelling_Salesman_(2012_film) dbr:2-satisfiability dbr:Approximation_algorithm dbr:Commun._ACM n37:Relative_NPC_chart.svg dbc:1971_in_computing dbr:NL-complete dbr:Logarithmic_space dbr:Information-theoretic_security dbr:Complete_(complexity) dbr:P_versus_NP_problem dbr:Strongly_NP-complete dbr:Graph-coloring_global_register_allocation dbr:Complexity_class dbr:Many-one_reduction dbr:Randomized_algorithm dbr:Jeffrey_Ullman dbr:Deterministic dbr:Vertex_cover_problem dbr:Turing_machine
dbo:wikiPageExternalLink
n9:annotated_np.html n15:lan-cx-np,intro.html n18:lect8.pdf n21:lect8.pdf n22:NPC-3.ppt n23:pnp-cacm.pdf n29:0210020 n32:0502072 n35:ordmsw.htm n52: n55:hard.html n59:hmsunCh08.ppt n60:hmsunCh08.ppt n62:248
owl:sameAs
dbpedia-sv:NP-fullständig dbpedia-el:NP-completeness dbpedia-ca:NP-complet dbpedia-pt:NP-completo dbpedia-ja:NP完全問題 dbpedia-da:NP-komplet freebase:m.09tkl dbpedia-sh:NP-kompletni_problemi dbpedia-ar:مسألة_كثيرة_حدود_غير_قطعية_كاملة dbpedia-vi:NP-đầy_đủ dbpedia-ro:NP-completitudine wikidata:Q215206 dbpedia-fr:Problème_NP-complet dbpedia-no:NP-komplett dbpedia-sr:НП-комплетни_проблеми dbpedia-cs:NP-úplnost n40:23jm7 dbpedia-th:เอ็นพีบริบูรณ์ dbpedia-uk:NP-повна_задача dbpedia-fa:ان‌پی_کامل dbpedia-es:NP-completo dbpedia-de:NP-Vollständigkeit dbpedia-fi:NP-täydellisyys dbpedia-zh:NP完全 dbpedia-ko:NP-완전 dbpedia-nn:NP-komplett dbpedia-tr:NP-tam yago-res:NP-completeness dbpedia-pl:Problem_NP-zupełny dbpedia-nl:NP-volledig dbpedia-ru:NP-полная_задача dbpedia-simple:NP-complete dbpedia-az:NP-tam_məsələ dbpedia-it:NP-completo dbpedia-sk:NP-úplný_problém
dbp:wikiPageUsesTemplate
dbt:ComplexityClasses dbt:Short_description dbt:Sic dbt:Cite_conference dbt:Cite_book dbt:Cite_journal dbt:Cite_web dbt:Cn dbt:Clarify_span dbt:Main dbt:Div_col dbt:Div_col_end dbt:Confusing dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sqrt dbt:See_also
dbo:thumbnail
n19:3SAT_17_svg.svg?width=300
dbo:abstract
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. 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 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. 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. 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. في الرياضيات صنف التعقيد، تعرف المسائل كثيرة الحدود غير القطعية الكاملة (NP-complete problems)، بأنها كل ما يحقق الشرطين الآتيين: * لكل لغة،L, موجودة في NP يوجد دالة بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها، بحيث ان f : إذا وإذا * المسألة A من صنف NP أي يمكن بناء آلة تورنغ غير حتمية تقرر اللغة A. أول لغة عرفت بانها NP كاملة هي SAT حيث قام كل من كوك وليفين باثبات هذا كل على حدا، ومنذ ذلك الحين كثير من المسائل عُرف انها NP كاملة. NP完全(な)問題(エヌピーかんぜん(な)もんだい、NP-complete problem)とは、(1) クラスNP(Non-deterministic Polynomial)に属する決定問題(言語)で、かつ (2) クラスNPに属する任意の問題から多項式時間還元(帰着)可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明され、R. M. カープの定義した多項式時間還元によって多くの計算量的に困難な問題が NP 完全であることが示された。 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. 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. NP完全或NP完备 (NP-Complete,縮寫為NP-C或NPC),是計算複雜度理論中,決定性問題的等級之一。NP完备是NP与NP困难問題的交集,是NP中最難的決定性問題,所有NP問題都可以在多項式時間內被歸約(reduce to)為NP完備問題。倘若任何NP完備問題得到多項式時間內的解法,則該解法就可應用在所有NP問題上,亦可證明NP問題等於P問題,然而目前為止並未發現任何能在多項式時間內解決NP完備問題的方法。 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ů. 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의 형태로 풀리게 된다. NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных). Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». NP-повна задача (англ. NP-complete) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час. 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. 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. 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.
gold:hypernym
dbr:NP-complete
prov:wasDerivedFrom
wikipedia-en:NP-completeness?oldid=1123204053&ns=0
dbo:wikiPageLength
30665
foaf:isPrimaryTopicOf
wikipedia-en:NP-completeness