| rdfs:comment
| - مسائل NP صعبة في علم التعقيد الحسابي هي مجموعة مسائل حيث انه يمكن اختصار كل المسائل في NP اليها. ولهذه المجموعة اهمية عظيمة في علم الحاسوب والرياضيات لما لها من تاثير على كثير من النواحي العملية فيه إذ انه تمتد هذه المجموعة لمسائل التخطيط ومعالجة الصور الرقمية وتحسين مُصرف... ملاحظة: بشكل عام NP كاملة ≠ NP صعبة لذا يجب الاخذ بالحسبان انه إذا NP = P فهذا لا يعني بالضرورة أنَّ كل المسائل التي هي NP صعبة أيضا يمكن حلها بوقت حدودي (أي انها تابعة ل- P). (ar)
- En informatique théorique, un problème NP-difficile est un problème vers lequel on peut ramener tout problème de la classe NP par une réduction polynomiale. S'il est également dans la classe NP, on dit que c'est un problème NP-complet.
* Portail de l'informatique théorique (fr)
- NP-난해, NP-hard는 NP에 속하는 모든 판정 문제를 다항 시간에 다대일 환산할 수 있는 문제들의 집합이다. 다시 말하면, NP-난해는 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이다. NP-난해 집합에 속하는 문제가 NP에도 속하면 NP-완전에 속한다. 즉, NP-완전은 NP와 NP-난해의 교집합이다. 만약 P-NP 문제가 P=NP로 풀린다면 P=NP=NP-완전이므로 P와 NP는 NP-난해의 부분집합이 되고, P≠NP인 경우는 P와 NP-난해는 서로소가 된다. NP-난해 집합은 NP에 속하지는 않는다. NP에 속하지 않는 NP-난해 문제의 한 예로는 정지 문제가 있다. 또한, NP-난해 집합은 판정 문제 뿐만이 아니라 최적화 문제 등 다른 형태의 문제가 포함된다. (ko)
- NP困难（NP-hardness, non-deterministic polynomial-time hardness）问题是计算复杂性理论中最重要的复杂性类之一。如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。 因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。 (zh)
- NP-складна задача (англ. NP-hard) — задача не менш складна ніж NP-повна. Задача Π є NP-складною, якщо існує NP-повна задача Π1, що зводиться до Π. (uk)
- En teoria de la complexitat, la classe de complexitat NP-Hard és el conjunt dels problemes de decisió tals que si H és un problema d'aquesta classe, tot problema L de NP es pot transformar en H en temps polinòmic. Es pot veure aquesta classe com el conjunt de problemes com a mínim tan difícils com els NP. Com a conseqüència de la seva definició, si es troba un algorisme de temps polinòmic que solucioni un problema NP-hard, donaria una solució polinòmica a tots els problemes NP, cosa poc probable, ja que tots es consideren massa difícils. (ca)
- NP-Schwere bezeichnet die Eigenschaft eines algorithmischen Problems, mindestens so schwer lösbar zu sein wie die Probleme der Klasse NP. Die Komplexitätstheorie, ein Teilgebiet der theoretischen Informatik, beschäftigt sich mit der Klassifizierung von Problemen bezüglich ihrer Komplexität, d. h. der algorithmischen Schwierigkeit, sie zu lösen. Eine wichtige Problemklasse ist die Komplexitätsklasse NP, die Klasse der Probleme, die mit einer nichtdeterministischen Turingmaschine in Polynomialzeit gelöst werden können. Anschaulich ist NP die Klasse aller Entscheidungsprobleme, für die eine gefundene Lösung effizient überprüft werden kann. Ein NP-schweres Problem ist nun mindestens so „schwer“ wie alle Probleme in NP. Das bedeutet, dass ein Algorithmus, der ein NP-schweres Problem effizient ( (de)
- En , NP-peza (Ne-determina Polinomo-tempo peza) nomas la klason de , kiu enhavas ĉiujn problemojn H, tia, ke por ĉiu decida problemo L en ekzistas al H, skribata kiel . Neformale, ĉi tiu klaso povas esti priskribita kiel enhavanta la decidajn problemojn, kiuj estas "almenaŭ kiel peza kiel problemoj en ". Ĉi tiu intuicio estas subtenata per la fakto, ke se ni povas trovi algoritmon A, kiu solvas unu el ĉi tiuj problemoj H en polinoma tempo, ni povas konstrui polinom-tempan algoritmon por ĉiu problemo L en NP per unue plenumo de la malpligrandiĝo de L al H kaj tiam ruligo la algoritmo A. (eo)
- En teoría de la complejidad computacional, la clase de complejidad NP-hard (o NP-complejo, o NP-difícil) es el conjunto de los problemas de decisión que contiene los problemas H tales que todo problema L en NP puede ser transformado polinomialmente en H. Esta clase puede ser descrita como aquella que contiene a los problemas de decisión que son como mínimo tan difíciles como un problema de NP. Esta afirmación se justifica porque si podemos encontrar un algoritmo A que resuelve uno de los problemas H de NP-hard en tiempo polinómico, entonces es posible construir un algoritmo que trabaje en tiempo polinómico para cualquier problema de NP ejecutando primero la reducción de este problema en H y luego ejecutando el algoritmo A. (es)
- In computational complexity theory, NP-hardness (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class. (en)
- In teoria della complessità, i problemi NP-difficili o NP-ardui (in inglese NP-hard, da nondetermistic polynomial-time hard problem, "problema difficile non deterministico in tempo polinomiale") sono una classe di problemi che può essere definita informalmente come la classe dei problemi almeno difficili come i più difficili problemi delle classi di complessità P e NP. Più formalmente, un problema è NP-difficile se e solo se ogni problema NP è polinomialmente riducibile ad , ovvero tale che . In altre parole, deve poter essere risolto in tempo polinomiale da una macchina di Turing dotata di un per . Da questa definizione si ricava che i problemi NP-difficili sono non meno difficili dei problemi NP-completi, che a loro volta sono per definizione i più difficili delle classi P/NP. (it)
- NP困難（エヌピーこんなん、英: NP-hard）とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである。正確にいうと、ある問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。もしもあるNP困難問題を解ける多項式時間の機械が存在すれば、それを利用すればNPに属する任意の問題を多項式時間で解くことができる。 NP完全問題とは、NP困難であり、かつNPに属する問題である。これとは異なり、ある問題がNP困難であってもNPに属するとは限らない。NPは決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、(en)、組合せ最適化問題など様々な問題が属しうる。 上に挙げた定義から、問題 H がNP困難であるときには次のことが言える（以下は定義ではなく主張）。
* すべてのNP完全問題は H に還元して多項式時間で解ける。またNPに属する全ての問題も H に還元できる。
* もし最適化問題 H の特殊例としてNP完全な決定問題 L を考えられるなら、H はNP困難である。 (ja)
- Problem NP-trudny (NPH, ang. NP-Hard) – problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne, jak rozwiązanie każdego problemu z klasy NP (całej klasy NP). Formalna definicja problemu NP-trudnego jest następująca: Problem jest NP-trudny, jeżeli pewien problem NP-zupełny jest do niego redukowalny wielomianową transformacją Turinga. Wraz z definicjami klas problemów NP i NP-zupełnych ma to następujące konsekwencje: (pl)
- NP-moeilijk is een complexiteitsgraad. Een gegeven probleem A is NP-moeilijk als ieder beslissingsprobleem in NP in polynomiale tijd tot A gereduceerd kan worden; het is dus minstens zo moeilijk als ieder probleem in NP. Als het probleem zelf ook tot de klasse NP behoort, dan is het NP-volledig. Niet ieder probleem dat NP-moeilijk is, is NP-volledig; het omgekeerde is — per definitie — wel het geval. Voorbeelden van NP-moeilijke beslissingsproblemen zijn MAX-SAT en het handelsreizigersprobleem. (nl)
- NP-difícil (ou NP-hard, ou NP-complexo) na teoria da complexidade computacional, é uma classe de problemas que são, informalmente, "Pelo menos tão difíceis quanto os problemas mais difíceis em NP". Um problema H é NP-difícil se e somente se (sse) existe um problema NP-completo L que é para H (i.e., L?=?TH). Em outras palavras, L pode ser resolvido em por uma Máquina de Turing não determinística com um oráculo para H. Informalmente, podemos pensar em um algoritmo que pode chamar tal Máquina de Turing Não-Determinística como uma sub-rotina para resolver H, e resolver L em tempo polinomial, se a chamada da sub-rotina leva apenas um passo para computar. Problemas NP-difíceis podem ser de qualquer tipo: problemas de decisão, problemas de pesquisa ou problemas de otimização. (pt)
- В теории сложности вычислений NP-трудность (недетерминированная полиномиальная трудность по времени) является определяющим свойством класса задач, которые, неформально, «по крайней мере так же сложны, как самые сложные задачи в NP». Простым примером NP-трудной задачи является задача о сумме подмножеств. Считается что алгоритмов с полиномиальным временем для NP-трудных задач не существует, но это не доказано (см. проблему P≠NP). Более того, класс P, в котором все задачи решаются за полиномиальное время, содержится в классе 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)