| dbo:abstract
|
- La teoria de complexitat computacional és part de la teoria de la computació, que estudia els recursos necessaris durant el càlcul per resoldre un problema donat. Els recursos més habituals són temps (quantes passes calen per resoldre el problema) i espai (quanta memòria es necessita per resoldre el problema). En aquesta teoria, la classe P consisteix en tots els problemes de decisió que poden ser resolts en una màquina seqüencial determinista en un espai de temps que és polinòmic respecte la mida de les entrades; la classe NP la formen aquells problemes de decisió els quals la seva solució positiva es pot verificar en un temps polinòmic donada la informació adient, o equivalentment, les seves solucions poden ser trobades en un temps polinòmic en una màquina . Donat això, la qüestió que queda oberta és sobre la relació entre aquestes dues classes: P és igual a NP? És un dels problemes del mil·lenni, i l'Institut Clay de Matemàtiques ofereix un milió de dòlars a qui ho resolgui. Un paper important en aquesta discussió el té el conjunt dels problemes NP-complets, que es poden descriure com els problemes més durs dels NPs. Més acuradament, qualsevol problema NP, mitjançant una transformació eficient (de tipus polinòmic en el temps), es pot expressar com un problema NP-complet. D'aquesta forma, si algú troba una solució eficient (en termes polinòmics) per qualsevol problema NP-complet, llavors tots els problemes NP poden ser solucionats eficientment i a més ha de pertànyer al grup P, i es demostraria per tant que P = NP. (Vegeu NP-complet per la definició exacta). La majoria de científics en Informàtica creuen que la relació entre les classe P, NP i NP-complet és com es mostra a la figura, amb les classes P i NP-complet disjuntes. En essència, la qüestió P = NP pregunta: si una solució positiva per un problema de SÍ/NO pot ser verificada ràpidament, poden calcular-se igual de ràpidament les respostes? Es presenta a continuació un exemple: Donat un conjunt d'enters, existeix algun subconjunt que sumi 0? Per exemple, donat el conjunt {-2, -3, 8, 15, -10} existeix algun subconjunt que doni 0? La resposta es SÍ, tot i que pot costar un cert temps per trobar un subconjunt que ho faci - i si el conjunt és gran, es pot tardar molt de temps a trobar-lo. Per altra banda, si algú afirma que la resposta és "SÍ, perquè {-2, -3, -10, 15} sumen zero", llavors podem comprovar-ho amb molt poques operacions simples. Verificar que un conjunt suma zero és molt més ràpid que trobar el subconjunt de la primera solució. La informació necessària per verificar una solució positiva s'anomena certificat. Podem concloure que donat el certificat adient, respostes positives al nostre problema es poden verificar ràpidament (en temps polinòmic) i és per això que aquest problema pertany a la classe NP. La restricció SÍ/NO als problemes no dona cap diferència; inclús si es permeten respostes més complicades, el problema resultant és equivalent. (ca)
- إن العلاقة بين مسائل التعقيد كثيرة الحدود وكثير حدود غير قطعي هي مسألة غير محلولة في المعلوماتية النظرية. وهي تعتبر من أهم المسائل في هذا الحقل وقد عرض معهد كلاي للرياضيات جائزة مقدارها مليون دولار أمريكي لأول برهان صحيح لهذه المسألة. جوهر المسألة في أنه إذا كان من الممكن التأكد من الجواب الصحيح لمسألة ما بعد الحصول عليه في الزمن الخطي فهل من الممكن أيضا حساب هذه الأجوبة ذاتها بسرعة؟ خذ على سبيل المثال مسألة مجموع المجموعات الجزئية، وهو مثال على مسألة من السهل التحقق من صحة جوابها، لكن عملية حساب الجواب نفسه يعتبر (هذا الأمر غير مبرهن بعد) من الأمور الصعبة. على سبيل المثال هل يوجد مجموعة جزئية من المجموعة التالية {2−, 3−, 15, 14, 7, 10−} يكون مجموع عناصرها مساويا للصفر؟ الجواب بكل بساطة هو نعم، لأن المجموعة الجزئية {2−, 3−,10−, 15} مجموعها صفر وهو أمر من الممكن التحقق منه بكل بساطة بجمع العناصر. لكن إن عملية إيجاد كل مجموعة جزئية من المجموعة الأساسية يكون مجموع جميع عناصرها ينتهي إلى الصفر يأخذ وقتا طويلا. (ar)
- Problém P versus NP je důležitý otevřený problém v teoretické informatice; označuje se tak otázka, zda jsou P a NP totožné. Zjednodušeně řečeno jde o otázku, zda každý problém, u kterého dokáže počítač rychle ověřit správnost nabídnutého řešení, dokáže počítač také sám rychle vyřešit. Všeobecně se předpokládá, že platí P ≠ NP, tedy že existují úlohy, které je složitější vyřešit než ověřit platnost řešení. Důkaz však stále nebyl nalezen a tento problém je zařazený mezi sedm tzv. problémů tisíciletí. (cs)
- Το Πρόβλημα P vs NP είναι ένα σημαντικό ανοικτό πρόβλημα στην επιστήμη των υπολογιστών. Στην απλή διατύπωση του το ερώτημα που θέτει είναι, εάν κάθε πρόβλημα του οποίου η ύπαρξη λύσης μπορεί να επιβεβαιωθεί γρήγορα από έναν υπολογιστή μπορεί επίσης και να επιλυθεί γρήγορα από τον υπολογιστή. Ουσιαστικά, αναφέρεται για πρώτη φορά σε μια επιστολή που γράφτηκε το 1956 από τον Κουρτ Γκέντελ στον Τζον φον Νόιμαν. Ο Γκέντελ ρώτησε αν ένα ορισμένο NP πλήρες πρόβλημα (το οποίο σημαίνει ότι μια οποιαδήποτε λύση μπορεί εύκολα να ελεγχθεί για το αν ικανοποιεί τις συνθήκες του προβλήματος) θα μπορούσε να λυθεί σε τετραγωνικό ή γραμμικό χρόνο. Η ακριβής δήλωση του προβλήματος P vs NP εισήχθη το 1971 από τον στη δημοσίευσή του «Η πολυπλοκότητα θεωρημάτων αποδεικτικών διαδικασιών» και θεωρείται από πολλούς ως το πιο σημαντικό ανοικτό πρόβλημα στον τομέα αυτό. Πρόκειται για ένα από τα επτά (Millennium Prize) από το (Clay Mathematics Institute) με αμοιβή 1 εκατομμύριο δολάρια για την πρώτη σωστή λύση. Ο όρος γρήγορα, που χρησιμοποιήθηκε παραπάνω, δηλώνει την ύπαρξη ενός αλγορίθμου για μια διαδικασία ή οποία τρέχει σε πολυωνυμικό χρόνο. Η γενική κλάση ερωτημάτων για το οποίο κάποιος αλγόριθμος δίνει την απάντηση σε πολυωνυμικό χρόνο ονομάζεται "κλάση P" ή απλούστερα "". Για κάποια ερωτήματα δεν υπάρχει γνωστός τρόπος για την γρήγορη εύρεση απάντησης, αλλά αν κάποιος διαθέτει πληροφορίες που να αποδεικνύουν ποια είναι η απάντηση, είναι δυνατό να επιβεβαιώσει την απάντηση γρήγορα. Η κλάση των προβλημάτων που μπορούν να "επιβεβαιωθούν" σε πολυωνυμικό χρόνο ονομάζεται κλάση . Μια περίπτωση αποτελεί το , ένα παράδειγμα προβλήματος που είναι εύκολο να επιβεβαιωθεί,του οποίου,όμως, η λύση μπορεί να είναι δύσκολο να υπολογιστεί. Δοθέντος ενός συνόλου ακεραίων, υπάρχει κάποιο μη κενό υποσύνολο που να αθροίζει στο 0; Για παράδειγμα, υπάρχει υποσύνολο του συνόλου {−2, −3, 15, 14, 7, −10} που να αθροίζει στο 0; Η απάντηση "ναι, επειδή το υποσύνολο {−2, −3, −10, 15} αθροίζει στο 0" μπορεί γρήγορα να επιβεβαιωθεί με τρεις προσθέσεις. Ωστόσο,δεν υπάρχει γνωστός αλγόριθμος που να βρίσκει τέτοια υποσύνολα σε πολυωνυμικό χρόνο (υπάρχει ένας, παρόλα αυτά, σε εκθετικό χρόνο, που αποτελείται απο 2n-n-1 προσπάθειες), αλλά τέτοιος αλγόριθμος υπάρχει αν P = NP. Συνεπώς το πρόβλημα είναι NP (γρήγορα ελέγξιμο) αλλά όχι απαραίτητα P (γρήγορα επιλύσιμο). Μια απάντηση στο ερώτημα P = NP θα καθόριζε αν προβλήματα που μπορούν να επιβεβαιωθούν σε πολυωνυμικό χρόνο, όπως το πρόβλημα αθροίσματος υποσυνόλου, μπορούν και να λυθούν σε πολυωνυμικό χρόνο. Αν αποδειχθεί ότι P ≠ NP, θα σημαίνει ότι υπάρχει προβλήματα στην NP (όπως τα προβλήματα) τα οποία είναι δυσκολότερο να υπολογιστούν από το να επιβεβαιωθούν. Δεν θα μπορούν να υπολογιστούν σε πολυωνυμικό χρόνο αλλά η απάντηση μπορεί να επιβεβαιωθεί σε πολυωνυμικό χρόνο. Εκτός από το να είναι ένα σημαντικό πρόβλημα στην Θεωρία Υπολογισμού, μια απόδειξη του θα εχει σημαντικές επιρροές στα Μαθηματικά, την Κρυπτογραφία, την μελέτη Αλγορίθμων, την Τεχνητή Νοημοσύνη, την Θεωρία Παιγνίων, την Φιλοσοφία, τα Οικονομικά και πολλά άλλα πεδία. (el)
- Das P-NP-Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Komplexitätstheorie in der theoretischen Informatik. Dabei geht es um die Frage, ob die Menge der Probleme, die schnell lösbar sind, und die Menge der Probleme, bei denen man eine vorgeschlagene Lösung schnell auf Korrektheit überprüfen kann, identisch sind. Schnell lösbar bzw. prüfbar bedeutet hier, dass dafür ein Algorithmus existiert, dessen Rechenaufwand (Zahl der Rechenschritte) abhängig von der Größe der Eingabe durch eine Polynomfunktion beschränkt ist. Die Größe der Eingabe ist hier vereinfacht gesagt die Anzahl der Elemente, die dem Algorithmus eingegeben werden. Beim Sortieren von Karteikarten wäre dies zum Beispiel die Anzahl der Karteikarten. Es ist zwar klar, dass man bei allen schnell lösbaren Problemen auch schnell die Korrektheit einer Lösung überprüfen kann, in der umgekehrten Richtung ist dies jedoch nicht klar: Für manche Probleme existiert zwar ein Algorithmus, der eine vorgeschlagene Lösung schnell überprüfen kann, aber es konnte weder ein Algorithmus gefunden werden, der auch schnell eine korrekte Lösung findet, noch konnte die Unmöglichkeit eines solchen Algorithmus bewiesen werden. Somit ist die Fragestellung ungelöst. Würde man für alle schnell prüfbaren Probleme einen Algorithmus finden, der diese auch schnell löst, so gälte . Könnte für mindestens ein Problem aus gezeigt werden, dass dieses prinzipiell nicht schnell lösbar ist, wäre bewiesen. (de)
- La interrilato inter la rultempaj P kaj estas nesolvita demando en . En esenco la demando ĉu P = NP estas jena: se jes-respondo al povas esti kontrolita en polinoma tempo, ĉu la respondo povas ankaŭ esti komputita en polinoma tempo? estas problemo kun respondo jes aŭ ne. Solvado estas en polinoma tempo se ĝi estas farata en maksimume c·nk paŝoj, kie n estas longo de la enigo kaj k kaj c estas konstantoj sendependaj de la enigo. Konsideru, ekzemple, la , kiu estas ekzemplo de problemo kiu estas facila al kontroli, sed kiu estas kredita (sed ne pruvita) al esti malfacila al komputi. Por donita aro de entjeroj, ĉu estas iu nemalplena subaro de ĝi kies sumo estas 0? La problemo estas decida problemo ĉar la respondo estas jes (la subaro ekzistas) aŭ ne (ne ekzistas). Ekzemple, ĉu estas subaro de la aro {−2, −3, 15, 14, 7, −10} kies sumo estas 0? La respondo estas jesa en ĉi tio okazo, ĉar (−2)+(−3)+15+(−10)=0. Ĝi povas esti rapide kontrolita per kelkaj adicioj. Tamen, trovado de ĉi tia subaro povas preni multe pli longan tempon. La informo bezonata por kontroli pozitivan respondon estas ankaŭ nomata kiel dokumento. Kun donita ĝusta dokumento, la jesa respondo al la problemo povas esti kontrolita en polinoma tempo, tiel la problemo estas en NP. La demando ĉu P = NP demando devas difini ĉu problemoj similaj al la subara suma problemo estas facile (en polinoma tempo) komputeblaj. Se P ≠ NP, do iuj NP problemoj estas signife "pli pezaj" por komputi ol por kontroli. La limigo al jes/ne problemoj estas negrava; la rezultanta problemo kun pli komplika respondo estas permesata, la demando ĉu = estas ekvivalenta al ĉu P = NP. (eo)
- P vs NP problema informatika teorikoan konpondu gabeko problema garrantzitsua da. Termino informaletan, konponbidea azkar egiazta daitekeen arazoak ea azkar konpondu daitekeen ere galdetzen du. Goian erabilitako azkar termino informalak denbora polinomikoan exekutatzen den zeregina ebazten duen algoritmo baten existentzia esan nahi du; hau da, zeregina burutzeko denbora funtzio polinomiko gisa aldatzen da algoritmoaren sarreraren tamainaren arabera (esaterako,denbora esponentzialaren aurkakoa). Algoritmo batzuek denbora polinomikoan erantzuna eman dezaketen galderen klase orokorra "P" edo "P klasea" da. Galdera batzuetarako, ez dago erantzuna azkar aurkitzeko modu jakinik, baina, erantzuna zein den erakusten duen informazioa ematen bazaio, erantzuna azkar egiaztatzeko aukera dago. Erantzuna denbora polinomikoan egiazta daitekeen galderen klasea NP da, «denbora polinomiko ez determinista» esan nahi duena P versus NP galderari erantzunak denbora polinomikoan egiazta daitezkeen problemak denbora polinomikoan ere ebatzi daitezkeen zehaztuko luke. Gertatzen bada P ≠ NP, uste zabala duen bezala, NPn zenbatzea baino zailagoa den problemak badirela esan nahiko luke, eta ezingo lirateke denbora polinomikoan ebatzi, baina erantzuna denbora polinomikoan egiazta zitekeen. Arazoari informatikako arazo ireki garrantzitsuena deitu izan zaio. Teoria konputazionalean arazo garrantzitsu bat izateaz gain, proba batek inplikazio sakonak izango lituzke matematika, kriptografia, algoritmoen ikerketa, adimen artifiziala, jokoen teoria, multimedia prozesatzea, filosofia, ekonomia eta beste hainbat esparrutan. Konplexutasun konputazionalean aztertzen diren baliabideak hauek dira: – Denbora: algoritmo batek arazo bat ebazteko erabiltzen duen exekuzio-urratsen arteko hurbilketa baten bidez. – Espazioa: arazoa ebazteko erabilitako memoria kopuruaren hurbilketa. Arazoak multzo edo konplexutasun klaseetan sailkatzen dira (L, NL, P, PCOlea, NP, NP-Complete, NP Hard...). Artikulu hau P eta NP klaseetan zentratuko da. Clay Mathematics Institute-k hautatutako zazpi Millennium Prize Problemetako bat da, eta horietako bakoitzak 1.000.000 USDko saria du lehen irtenbide zuzenarentzat. (eu)
- La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder. En esencia, la pregunta ¿es P = NP completo? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestas rápidamente? Los recursos comúnmente estudiados en complejidad computacional son: – El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema. – El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema. Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto, NP, NP-Completo, NP Duro...). Este artículo se centrará en las clases P y NP. Se considera el problema más importante en este campo, el Clay Mathematics Institute ha ofrecido un premio de un millón de dólares estadounidenses para quien desarrolle la primera demostración correcta. (es)
- Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable. Ce problème est également le troisième problème de Smale. Très schématiquement, il s'agit de déterminer si le fait de pouvoir vérifier rapidement une solution à un problème implique de pouvoir la trouver rapidement ; ou encore, si ce que nous pouvons trouver rapidement lorsque nous avons de la chance peut être trouvé aussi vite par un calcul intelligent. Plus précisément, il s'agit de savoir si la classe de complexité P des problèmes de décision admettant un algorithme de résolution s'exécutant en temps polynomial sur une machine de Turing est équivalente à la classe de complexité NP des problèmes de décision dont la vérification du résultat, une fois celui-ci connu, demande un temps polynomial. Un algorithme qui demande un temps d'exécution polynomial est généralement considéré comme « rapide » (par rapport à un temps d'exécution exponentiel par exemple). À condition que le degré du polynôme issu du caractère polynomial de l'algorithme soit raisonnable, les conséquences de P = NP pourraient être considérables dans de nombreux domaines : cryptologie, informatique, mathématiques, ingénierie, économie. S'il était prouvé que P = NP, alors la résolution de tous les autres problèmes posés par l’Institut Clay pourrait devenir évidente. S'il était au contraire avéré que P ≠ NP, cela signifierait qu'une large classe de problèmes seraient presque sûrement définitivement hors d'atteinte du calcul dans un temps raisonnable (ou nécessiteraient le développement d'architectures différentes de celles des machines de Turing). (fr)
- The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time). The general class of questions for which some algorithm can provide an answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is NP, which stands for "nondeterministic polynomial time". An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turns out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time. The problem has been called the most important open problem in computer science. Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution. (en)
- Masalah P versus NP adalah permasalahan besar yang merupakan salah satu . Problema ini menanyakan apakah setiap masalah yang solusinya dapat segera diverifikasi (secara teknis, diverifikasi dalam ) juga dapat dipecahkan dengan cepat (sekali lagi, dalam waktu polinomial). Isu yang mendasari masalah ini pertama kali dibahas pada tahun 1950-an, dalam surat dari John Forbes Nash Jr. ke National Security Agency, dan dari Kurt Gödel ke John von Neumann. Pernyataan terperinci masalah P versus NP diperkenalkan pada tahun 1971 oleh Stephen Cook dalam paper seminarnya "Kompleksitas prosedur pembuktian teorema" dan dianggap oleh banyak orang sebagai masalah terbuka terpenting dalam bidang ilmu komputer. Problema ini adalah salah satu dari tujuh Masalah Milenium yang dipilih untuk membawa hadiah senilai US $ 1.000.000 bagi pencetus solusi pertama yang benar. Istilah informal dengan cepat, yang digunakan di atas, berarti adanya algoritme yang memecahkan tugas yang berjalan dalam , sehingga waktu untuk menyelesaikan tugas bervariasi sebagai fungsi polinom pada ukuran input ke algoritme (berlawanan dengan, katakanlah, ). Kelas umum pertanyaan yang beberapa algoritmanya dapat memberikan jawaban dalam waktu polinomial disebut "kelas P" atau hanya "". Untuk beberapa pertanyaan, tidak ada cara yang diketahui untuk menemukan jawaban dengan cepat, tetapi jika ada informasi yang menunjukkan jawabannya, mungkin untuk memverifikasi jawabannya dengan cepat. Kelas pertanyaan yang jawabannya dapat diverifikasi dalam waktu polinom disebut , yang berarti "waktu polinomial nondeterministik". (in)
- Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale. Nonostante ci sia in palio un premio di un milione di dollari il problema rimane ancora senza una soluzione (si tratta di uno dei problemi del millennio). (it)
- P≠NP予想（P≠NPよそう、英: P is not NP）は、計算複雑性理論（計算量理論）における予想 (未解決問題) の1つで、「クラスPとクラスNPが等しくない」というものである。P対NP問題（PたいNPもんだい、英: P versus NP）と呼ばれることもある。 理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。 (ja)
- P-NP 문제(-問題, 영어: P versus NP problem)는 복잡도 종류 P와 NP가 같은지에 대한 이론 컴퓨터 과학의 미해결 문제로, 간략하게 말해 답을 빠르게 검산할 수 있는 문제는 빠르게 풀릴 수도 있는가를 묻고 있다. 여기서 빠르게라는 말은 다항 시간 안에 작업을 수행하는 알고리즘이 존재한다는 의미로, 즉 걸리는 시간이 알고리즘에 입력하는 크기의 다항함수(이를테면, 지수 함수와 반대이다.)가 된다는 뜻이다. 다항 시간 안에 답을 구하는 알고리즘이 존재하는 문제들을 "P"라고 하며, P는 결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제류이다. 어떤 문제들은 빠르게 답을 찾을 수 있는 방법이 알려져 있지는 않지만 답이 제공되었을 때 빠르게 검산하는 것은 가능한데, 다항 시간 안에 답을 검산할 수 있는 문제들을 "NP"라고 한다. NP는 비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제류이며 "nondeterministic polynomial time"의 약자이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분류가 된다. P-NP 문제가 해결되면 다항 시간 안에 답을 검산할 수 있는 문제들이 다항 시간 안에 답을 구할 수도 있는지를 알 수 있게 된다. 현재 대부분의 학자들은 P ≠ NP일 것으로 예상하는데, 만약 P ≠ NP인 것으로 드러난다면 NP인 문제들 중에는 풀이법을 확인하는 것보다 답을 구하는 게 더 어려운 경우가 있다는 것을 의미한다. 그러한 문제들은 다항시간 안에 풀 수 없지만 다항시간 안에 답을 검산하는 것은 가능하다. P-NP 문제는 컴퓨터 과학에서 가장 중요한 미해결 난제이자, 클레이 수학연구소에서 정한 7개의 밀레니엄 문제 중 하나로 100만 달러의 상금이 걸려있다. 계산 이론에서의 중요성을 차치하고서도, 문제의 증명은 수학, 암호학, 알고리즘 연구, 인공지능, 게임이론, 멀티미디어 프로세싱, 철학, 경제학 등 다양한 분야에 깊은 영향을 끼칠 것으로 예상된다. (ko)
- P=NP? är ett problem inom datavetenskap. Problemet handlar om huruvida två klasser av beslutsproblem, P och NP, är samma klass eller ej. Problemet är inte löst och anses av vissa som det viktigaste inom datavetenskapen. Problemet lyder, Finns det något beslutsproblem, vars lösning kan verifieras på polynomiell tid, dvs det ligger i komplexitetsklassen NP, men som inte kan lösas på polynomiell tid, dvs det ligger inte i komplexitetsklassen P? Problemet är viktigt inom datavetenskapen, eftersom många svåra problem finns i klassen NP. Problemet ger viktig information om hur mycket tid man kan förvänta sig att dessa problem borde ta. Clay Mathematics Institute valde problemet som ett av millennieproblemen, så den som löser problemet vinner 1 000 000 dollar. Ett förenklat sätt att förklara problemet är: om du har ett problem där det går fort att kontrollera att en lösning är korrekt, finns det alltid då ett sätt att hitta en lösning snabbt också? (sv)
- O problema "P versus NP" é o principal problema aberto da Ciência da Computação. Possui também enorme relevância em campos que vão desde a Engenharia até a criptografia aplicada aos serviços militares e às transações comerciais e financeiras via Internet. (pt)
- Вопрос о равенстве классов сложности P и NP (в русскоязычных источниках также известный как проблема перебора) — это одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас. Отношения между классами P и NP рассматриваются в разделе теории алгоритмов, который называется теорией вычислительной сложности. Она изучает ресурсы, необходимые для решения некоторой задачи. Наиболее общие ресурсы — это время (сколько нужно сделать шагов) и память (сколько памяти потребуется для решения задачи). Проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США. (ru)
- У теорії алгоритмів питання про рівність класів складності P і NP є однією з центральних відкритих проблем вже більше трьох десятиліть. Якщо на нього буде дано позитивну відповідь, це означатиме, що теоретично можливо вирішувати багато складних завдань істотно швидше, ніж зараз. (uk)
- P/NP问题是理论信息学中计算复杂度理论领域至今未解决的问题，名列克雷数学研究所七題千禧年大奖难题。P/NP问题包括复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和各自提出了以下问题，即复杂度类P和NP是否等价（P=NP?）。 (zh)
|
| rdfs:comment
|
- Problém P versus NP je důležitý otevřený problém v teoretické informatice; označuje se tak otázka, zda jsou P a NP totožné. Zjednodušeně řečeno jde o otázku, zda každý problém, u kterého dokáže počítač rychle ověřit správnost nabídnutého řešení, dokáže počítač také sám rychle vyřešit. Všeobecně se předpokládá, že platí P ≠ NP, tedy že existují úlohy, které je složitější vyřešit než ověřit platnost řešení. Důkaz však stále nebyl nalezen a tento problém je zařazený mezi sedm tzv. problémů tisíciletí. (cs)
- Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale. Nonostante ci sia in palio un premio di un milione di dollari il problema rimane ancora senza una soluzione (si tratta di uno dei problemi del millennio). (it)
- P≠NP予想（P≠NPよそう、英: P is not NP）は、計算複雑性理論（計算量理論）における予想 (未解決問題) の1つで、「クラスPとクラスNPが等しくない」というものである。P対NP問題（PたいNPもんだい、英: P versus NP）と呼ばれることもある。 理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。 (ja)
- O problema "P versus NP" é o principal problema aberto da Ciência da Computação. Possui também enorme relevância em campos que vão desde a Engenharia até a criptografia aplicada aos serviços militares e às transações comerciais e financeiras via Internet. (pt)
- У теорії алгоритмів питання про рівність класів складності P і NP є однією з центральних відкритих проблем вже більше трьох десятиліть. Якщо на нього буде дано позитивну відповідь, це означатиме, що теоретично можливо вирішувати багато складних завдань істотно швидше, ніж зараз. (uk)
- P/NP问题是理论信息学中计算复杂度理论领域至今未解决的问题，名列克雷数学研究所七題千禧年大奖难题。P/NP问题包括复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和各自提出了以下问题，即复杂度类P和NP是否等价（P=NP?）。 (zh)
- إن العلاقة بين مسائل التعقيد كثيرة الحدود وكثير حدود غير قطعي هي مسألة غير محلولة في المعلوماتية النظرية. وهي تعتبر من أهم المسائل في هذا الحقل وقد عرض معهد كلاي للرياضيات جائزة مقدارها مليون دولار أمريكي لأول برهان صحيح لهذه المسألة. جوهر المسألة في أنه إذا كان من الممكن التأكد من الجواب الصحيح لمسألة ما بعد الحصول عليه في الزمن الخطي فهل من الممكن أيضا حساب هذه الأجوبة ذاتها بسرعة؟ (ar)
- La teoria de complexitat computacional és part de la teoria de la computació, que estudia els recursos necessaris durant el càlcul per resoldre un problema donat. Els recursos més habituals són temps (quantes passes calen per resoldre el problema) i espai (quanta memòria es necessita per resoldre el problema). P és igual a NP? És un dels problemes del mil·lenni, i l'Institut Clay de Matemàtiques ofereix un milió de dòlars a qui ho resolgui. La restricció SÍ/NO als problemes no dona cap diferència; inclús si es permeten respostes més complicades, el problema resultant és equivalent. (ca)
- Το Πρόβλημα P vs NP είναι ένα σημαντικό ανοικτό πρόβλημα στην επιστήμη των υπολογιστών. Στην απλή διατύπωση του το ερώτημα που θέτει είναι, εάν κάθε πρόβλημα του οποίου η ύπαρξη λύσης μπορεί να επιβεβαιωθεί γρήγορα από έναν υπολογιστή μπορεί επίσης και να επιλυθεί γρήγορα από τον υπολογιστή. Εκτός από το να είναι ένα σημαντικό πρόβλημα στην Θεωρία Υπολογισμού, μια απόδειξη του θα εχει σημαντικές επιρροές στα Μαθηματικά, την Κρυπτογραφία, την μελέτη Αλγορίθμων, την Τεχνητή Νοημοσύνη, την Θεωρία Παιγνίων, την Φιλοσοφία, τα Οικονομικά και πολλά άλλα πεδία. (el)
- Das P-NP-Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Komplexitätstheorie in der theoretischen Informatik. Dabei geht es um die Frage, ob die Menge der Probleme, die schnell lösbar sind, und die Menge der Probleme, bei denen man eine vorgeschlagene Lösung schnell auf Korrektheit überprüfen kann, identisch sind. Schnell lösbar bzw. prüfbar bedeutet hier, dass dafür ein Algorithmus existiert, dessen Rechenaufwand (Zahl der Rechenschritte) abhängig von der Größe der Eingabe durch eine Polynomfunktion beschränkt ist. Die Größe der Eingabe ist hier vereinfacht gesagt die Anzahl der Elemente, die dem Algorithmus eingegeben werden. Beim Sortieren von Karteikarten wäre dies zum Beispiel die Anzahl der Karteikarten. (de)
- La interrilato inter la rultempaj P kaj estas nesolvita demando en . En esenco la demando ĉu P = NP estas jena: se jes-respondo al povas esti kontrolita en polinoma tempo, ĉu la respondo povas ankaŭ esti komputita en polinoma tempo? estas problemo kun respondo jes aŭ ne. Solvado estas en polinoma tempo se ĝi estas farata en maksimume c·nk paŝoj, kie n estas longo de la enigo kaj k kaj c estas konstantoj sendependaj de la enigo. La limigo al jes/ne problemoj estas negrava; la rezultanta problemo kun pli komplika respondo estas permesata, la demando ĉu = estas ekvivalenta al ĉu P = NP. (eo)
- P vs NP problema informatika teorikoan konpondu gabeko problema garrantzitsua da. Termino informaletan, konponbidea azkar egiazta daitekeen arazoak ea azkar konpondu daitekeen ere galdetzen du. Goian erabilitako azkar termino informalak denbora polinomikoan exekutatzen den zeregina ebazten duen algoritmo baten existentzia esan nahi du; hau da, zeregina burutzeko denbora funtzio polinomiko gisa aldatzen da algoritmoaren sarreraren tamainaren arabera (esaterako,denbora esponentzialaren aurkakoa). Algoritmo batzuek denbora polinomikoan erantzuna eman dezaketen galderen klase orokorra "P" edo "P klasea" da. Galdera batzuetarako, ez dago erantzuna azkar aurkitzeko modu jakinik, baina, erantzuna zein den erakusten duen informazioa ematen bazaio, erantzuna azkar egiaztatzeko aukera dago. Erantzun (eu)
- La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder. En esencia, la pregunta ¿es P = NP completo? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestas rápidamente? Los recursos comúnmente estudiados en complejidad computacional son: (es)
- Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable. Ce problème est également le troisième problème de Smale. (fr)
- The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time). The general class of questions for which some algorithm can provide an answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions (en)
- Masalah P versus NP adalah permasalahan besar yang merupakan salah satu . Problema ini menanyakan apakah setiap masalah yang solusinya dapat segera diverifikasi (secara teknis, diverifikasi dalam ) juga dapat dipecahkan dengan cepat (sekali lagi, dalam waktu polinomial). (in)
- P-NP 문제(-問題, 영어: P versus NP problem)는 복잡도 종류 P와 NP가 같은지에 대한 이론 컴퓨터 과학의 미해결 문제로, 간략하게 말해 답을 빠르게 검산할 수 있는 문제는 빠르게 풀릴 수도 있는가를 묻고 있다. 여기서 빠르게라는 말은 다항 시간 안에 작업을 수행하는 알고리즘이 존재한다는 의미로, 즉 걸리는 시간이 알고리즘에 입력하는 크기의 다항함수(이를테면, 지수 함수와 반대이다.)가 된다는 뜻이다. 다항 시간 안에 답을 구하는 알고리즘이 존재하는 문제들을 "P"라고 하며, P는 결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제류이다. 어떤 문제들은 빠르게 답을 찾을 수 있는 방법이 알려져 있지는 않지만 답이 제공되었을 때 빠르게 검산하는 것은 가능한데, 다항 시간 안에 답을 검산할 수 있는 문제들을 "NP"라고 한다. NP는 비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제류이며 "nondeterministic polynomial time"의 약자이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분류가 된다. (ko)
- Вопрос о равенстве классов сложности P и NP (в русскоязычных источниках также известный как проблема перебора) — это одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас. Проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США. (ru)
- P=NP? är ett problem inom datavetenskap. Problemet handlar om huruvida två klasser av beslutsproblem, P och NP, är samma klass eller ej. Problemet är inte löst och anses av vissa som det viktigaste inom datavetenskapen. Problemet lyder, Finns det något beslutsproblem, vars lösning kan verifieras på polynomiell tid, dvs det ligger i komplexitetsklassen NP, men som inte kan lösas på polynomiell tid, dvs det ligger inte i komplexitetsklassen P? (sv)
|
