| dbpprop:abstract
|
- In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC, with NP standing for nondeterministic polynomial time), is a class of problems having two properties Any given solution to the problem can be verified quickly; the set of problems with this property is called NP. If the problem can be solved quickly (in polynomial time), then so can every problem in NP. Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly is one of the principal unsolved problems in computer science today. While a method for computing the solutions to NP-complete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. An expert programmer should be able to recognize an NP-complete problem so that he or she does not unknowingly waste time trying to solve a problem which so far has eluded generations of computer scientists. Instead, NP-complete problems are often addressed by using approximation algorithms.
- Der Begriff NP-Vollständigkeit ist ein Begriff aus der Komplexitätstheorie der Theoretischen Informatik, der im Jahre 1971 von Stephen A. Cook durch den Satz von Cook eingeführt wurde. Er zeichnet spezielle formale Sprachen der Komplexitätsklasse NP aus. So werden solche Sprachen NP-vollständig genannt, die – intuitiv gesprochen – die vollständige Schwierigkeit aller Sprachen aus der Komplexitätsklasse NP in sich tragen. Der Begriff benötigt eine Rechtfertigung in dem Sinn, dass überhaupt wenigstens eine derartige Sprache existiert. Die wesentliche Leistung von Cook bestand zunächst darin, diesen Nachweis erbracht zu haben. Heute existieren wesentlich einfachere Nachweise für die Existenz einer solchen Sprache, allerdings sind die dafür verwendeten Sprachen sehr künstlich. Cooks Verdienst besteht also auch darin, für eine besonders interessante Sprache diesen Nachweis erbracht zu haben. Aufbauend auf der Arbeit von Cook konnte Richard Karp im Jahre 1972 eine weitere bahnbrechende Arbeit vorlegen, die der Theorie der NP-Vollständigkeit zu noch größerer Popularität verhalf. Karps Verdienst besteht darin, die Technik der Polynomialzeitreduktion konsequent genutzt zu haben, um für weitere 21 populäre Probleme die NP-Vollständigkeit nachzuweisen. Die Bedeutung der gesamten Theorie begründet sich vor allem auf folgenden Eigenschaften NP-vollständiger Sprachen: Es konnte bisher für keine dieser Sprachen nachgewiesen werden, dass ein Algorithmus existiert, der für ihr Wortproblem in polynomieller Zeit eine korrekte Antwort liefert. Wenn für eine NP-vollständige Sprache ein Algorithmus gefunden wird, der in polynomieller Zeit eine korrekte Antwort liefert, dann kann das Wortproblem für alle Sprachen in der Komplexitätsklasse NP in polynomieller Zeit entschieden werden. 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 complexitat computacional, el conjunt de problemes NP-complets representa el subconjunt de problemes de tipus NP més difícils de resoldre. Aquesta classificació és deguda a que: Qualsevol problema de tipus NP es pot reduir a un problema de tipus NP-complet. Com a conseqüència, trobar una solució en temps polinòmic a un problema NP-complet resoldria qualsevol problema NP en temps polinòmic, resolent el problema P=NP. Un exemple de problema NP-complet és el problema del viatjant de comerç.
- NP-úplné (NP-complete, NPC) problémy jsou takové nedeterministicky polynomiální problémy, na které jsou polynomiálně redukovatelné 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 deterministický polynomiální 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 Mathematics Institute 24. května 2000, za rozhodnutí vztahu nabízí 1 000 000 dolarů.
- 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 de NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico (y por lo tanto, si se demuestra que para un problema NP-completo no existe solución en tiempo polinómico, ninguno de los problemas NP tendrá solución). 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 2-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición.
- Laskettavuusteoriassa NP-täydelliset ongelmat ovat laskennallisesti erittäin vaativia ongelmia. Ne ovat luokan NP vaikeimmat ongelmat. Polynomiaikaisen ratkaisun löytyminen NP-täydelliseen ongelmaan deterministisellä Turingin koneella (tai millä tahansa nykyisellä tietokoneella) johtaisi polynomiaikaisen ratkaisun olemassaoloon kaikille muillekin luokan NP ongelmille. Tämä tarkoittaisi sitä, että P=NP, eli kaikki epädeterministisellä Turingin koneella polynomiaalisessa ajassa ratkeavat ongelmat ovat myös deterministisellä Turingin koneella polynomiaalisessa ajassa ratkeavia. NP-täydellisten ongelmien ratkaisemiseen tunnetaan ainoastaan eksponentiaalisen ajan vieviä algoritmeja. Yleisesti asiantuntijat ovat sitä mieltä, että P≠NP. Tätä ei kuitenkaan ole pystytty todistamaan. Jos P≠NP, avoin ongelma on myös, onko luokan NP kaikille ongelmille olemassa jokin ratkaisu joka vie vähemmän kuin eksponentiaalisen ajan. Tunnettuja NP-täydellisiä ongelmia ovat mm. kauppamatkustajan ongelma, Hamiltonin syklin tai polun löytäminen graafista, Boolen lausekkeiden toteutuvuusongelma ja graafin väritys.
- Questa pagina fornisce una descrizione tecnica dei problemi NP-completi. Per una introduzione divulgativa, vedi Classi di complessità P ed NP. Nella Teoria della Complessità i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi non deterministici a 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.
- NP完全問題（えぬぴーかんぜんもんだい、NP-complete problem）は、クラスNP（Non-deterministic Polynomial）に属する問題でかつ、クラスNPのすべての問題から多項式時間帰着可能な問題である。すなわち、NPに属する問題のうちでNP困難なものである。クラスNPに含まれる問題で、あるNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の多くがこの定理によって充足可能性問題より導かれたものである。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明された。
- NP-volledigheid is een concept uit de complexiteitstheorie. Het is een beschrijving van het inzicht uit de jaren 1970 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 als en slechts als het probleem tot de verzameling NP behoort. elk ander probleem in NP naar dit probleem kan worden gereduceerd.
- Problem NP-zupełny (NPC) czyli problem zupełny 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 czasie wielomianowym 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ż <math>P\not=NP\,</math> (nie udowodniono także przeciwnie - że <math>P=NP\,</math>), 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 problemu, nikomu się to nie udało. Pytanie związane z problemami NP-zupełnymi ma szczególne znaczenie w kryptografii - rozwiązanie któregokolwiek problemu NP-zupełnego w czasie wielomianowym (a zatem rozwiązanie ich wszystkich) umożliwiłoby między innymi szybkie łamanie szyfru RSA (jednego z najbardziej popularnych szyfrów aktualnie stosowanych) - opiera się on na założeniu, że problem podziału dowolnej liczby na czynniki pierwsze nie jest problemem wielomianowym. Problem ten jest w NP, ale nie udowodniono jego NP-trudności. Problem nie może być jednocześnie NP-zupełny i CoNP-zupełny, chyba że <math>NP=CoNP\,</math>.
- Na teoria da complexidade computacional, a classe de complexidade NP-completo é o subconjunto dos problemas de decisão em 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 poderia ser utilizado 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.
- В теории алгоритмов NP-полная задача — это такая задача из класса NP, к которой можно свести любую другую задачу из класса NP. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».
- NP-fullständiga tal (på engelska NP complete) ä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. De NP-fullständiga talen ingår i klassen NP, vilket innebär att tiden som behövs för att lösa ett problem snabbt växer till årmiljoner när problemets omfattning ökar (vilket presenteras bland annat i exemplet med det ökande antalet städer i handelsresandeproblemet). Ett annat välkänt exempel på NP-fullständiga problem är Hamiltons problem. Ingen har hittills funnit något sätt att lösa NP-fullständiga problem med en algoritm (alltså på ett enklare sätt än genom att testa alla tänkbara lösningar), men ingen har heller bevisat att det inte går. Ett problem är NP-fullständigt om det har egenskapen att om det finns en polynomiell deterministisk algoritm för problemet, så finns en polynomiell deterministisk algoritm för alla problem i NP. Bland de NP-fullständiga problemen återfinns många viktiga vardagsproblem (optimeringsproblem) t ex industriell logistikoptimering, schemaläggningsproblem och packningsproblem. För många av dessa svåra problem finns dock lösningar som ger bevisbart goda approximationer, och i praktiken används ofta de i brist på exakta lösningar.
- NP-повна задача — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час.
- 在計算複雜度理論的世界中，NPC問題，又稱NP完全問題或NP完備問題，是NP（非決定性多項式時間）中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。許多人推測P與NPC沒有交集。理由是因若任何NPC問題得到多項式時間的解法，那此解法就可應用在所有NP問題上。更詳細的定義容下敘述。 一個NPC問題的例子是子集合加總問題，題目為 給予一個有限數量的整數集合，找出任何一個此集合的非空子集且此子集內整數和為零。 意即：I是一個包括若干整數的集合，找出任一一个I′⊂I且∑ I′ = 0 這個問題的答案非常容易驗證，但沒有任何一個夠快的方法可以在合理的時間內（意即多項式時間）找到答案。只能一個個將它的子集取出來一一測試，它的時間複雜度是Ο（2），n是此集合的元素數量。
|
| rdfs:comment
|
- In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC, with NP standing for nondeterministic polynomial time), is a class of problems having two properties Any given solution to the problem can be verified quickly; the set of problems with this property is called NP. If the problem can be solved quickly (in polynomial time), then so can every problem in NP.
- Der Begriff NP-Vollständigkeit ist ein Begriff aus der Komplexitätstheorie der Theoretischen Informatik, der im Jahre 1971 von Stephen A. Cook durch den Satz von Cook eingeführt wurde. Er zeichnet spezielle formale Sprachen der Komplexitätsklasse NP aus. So werden solche Sprachen NP-vollständig genannt, die – intuitiv gesprochen – die vollständige Schwierigkeit aller Sprachen aus der Komplexitätsklasse NP in sich tragen.
- En complexitat computacional, el conjunt de problemes NP-complets representa el subconjunt de problemes de tipus NP més difícils de resoldre. Aquesta classificació és deguda a que: Qualsevol problema de tipus NP es pot reduir a un problema de tipus NP-complet. Com a conseqüència, trobar una solució en temps polinòmic a un problema NP-complet resoldria qualsevol problema NP en temps polinòmic, resolent el problema P=NP.
- NP-úplné (NP-complete, NPC) problémy jsou takové nedeterministicky polynomiální problémy, na které jsou polynomiálně redukovatelné 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.
- 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.
- Laskettavuusteoriassa NP-täydelliset ongelmat ovat laskennallisesti erittäin vaativia ongelmia. Ne ovat luokan NP vaikeimmat ongelmat. Polynomiaikaisen ratkaisun löytyminen NP-täydelliseen ongelmaan deterministisellä Turingin koneella (tai millä tahansa nykyisellä tietokoneella) johtaisi polynomiaikaisen ratkaisun olemassaoloon kaikille muillekin luokan NP ongelmille.
- Questa pagina fornisce una descrizione tecnica dei problemi NP-completi. Per una introduzione divulgativa, vedi Classi di complessità P ed NP.
- NP-volledigheid is een concept uit de complexiteitstheorie. Het is een beschrijving van het inzicht uit de jaren 1970 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 als en slechts als het probleem tot de verzameling NP behoort. elk ander probleem in NP naar dit probleem kan worden gereduceerd.
- Problem NP-zupełny (NPC) czyli problem zupełny 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.
- Na teoria da complexidade computacional, a classe de complexidade NP-completo é o subconjunto dos problemas de decisão em 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.
- В теории алгоритмов NP-полная задача — это такая задача из класса NP, к которой можно свести любую другую задачу из класса NP.
- NP-fullständiga tal (på engelska NP complete) ä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 та всі задачі з класу NP можна звести до неї за поліноміальний час.
|
![[RDF Data]](/statics/sw-cube.png)
