NP (complexity) (original) (raw)
هي قسم(class) لغات، اللغة(language) في سياقنا هذا هي مجموعة سلاسل (strings) من رموز الابجدية (alphabet) ومسألة التقرير (Decision problem) هي باعطانا سلسلة(string) من الرموز هل هي موجودة باللغة ام لا أي: ، ويوجد خوارزمية A بحيث ان A(s)=1 فقط إذا . واللغات التي في NP هي التي يمكن حلها (أي حل مسألة التقرير) بواسطة آلة تيورنغ غير حتمية متعددة الحدود، ولعل هذا القسم من اللغات هو الأهم في نظرية التعقيد الحسابي إذ ان اللغات التي يحتويها تمتد إلى كل فروع علم الحاسوب والنتائج على هذا قسم NP يؤثر في كل علوم الحاسوب. الاسم NP هو اختصار ل- Non deterministic Polynomial time
| Property | Value |
|---|---|
| dbo:abstract | هي قسم(class) لغات، اللغة(language) في سياقنا هذا هي مجموعة سلاسل (strings) من رموز الابجدية (alphabet) ومسألة التقرير (Decision problem) هي باعطانا سلسلة(string) من الرموز هل هي موجودة باللغة ام لا أي: ، ويوجد خوارزمية A بحيث ان A(s)=1 فقط إذا . واللغات التي في NP هي التي يمكن حلها (أي حل مسألة التقرير) بواسطة آلة تيورنغ غير حتمية متعددة الحدود، ولعل هذا القسم من اللغات هو الأهم في نظرية التعقيد الحسابي إذ ان اللغات التي يحتويها تمتد إلى كل فروع علم الحاسوب والنتائج على هذا قسم NP يؤثر في كل علوم الحاسوب. الاسم NP هو اختصار ل- Non deterministic Polynomial time (ar) NP (zkratka nedeterministicky polynomiální) je množina problémů, které lze řešit v polynomiálně omezeném čase na nedeterministickém Turingově stroji - na počítači, který umožňuje v každém kroku rozvětvit výpočet na n větví, v nichž se posléze řešení hledá současně. Ekvivalentně se hovoří o stroji, který na místě rozhodování uhodne správnou cestu výpočtu. Alternativně lze tyto problémy definovat tak, že je to množina problémů, u kterých lze pro dodaný výsledek v polynomiálním čase ověřit jeho správnost (ale obecně nikoliv nalézt řešení v polynomiálním čase). Složitostní třída P je obsažena v NP, ale NP obsahuje velké množství důležitých problémů, zvaných NP-úplné, pro které není znám žádný polynomiální algoritmus. Pravděpodobně nejdůležitějším problémem současné informatiky (patří mezi Problémy milénia) je otázka, zda P = NP. Většina expertů[kdo?] ale věří, že P je vlastní podmnožinou NP. (cs) En complexitat computacional, NP és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb una màquina de Turing no determinista usant una quantitat de temps de computació polinòmic, temps polinòmic. Equivalentment, aquest és el conjunt de problemes els quals la seva solució es pot "verificar" per una màquina de Turing determinista en temps polinòmic. (ca) In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Intuitiv beschrieben, enthält NP die Entscheidungsprobleme, bei denen es für „Ja“-Antworten Beweise gibt, die effizient (in Polynomialzeit) verifiziert werden können. Es kann aber mitunter aufwändig sein, einen solchen Beweis zu finden. Eine alternative Beschreibung von NP ist also die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine (NTM) bezüglich der Eingabelänge in Polynomialzeit gelöst werden können. Hierbei wird eine Instanz mit „Ja“ beantwortet, wenn mindestens eine der möglichen Berechnungen der nichtdeterministischen Turingmaschine dies tut. Besonders interessant sind NP-vollständige Probleme (Probleme, die vollständig für die Klasse NP sind). NP-vollständige Probleme lassen sich vermutlich nicht effizient lösen. Alle bekannten deterministischen Algorithmen für diese Probleme erfordern exponentiellen Rechenaufwand, und es wird stark vermutet, dass es keine effizienteren Algorithmen gibt. Die Bestätigung oder Widerlegung dieser Vermutung ist das P-NP-Problem, eines der wichtigsten offenen Probleme der Informatik. Das vielleicht bekannteste NP-vollständige Problem ist das Problem des Handlungsreisenden. Gelegentlich wird NP fälschlich als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Die Klasse NP definiert aber lediglich eine obere Schranke für die Komplexität der enthaltenen Probleme und enthält auch alle durch eine deterministische Maschine in Polynomialzeit lösbaren Probleme. Richtig ist, dass für NP-vollständige Probleme (und einige weitere in NP) nicht bekannt ist, ob sie deterministisch in Polynomialzeit lösbar sind; man vermutet, dass dies nicht der Fall ist. (de) En teoría de la complejidad computacional, NP es el acrónimo en inglés de nondeterministic polynomial time ("tiempo polinomial no determinista"). Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista. (es) La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« nondeterministic polynomial time »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution. Par exemple, considérons le problème de décision du voyageur de commerce qui, étant donné un entier k et un ensemble de villes séparées par des distances, détermine s'il existe un circuit de longueur inférieure à k qui passe une et une seule fois par toutes les villes. On vérifie « rapidement » qu'une solution candidate, ici un chemin quelconque, est bien solution, c'est-à-dire que c'est bien un circuit de longueur inférieur à k et qu'il passe bien une et seule fois par toutes les villes. L'un des grands problèmes ouverts de l'informatique théorique est le Problème P ≟ NP. (fr) In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine. An equivalent definition of NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine. This definition is the basis for the abbreviation NP; "nondeterministic, polynomial time". These two definitions are equivalent because the algorithm based on the Turing machine consists of two phases, the first of which consists of a guess about the solution, which is generated in a nondeterministic way, while the second phase consists of a deterministic algorithm that verifies whether the guess is a solution to the problem. It is easy to see that the complexity class P (all problems solvable, deterministically, in polynomial time) is contained in NP (problems where solutions can be verified in polynomial time), because if a problem is solvable in polynomial time, then a solution is also verifiable in polynomial time by simply solving the problem. But NP contains many more problems, the hardest of which are called NP-complete problems. An algorithm solving such a problem in polynomial time is also able to solve any other NP problem in polynomial time. The most important P versus NP (“P = NP?”) problem, asks whether polynomial-time algorithms exist for solving NP-complete, and by corollary, all NP problems. It is widely believed that this is not the case. The complexity class NP is related to the complexity class co-NP, for which the answer "no" can be verified in polynomial time. Whether or not NP = co-NP is another outstanding question in complexity theory. (en) NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이다. NP에 속하는 문제는 결정론적 튜링 기계로 다항 시간에 검증이 가능하고, 그 역도 성립한다. 또한 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 문제는 비결정론적 튜링 기계로도 다항 시간 안에 풀 수 있으므로, P 집합은 NP 집합의 부분집합이다. 이때 P가 NP의 진부분집합인지, 혹은 P와 NP가 같은지에 대해서는 아직 알려지지 않았고, 이 문제는 P-NP 문제로 불린다. NP=PCP(log n, O(1)) (ko) NP, de aanduiding voor niet-deterministisch polynomiaal, is een die alle beslissingsproblemen bevat die oplosbaar zijn in polynomiale tijd door een niet-deterministische turingmachine. In de complexiteitstheorie is NP ook bekend als NTIME( nO(1) ) NP kan ook beschouwd worden als de verzameling beslissingsproblemen (te beantwoorden met 'ja' of 'nee') waarvoor een 'ja'-oplossing in polynomiale tijd geverifieerd kan worden door een deterministische turingmachine. De beslissingsproblemen waarvoor een 'nee'-oplossing eenvoudig te controleren is, behoren tot , het complement van NP. (nl) 計算複雑性理論における NP (Non-deterministic Polynomial time)は、複雑性クラスのひとつであり、答えがyesとなるような問いに対して、多項式時間で検証できる証拠が存在する決定問題のクラスである。 (ja) La classe di problemi comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale. La classe NP prende il suo nome dall'abbreviazione di Nondeterministic Polynomial Time. La classe può essere definita in modo alternativo andando a sfruttare le macchine di Turing non deterministiche. Infatti si avrà che dato come un insieme di parole su un alfabeto , allora è nella classe se e solo se esiste una macchina di Turing non deterministica di complessità polinomiale che, per ogni input , ha almeno una computazione che converge. In sostanza qualora esiste una macchina di Turing non deterministica che accetta (quindi converge per ogni input ). Presa una macchina di Turing non deterministica di complessità polinomiale, allora essa accetterà un linguaggio il quale sarà un problema che appartiene alla classe . Tale macchina di Turing dunque, per ogni input avrà fra tutte le possibili computazioni su tale input, una che si arresta. Invece se l'input che si fornisce alla macchina di Turing che accetta non appartiene a quest'ultimo linguaggio, allora si avranno solo computazioni infinite o computazioni massimali non accettanti. Si ha che . Da tale affermazione si evince innanzitutto che tutti i problemi di classe P sono anche problemi di classe NP. A seguito si mostra che la classe può essere caratterizzata come quella classe di problemi per i quali si è in grado di verificare in modo rapido se una possibile soluzione è effettivamente tale. (it) Problem NP (ang. nondeterministic polynomial, niedeterministycznie wielomianowy) – problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga. Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność. Przykładowy problem: Czy jakikolwiek niepusty podzbiór zadanego zbioru (np. ) sumuje się do zera? Trudno znaleźć rozwiązanie tego zagadnienia w czasie wielomianowym. Nasuwający się algorytm sprawdzenia wszystkich możliwych podzbiorów ma złożoność wykładniczą ze względu na liczebność zbioru. Nie wiadomo zatem, czy problem ten jest klasy P. Na pewno natomiast uzyskawszy z zewnątrz kandydata na rozwiązanie (np. ) możemy w liniowym (a zatem wielomianowym) czasie sprawdzić, czy sumuje się do zera. Jest to zatem problem NP. W szczególności wszystkie problemy klasy P są NP, ponieważ można je sprawdzić w czasie wielomianowym. Innymi słowy, klasa P zawiera się nieostro w NP Nie wiadomo natomiast czy istnieje problem NP, który nie jest w klasie P (czyli, czy P różni się od NP lub inaczej albo ). Jest to jeden z problemów milenijnych. (pl) Na teoria da complexidade computacional, NP é o acrônimo em inglês para Tempo polinomial não determinístico (Non-Deterministic Polynomial time) que denota o conjunto de problemas que são decidíveis em tempo polinomial por uma máquina de Turing não-determinística. Uma definição equivalente é o conjunto de problemas de decisão que podem ter seu certificado verificado em por uma máquina de Turing determinística. (pt) В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения). Эквивалентно класс NP включает задачи, которые можно за полиномиальное время решить на недетерминированной машине Тьюринга. Задачи, имеющие полиномиальные по времени алгоритмы решения, можно решать с помощью компьютера значительно быстрее, чем путём прямого перебора, время которого экспоненциально. Это обуславливает практическое значение проблемы о равенстве классов P и NP. (ru) NP betecknar mängden beslutsproblem som kan lösas på polynomiell tid av en Turingmaskin. (sv) Клас складності NP (англ. Complexity class NP) — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний час; тобто, недетермінованими алгоритмами в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що . (uk) 非決定性多项式集合（英語：non-deterministic polynomial，缩写：NP）是计算理论中最重要的集合之一。它包含P和NP-complete。 P問題是指在多项式时间内可以找出解的決定性問題(decision problem)，而NP問題則包含可在多项式时间內驗證其解是否正確，但不保證能在多項式時間內能找出解的決定性問題。NP包含P和NP-complete问题, 因此NP集合中有簡單的問題和不容易快速得到解的難題。 [NP等不等於P?]是一個计算机科学中知名的難題。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/P_np_np-complete_np-hard.svg?width=300 |
| dbo:wikiPageExternalLink | https://archive.org/details/introductiontoth00sips https://web.archive.org/web/20081012155440/http:/www.americanscientist.org/issues/pub/accidental-algorithms |
| dbo:wikiPageID | 21562 (xsd:integer) |
| dbo:wikiPageLength | 19679 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119703601 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:American_Scientist dbr:Nondeterministic_Turing_machine dbr:Primality_test dbr:Big-O_notation dbr:David_Harel dbr:Approximation_algorithm dbr:Decision_problem dbr:Descriptive_complexity_theory dbr:Interactive_proof_system dbr:Intersection dbr:Introduction_to_Algorithms dbr:Thomas_H._Cormen dbr:Space_hierarchy_theorem dbr:Complement_(set_theory) dbr:Concatenation dbr:Clifford_Stein dbr:Co-NP dbr:NP-complete dbr:Complexity_class dbr:Computation_tree dbr:Computational_complexity_theory dbr:Computer_science dbr:P_(complexity) dbr:Probabilistically_checkable_proof dbr:Propositional_logic dbr:Travelling_salesman_problem dbr:EXPTIME dbr:PSPACE dbr:Fork_(system_call) dbr:Formal_language dbr:Mathematical_proof dbc:Complexity_classes dbr:Charles_E._Leiserson dbr:Witness_(mathematics) dbr:Arthur–Merlin_protocol dbr:Boolean_satisfiability_problem dbr:Polynomial_hierarchy dbr:Polynomial_time dbr:Integer dbr:Certificate_(complexity) dbr:Search_problem dbr:Second-order_logic dbr:Set_(mathematics) dbr:Kleene_star dbr:Turing_machine dbr:Subset_sum_problem dbr:Union_(set_theory) dbr:FNP_(complexity) dbr:Fagin's_theorem dbr:Subgraph_isomorphism_problem dbr:NTIME dbr:Time_hierarchy_theorem dbr:Nondeterministic_algorithm dbr:P_versus_NP_problem dbr:Super-polynomial_time dbr:Deterministic_Turing_machine dbr:Integer_factorization_problem dbr:Binary_search dbr:Ronald_L._Rivest dbr:File:P_np_np-complete_np-hard.svg dbr:Yishai_Feldman |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Annotated_link dbt:Cite_book dbt:More_footnotes dbt:Mvar dbt:Reflist dbt:Short_description dbt:Tmath dbt:Isbn dbt:ComplexityClasses dbt:Mathematical_logic dbt:CZoo dbt:Unsolved |
| dct:subject | dbc:Complexity_classes |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | هي قسم(class) لغات، اللغة(language) في سياقنا هذا هي مجموعة سلاسل (strings) من رموز الابجدية (alphabet) ومسألة التقرير (Decision problem) هي باعطانا سلسلة(string) من الرموز هل هي موجودة باللغة ام لا أي: ، ويوجد خوارزمية A بحيث ان A(s)=1 فقط إذا . واللغات التي في NP هي التي يمكن حلها (أي حل مسألة التقرير) بواسطة آلة تيورنغ غير حتمية متعددة الحدود، ولعل هذا القسم من اللغات هو الأهم في نظرية التعقيد الحسابي إذ ان اللغات التي يحتويها تمتد إلى كل فروع علم الحاسوب والنتائج على هذا قسم NP يؤثر في كل علوم الحاسوب. الاسم NP هو اختصار ل- Non deterministic Polynomial time (ar) En complexitat computacional, NP és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb una màquina de Turing no determinista usant una quantitat de temps de computació polinòmic, temps polinòmic. Equivalentment, aquest és el conjunt de problemes els quals la seva solució es pot "verificar" per una màquina de Turing determinista en temps polinòmic. (ca) En teoría de la complejidad computacional, NP es el acrónimo en inglés de nondeterministic polynomial time ("tiempo polinomial no determinista"). Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista. (es) NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이다. NP에 속하는 문제는 결정론적 튜링 기계로 다항 시간에 검증이 가능하고, 그 역도 성립한다. 또한 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 문제는 비결정론적 튜링 기계로도 다항 시간 안에 풀 수 있으므로, P 집합은 NP 집합의 부분집합이다. 이때 P가 NP의 진부분집합인지, 혹은 P와 NP가 같은지에 대해서는 아직 알려지지 않았고, 이 문제는 P-NP 문제로 불린다. NP=PCP(log n, O(1)) (ko) NP, de aanduiding voor niet-deterministisch polynomiaal, is een die alle beslissingsproblemen bevat die oplosbaar zijn in polynomiale tijd door een niet-deterministische turingmachine. In de complexiteitstheorie is NP ook bekend als NTIME( nO(1) ) NP kan ook beschouwd worden als de verzameling beslissingsproblemen (te beantwoorden met 'ja' of 'nee') waarvoor een 'ja'-oplossing in polynomiale tijd geverifieerd kan worden door een deterministische turingmachine. De beslissingsproblemen waarvoor een 'nee'-oplossing eenvoudig te controleren is, behoren tot , het complement van NP. (nl) 計算複雑性理論における NP (Non-deterministic Polynomial time)は、複雑性クラスのひとつであり、答えがyesとなるような問いに対して、多項式時間で検証できる証拠が存在する決定問題のクラスである。 (ja) Na teoria da complexidade computacional, NP é o acrônimo em inglês para Tempo polinomial não determinístico (Non-Deterministic Polynomial time) que denota o conjunto de problemas que são decidíveis em tempo polinomial por uma máquina de Turing não-determinística. Uma definição equivalente é o conjunto de problemas de decisão que podem ter seu certificado verificado em por uma máquina de Turing determinística. (pt) NP betecknar mängden beslutsproblem som kan lösas på polynomiell tid av en Turingmaskin. (sv) Клас складності NP (англ. Complexity class NP) — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний час; тобто, недетермінованими алгоритмами в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що . (uk) 非決定性多项式集合（英語：non-deterministic polynomial，缩写：NP）是计算理论中最重要的集合之一。它包含P和NP-complete。 P問題是指在多项式时间内可以找出解的決定性問題(decision problem)，而NP問題則包含可在多项式时间內驗證其解是否正確，但不保證能在多項式時間內能找出解的決定性問題。NP包含P和NP-complete问题, 因此NP集合中有簡單的問題和不容易快速得到解的難題。 [NP等不等於P?]是一個计算机科学中知名的難題。 (zh) NP (zkratka nedeterministicky polynomiální) je množina problémů, které lze řešit v polynomiálně omezeném čase na nedeterministickém Turingově stroji - na počítači, který umožňuje v každém kroku rozvětvit výpočet na n větví, v nichž se posléze řešení hledá současně. Ekvivalentně se hovoří o stroji, který na místě rozhodování uhodne správnou cestu výpočtu. Alternativně lze tyto problémy definovat tak, že je to množina problémů, u kterých lze pro dodaný výsledek v polynomiálním čase ověřit jeho správnost (ale obecně nikoliv nalézt řešení v polynomiálním čase). (cs) In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Intuitiv beschrieben, enthält NP die Entscheidungsprobleme, bei denen es für „Ja“-Antworten Beweise gibt, die effizient (in Polynomialzeit) verifiziert werden können. Es kann aber mitunter aufwändig sein, einen solchen Beweis zu finden. Eine alternative Beschreibung von NP ist also die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine (NTM) bezüglich der Eingabelänge in Polynomialzeit gelöst werden können. Hierbei wird eine Instanz mit „Ja“ beantwortet, wenn mindestens eine der möglichen Berechnungen der nichtdeterministischen Turingmaschine dies tut. (de) In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine. (en) La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« nondeterministic polynomial time »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution. Par exemple, considérons le problème de décision du voyageur de commerce qui, étant donné un entier k et un ensemble de villes séparées par des distances, détermine s'il existe un circuit de longueur inférieure à k qui passe une et une seule fois par toutes les villes. On vérifie « rapidement » qu'une solution candidate, ici un chem (fr) La classe di problemi comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale. La classe NP prende il suo nome dall'abbreviazione di Nondeterministic Polynomial Time. In sostanza qualora esiste una macchina di Turing non deterministica che accetta (quindi converge per ogni input ). Invece se l'input che si fornisce alla macchina di Turing che accetta non appartiene a quest'ultimo linguaggio, allora si avranno solo computazioni infinite o computazioni massimali non accettanti. (it) Problem NP (ang. nondeterministic polynomial, niedeterministycznie wielomianowy) – problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga. Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność. Przykładowy problem: (pl) В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения). Эквивалентно класс NP включает задачи, которые можно за полиномиальное время решить на недетерминированной машине Тьюринга. (ru) |
| rdfs:label | كثير حدود غير قطعي (ar) NP (Complexitat) (ca) NP (třída složitosti) (cs) NP (Komplexitätsklasse) (de) NP (clase de complejidad) (es) NP (complexité) (fr) NP (complessità) (it) NP (복잡도) (ko) NP (complexity) (en) NP (ja) NP (complexiteitsklasse) (nl) Problem NP (pl) NP (complexidade) (pt) NP (sv) Класс NP (ru) Клас складності NP (uk) NP (複雜度) (zh) |
| owl:sameAs | freebase:NP (complexity) freebase:NP (complexity) yago-res:NP (complexity) wikidata:NP (complexity) dbpedia-ar:NP (complexity) dbpedia-bg:NP (complexity) http://bs.dbpedia.org/resource/NP_(klasa_kompleksnosti) dbpedia-ca:NP (complexity) dbpedia-cs:NP (complexity) dbpedia-da:NP (complexity) dbpedia-de:NP (complexity) dbpedia-es:NP (complexity) dbpedia-fa:NP (complexity) dbpedia-fi:NP (complexity) dbpedia-fr:NP (complexity) dbpedia-he:NP (complexity) dbpedia-it:NP (complexity) dbpedia-ja:NP (complexity) dbpedia-ko:NP (complexity) dbpedia-nl:NP (complexity) dbpedia-nn:NP (complexity) dbpedia-no:NP (complexity) dbpedia-pl:NP (complexity) dbpedia-pt:NP (complexity) dbpedia-ro:NP (complexity) dbpedia-ru:NP (complexity) dbpedia-sr:NP (complexity) dbpedia-sv:NP (complexity) dbpedia-th:NP (complexity) dbpedia-tr:NP (complexity) dbpedia-uk:NP (complexity) dbpedia-vi:NP (complexity) dbpedia-zh:NP (complexity) https://global.dbpedia.org/id/4oqbS |
| prov:wasDerivedFrom | wikipedia-en:NP_(complexity)?oldid=1119703601&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/P_np_np-complete_np-hard.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:NP_(complexity) |
| is dbo:knownFor of | dbr:Jack_Edmonds |
| is dbo:wikiPageDisambiguates of | dbr:NP |
| is dbo:wikiPageRedirects of | dbr:Nondeterministic_Polynomial dbr:Nondeterministic_polynomial dbr:Nondeterministic_polynomial_time dbr:Np_(complexity) dbr:Class_NP dbr:Complexity_class_NP dbr:NP-Class dbr:NP-Problem dbr:NP-class dbr:NP-problem dbr:NP_(class) dbr:NP_(complexity_class) dbr:NP_Class dbr:NP_class |
| is dbo:wikiPageWikiLink of | dbr:Primality_certificate dbr:Probabilistic_Turing_machine dbr:Proof_complexity dbr:Quantum_complexity_theory dbr:Enumeration_algorithm dbr:List_of_complexity_classes dbr:List_of_computing_and_IT_abbreviations dbr:NP dbr:Memetic_algorithm dbr:Parity_P dbr:Parity_game dbr:Primality_Testing_for_Beginners dbr:Primality_test dbr:Nondeterministic_Polynomial dbr:Nondeterministic_polynomial dbr:Nondeterministic_polynomial_time dbr:List_of_important_publications_in_cryptography dbr:Vaughan_Pratt dbr:Decision_problem dbr:Descriptive_Complexity dbr:Descriptive_complexity_theory dbr:Deterministic_algorithm dbr:EXPSPACE dbr:Integer_factorization dbr:Interactive_proof_system dbr:Quantum_computing dbr:PSPACE-complete dbr:Proof_of_knowledge dbr:Propositional_proof_system dbr:Security_parameter dbr:Np_(complexity) dbr:Well-colored_graph dbr:♯P dbr:♯P-complete dbr:(SAT,_ε-UNSAT) dbr:Computing_the_permanent dbr:Mathematical_logic dbr:Maximum_cut dbr:Geometric_complexity_theory dbr:Valiant–Vazirani_theorem dbr:NP-easy dbr:QMA dbr:Co-NP dbr:Glossary_of_artificial_intelligence dbr:Graph_coloring dbr:Bounded_arithmetic dbr:NLTS_Conjecture dbr:NL_(complexity) dbr:Constraint_satisfaction_problem dbr:Cook–Levin_theorem dbr:L_(complexity) dbr:Linkless_embedding dbr:Stephen_Cook dbr:Combinatorial_optimization dbr:Commitment_scheme dbr:Complement_(complexity) dbr:Complete_(complexity) dbr:Complexity dbr:Complexity_class dbr:Computational_complexity dbr:Computational_complexity_theory dbr:Computational_topology dbr:Zero-knowledge_proof dbr:Function_problem dbr:PCP_theorem dbr:PH_(complexity) dbr:PLS_(complexity) dbr:P_(complexity) dbr:Padding_argument dbr:Probabilistically_checkable_proof dbr:Sparse_language dbr:Theory_of_computation dbr:Many-one_reduction dbr:P/poly dbr:BPP_(complexity) dbr:BQP dbr:Time_complexity dbr:Domatic_number dbr:Gittins_index dbr:Joel_Hass dbr:Lattice_problem dbr:Polynomial-time_reduction dbr:TFNP dbr:Resource_bounded_measure dbr:EXPTIME dbr:Alternating_Turing_machine dbr:Nicola_Leone dbr:PSPACE dbr:Discrete_mathematics dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Reduction_(complexity) dbr:2-EXPTIME dbr:2-satisfiability dbr:Hajós_construction dbr:Jack_Edmonds dbr:Counting_problem_(complexity) dbr:Toda's_theorem dbr:APX dbr:Advice_(complexity) dbr:Johan_Håstad dbr:Karp–Lipton_theorem dbr:Co-NP-complete dbr:Rectangle_packing dbr:Arthur–Merlin_protocol dbr:Average-case_complexity dbr:Mark_Sapir dbr:Boolean_circuit dbr:Boolean_hierarchy dbr:Boolean_satisfiability_problem dbr:Planar_SAT dbr:Polynomial_hierarchy dbr:Sokoban dbr:Circuit_Value_Problem dbr:Circuit_complexity dbr:Circuits_over_sets_of_natural_numbers dbr:Implicit_graph dbr:RP_(complexity) dbr:Randomized_algorithm dbr:Certificate_(complexity) dbr:Second-order_logic dbr:Shafi_Goldwasser dbr:Mixed_Chinese_postman_problem dbr:Monadic_second-order_logic dbr:SNP_(complexity) dbr:Shmuel_Safra dbr:Skolem_arithmetic dbr:UP_(complexity) dbr:Verifiable_random_function dbr:Vijay_Vazirani dbr:Tag_SNP dbr:FL_(complexity) dbr:FNP_(complexity) dbr:IP_(complexity) dbr:Immerman–Szelepcsényi_theorem dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_unsolved_problems_in_computer_science dbr:Low_(complexity) dbr:Rotation_distance dbr:Existential_theory_of_the_reals dbr:Finite_model_theory dbr:First-order_reduction dbr:NEXPTIME dbr:NP-completeness dbr:NP-hardness dbr:NP-intermediate dbr:NP/poly dbr:NTIME dbr:Witness-indistinguishable_proof dbr:Polygonalization dbr:Polynomial-time_counting_reduction dbr:Time_hierarchy_theorem dbr:Unambiguous_Turing_machine dbr:Set_packing dbr:Unknot dbr:Savitch's_theorem dbr:P_versus_NP_problem dbr:Unknotting_problem dbr:S2P_(complexity) dbr:Structural_complexity_theory dbr:Space_complexity dbr:Ronald_Fagin dbr:Word-representable_graph dbr:Class_NP dbr:Complexity_class_NP dbr:NP-Class dbr:NP-Problem dbr:NP-class dbr:NP-problem dbr:NP_(class) dbr:NP_(complexity_class) dbr:NP_Class dbr:NP_class |
| is dbp:knownFor of | dbr:Jack_Edmonds |
| is foaf:primaryTopic of | wikipedia-en:NP_(complexity) |
