| 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)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[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)