An Entity of Type: Collection107951464, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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.

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)
  • 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)
  • 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 e la macchina di Turing ovviamente diverge. 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)
  • 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 non-deterministic 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 non-deterministic way, while the second phase consists of a deterministic algorithm that verifies if 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 (Non-deterministic Polynomial time)は、複雑性クラスのひとつであり、答えがyesとなるような問いに対して、多項式時間で検証できる証拠が存在する決定問題のクラスである。 (ja)
  • NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이다. NP에 속하는 문제는 결정론적 튜링 기계로 다항 시간에 검증이 가능하고, 그 역도 성립한다. 또한 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 문제는 비결정론적 튜링 기계로도 다항 시간 안에 풀 수 있으므로, P 집합은 NP 집합의 부분집합이다. 이때 P가 NP의 진부분집합인지, 혹은 P와 NP가 같은지에 대해서는 아직 알려지지 않았고, 이 문제는 P-NP 문제로 불린다. NP=PCP(log n, O(1)) (ko)
  • 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. W 2000 roku Buss przewidywał, że zostanie potwierdzone w ciągu 20 lat. W 2001 roku 40 spośród 97 ekspertów było przekonanych, że problem ten zostanie rozwiązany do 2039 roku, a 57, że do roku 2070. Według New Scientist z 2010 roku istnieje 50% szans na rozwiązanie problemu przed 2024 rokiem, gdyż 9 spośród 18 badanych hipotez udowodniono, zanim upłynęły 54 lata od ich postawienia. W 2012 roku analiza 144 hipotez matematycznych (w tym tych nieudowodnionych) uwzględniająca wzrost liczby matematyków oraz coraz lepszy przepływ wiedzy pomiędzy nimi wykazała, że szansa na rozwiązanie problemu przed 2024 rokiem to 41%. Zgodnie z ankietą z 2011 roku wśród 152 ekspertów 53% z nich uważa, iż problem zostanie rozwiązany przed 2100 rokiem, a 41%, że po nim. (pl)
  • 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)
  • 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)
  • 非決定性多项式集合(英語:non-deterministic polynomial,缩写:NP)是计算理论中最重要的集合之一。它包含P和NP-complete。P集合的問題即在多项式时间内可以找出解的決策性問題(decision problem)集合。注意NP包含P和NP-complete问题, 因此NP集合中有簡單的問題和不容易快速得到解的難題。[NP等不等於P?]是一個计算机科学中知名的難題。 (zh)
  • В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения). Эквивалентно класс NP включает задачи, которые можно за полиномиальное время решить на недетерминированной машине Тьюринга. Задачи, имеющие полиномиальные по времени алгоритмы решения, можно решать с помощью компьютера значительно быстрее, чем путём прямого перебора, время которого экспоненциально. Это обуславливает практическое значение проблемы о равенстве классов P и NP. (ru)
  • Клас складності NP (англ. Complexity class NP) — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний час; тобто, недетермінованими алгоритмами в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що . (uk)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 21562 (xsd:integer)
dbo:wikiPageLength
  • 19606 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1023061794 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dct:subject
rdf:type
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 (Non-deterministic Polynomial time)は、複雑性クラスのひとつであり、答えがyesとなるような問いに対して、多項式時間で検証できる証拠が存在する決定問題のクラスである。 (ja)
  • 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)
  • 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)
  • 非決定性多项式集合(英語:non-deterministic polynomial,缩写:NP)是计算理论中最重要的集合之一。它包含P和NP-complete。P集合的問題即在多项式时间内可以找出解的決策性問題(decision problem)集合。注意NP包含P和NP-complete问题, 因此NP集合中有簡單的問題和不容易快速得到解的難題。[NP等不等於P?]是一個计算机科学中知名的難題。 (zh)
  • Клас складності NP (англ. Complexity class NP) — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний час; тобто, недетермінованими алгоритмами в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що . (uk)
  • 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 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 e la macchina di Turing ovviamente diverge. (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 (complexity) (en)
  • NP (clase de complejidad) (es)
  • NP (complexité) (fr)
  • NP (ja)
  • NP (complessità) (it)
  • NP (복잡도) (ko)
  • Problem NP (pl)
  • NP (complexiteitsklasse) (nl)
  • NP (complexidade) (pt)
  • NP (sv)
  • Класс NP (ru)
  • NP (複雜度) (zh)
  • Клас складності NP (uk)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:knownFor of
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is dbp:knownFor of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License