| 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)
|
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
![[RDF Data]](/fct/images/sw-rdf-blue.png)