NP-hardness
http://dbpedia.org/resource/NP-hardness an entity of type: WikicatComplexityClasses
مسائل NP صعبة في علم التعقيد الحسابي هي مجموعة مسائل حيث انه يمكن اختصار كل المسائل في NP اليها. ولهذه المجموعة اهمية عظيمة في علم الحاسوب والرياضيات لما لها من تاثير على كثير من النواحي العملية فيه إذ انه تمتد هذه المجموعة لمسائل التخطيط ومعالجة الصور الرقمية وتحسين مُصرف... ملاحظة: بشكل عام NP كاملة ≠ NP صعبة لذا يجب الاخذ بالحسبان انه إذا NP = P فهذا لا يعني بالضرورة أنَّ كل المسائل التي هي NP صعبة أيضا يمكن حلها بوقت حدودي (أي انها تابعة ل- P).
rdf:langString
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
rdf:langString
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-난해 집합은 판정 문제 뿐만이 아니라 최적화 문제 등 다른 형태의 문제가 포함된다.
rdf:langString
NP困难（NP-hardness, non-deterministic polynomial-time hardness）问题是计算复杂性理论中最重要的复杂性类之一。如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。 因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。
rdf:langString
NP-складна задача (англ. NP-hard) — задача не менш складна ніж NP-повна. Задача Π є NP-складною, якщо існує NP-повна задача Π1, що зводиться до Π.
rdf:langString
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.
rdf:langString
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 (
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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困難である。
rdf:langString
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:
rdf:langString
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.
rdf:langString
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.
rdf:langString
В теории сложности вычислений NP-трудность (недетерминированная полиномиальная трудность по времени) является определяющим свойством класса задач, которые, неформально, «по крайней мере так же сложны, как самые сложные задачи в NP». Простым примером NP-трудной задачи является задача о сумме подмножеств. Считается что алгоритмов с полиномиальным временем для NP-трудных задач не существует, но это не доказано (см. проблему P≠NP). Более того, класс P, в котором все задачи решаются за полиномиальное время, содержится в классе NP.
rdf:langString
rdf:langString
مسائل NP صعبة
rdf:langString
NP-difícil
rdf:langString
NP-Schwere
rdf:langString
NP-peza
rdf:langString
NP-hard
rdf:langString
NP-difficile
rdf:langString
NP-difficile
rdf:langString
NP困難
rdf:langString
NP-난해
rdf:langString
NP-hardness
rdf:langString
NP-moeilijk
rdf:langString
NP-difícil
rdf:langString
Problem NP-trudny
rdf:langString
NP-трудность
rdf:langString
NP困难
rdf:langString
NP-складна задача
xsd:integer
54681
xsd:integer
1098421480
rdf:langString
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. Com classes similars, la NP de NP-hard vol dir que el problema és acceptat en temps polinòmic per una màquina de Turing no determinista.
rdf:langString
مسائل NP صعبة في علم التعقيد الحسابي هي مجموعة مسائل حيث انه يمكن اختصار كل المسائل في NP اليها. ولهذه المجموعة اهمية عظيمة في علم الحاسوب والرياضيات لما لها من تاثير على كثير من النواحي العملية فيه إذ انه تمتد هذه المجموعة لمسائل التخطيط ومعالجة الصور الرقمية وتحسين مُصرف... ملاحظة: بشكل عام NP كاملة ≠ NP صعبة لذا يجب الاخذ بالحسبان انه إذا NP = P فهذا لا يعني بالضرورة أنَّ كل المسائل التي هي NP صعبة أيضا يمكن حلها بوقت حدودي (أي انها تابعة ل- P).
rdf:langString
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 (also deterministisch in Polynomialzeit) löst, mithilfe einer Polynomialzeitreduktion genutzt werden kann, um ein beliebiges Problem in NP effizient zu lösen. Der umgangssprachlich auftretende Begriff NP-Härte ist eine Fehlübersetzung des englischen NP-hard.
rdf:langString
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. Do, formale, lingvo L estas NP-peza se ∀L' en NP, . Se ĝi estas ankaŭ la kazo, ke L estas en NP, tiam L estas . La nocio de NP-dureco ludas gravan rolon en la diskuto pri la interrilato inter la kompleksecaj klasoj P kaj NP. La klaso NP-peza povas esti komprenita kiel la klaso de problemoj, kiuj estas NP-plenaj aŭ pli pezaj. Komuna eraro estas, pensi, ke la "NP" en "NP-peza" staras por "ne-polinomo". Kvankam ĝi estas larĝe suspektite, ke ne estas polinomo-tempaj algoritmoj por ĉi tiuj problemoj, tio ne estis pruvita.
rdf:langString
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
rdf:langString
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. Asumiendo que el lenguaje L es NP-completo, 1. L está en NP2. ∀L' en NP, L' ≤ L En el conjunto NP-Hard se asume que el lenguaje L satisface la propiedad 2, pero no la propiedad 1. La clase NP-completo puede definirse alternativamente como la intersección entre NP y NP-hard. Algunas consecuencias de la definición son:
* Como NP-completo es el tipo más costoso de la clase NP, el problema H es al menos tan costoso como NP, pero H no tiene por qué estar en NP y por tanto no tiene por qué ser un problema de decisión.
* Los problemas NP-completos se pueden transformar unos en otros por una reducción polinómica, los problemas NP-completos pueden ser resueltos en tiempo polinómico por reducción a H, así que todos los problemas de NP se reducen a H; sin embargo, esto implica utilizar dos tipos diferentes de transformaciones: de problemas de decisión NP-completos a un problema NP-completo L por transformaciones polinómicas, y de L a H por reducción polinómica de Turing.
* Si hay algún algoritmo polinómico para resolver un problema NP-hard, entonces hay algoritmos para resolver todos los problemas de NP en tiempo polinómico, esto significaría que P=NP.
* Si un problema de optimización H tiene una versión NP-completa, entonces H es NP-hard.
* Si H pertenece a NP, entonces H pertenece también a NP-completo porque en este caso existe una transformación polinómica de Turing que cumple los requisitos de las transformaciones polinómicas. Un error común es pensar que NP en NP-hard quiere decir no polinómico, ya que aunque hay serias sospechas sobre que no existen algoritmos para resolver estos problemas en tiempo polinómico, esto nunca ha sido demostrado.
rdf:langString
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. A more precise specification is: a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H; that is, assuming a solution for H takes 1 unit time, H's solution can be used to solve L in polynomial time. As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists. 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.
rdf:langString
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困難である。 NP困難な組合せ最適化問題は、一般に最適解を求めるアルゴリズムが計算完了までに指数関数時間を必要とするなどして、非常に困難であると考えられているため、近似アルゴリズムが多数考案されている。また、数理的に解く従来からのアプローチの他に、ディープラーニングの応用なども盛んに行われている。量子コンピュータでは最適解をリアルタイムで求める方法も試みられている。
rdf:langString
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-난해 집합은 판정 문제 뿐만이 아니라 최적화 문제 등 다른 형태의 문제가 포함된다.
rdf:langString
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. La categoria dei problemi NP-difficili, a differenza delle classi P, NP e degli NP-completi, non è limitata per definizione ai soli ; vi appartengono infatti anche problemi di ottimizzazione e di altri generi. La classe dei problemi NP-difficili ha una grande rilevanza sia teorica che pratica. In pratica, dimostrare che un problema di calcolo è equivalente a un problema notoriamente NP-difficile significa dimostrare che è praticamente impossibile trovare un modo efficiente di risolverlo, cosa che ha molte implicazioni in informatica. Da un punto di vista teorico, lo studio dei problemi NP-difficili è un elemento essenziale della ricerca su alcuni dei principali problemi aperti della complessità.
rdf:langString
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. Soms is het probleem in kwestie aantoonbaar moeilijker dan NP: bijvoorbeeld het vinden van de beste schaakzet in een gegeneraliseerd schaakspel op een n x n bord. Dit probleem is . Het Stop-probleem is zelfs onbeslisbaar. Het is dus NP-moeilijk, maar niet NP-volledig. Aan de andere kant kan het zo zijn dat het (nog) niet bekend is of het probleem in kwestie deel uitmaakt van NP. Soms is het eenvoudig om een bewijs te leveren dat een probleem NP-moeilijk is, maar is het bewijs dat het probleem deel uitmaakt van NP het lastigste deel van een NP-volledigheidsbewijs.Geheeltallig lineair programmeren is een probleem waarvan het NP-moeilijkheidsbewijs niet zo moeilijk is, maar het veel lastiger is gebleken om te bewijzen dat het probleem deel uitmaakt van NP.
rdf:langString
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. Innymi słowy, problem NP-zupełny można rozwiązać w wielomianowym czasie algorytmem rozwiązującym problem NP-trudny przez wykorzystanie hipotetycznej procedury sprowadzającej problem NP-zupełny do problemu NP-trudnego jeżeli tylko daje się wykonać w wielomianowym czasie. NP-trudność można zdefiniować także w kategorii języków formalnych (a nie problemów). Do klasy problemów NP-trudnych mogą należeć problemy różnego typu: decyzyjne, , optymalizacyjne. Wraz z definicjami klas problemów NP i NP-zupełnych ma to następujące konsekwencje:
* problem optymalizacyjny, którego wersja decyzyjna jest NP-zupełna, jest problemem NP-trudnym;
* NP-trudny problem jest co najmniej tak trudny, jak problem
* ponieważ jest problemem NP-zupełnym, toteż należy on do problemów najtrudniejszych w klasie NP, dlatego NP-trudny problem jest co najmniej tak trudny, jak cała klasa NP;
* ponieważ wszystkie problemy NP-zupełne transformują się wzajemnie do siebie (zwykłą) transformacją wielomianową (nie Turinga), to również wszystkie problemy NP-zupełne można rozwiązać przez redukcję do NP-trudnego problemu
* ponadto, jeśli to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym, natomiast rozstrzygnięcie nie przesądza o wielomianowej rozwiązywalności wszystkich problemów NP-trudnych;
* jeżeli problem należy do klasy NP, to jest też problemem NP-zupełnym (gdyż wraz z istniejącą transformacją Turinga spełnia definicję problemu NP-zupełnego).
rdf:langString
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. Como conseqüências da definição, temos que (note que estas afirmações não são definições):
* O problema H é pelo menos tão difícil quanto L, porque H pode ser usado para resolver L;
* Como L é NP-completo e, portanto, o mais difícil na classe NP, também o problema H é pelo menos tão difícil quanto um NP, mas H não tem que estar em NP e, consequentemente, não tem de ser um problema de decisão (mesmo que seja um problema de decisão, ele não precisa estar em NP);
* Uma vez que os problemas NP-completos transformam-se uns aos outros por (também chamada de transformação polinomial), todos os problemas NP-completos podem ser resolvidos em tempo polinomial por uma redução para H, Assim, todos os problemas em NP reduzem para H; note-se, porém, que isso envolve a combinação de duas transformações diferentes: de problemas de decisão NP-completos para o problema NP-completo L por transformação polinomial, e de L para H pela redução em tempo polinomial de Turing;
* Se existe um algoritmo polinomial para qualquer problema NP-difícil, então existem algoritmos polinomiais para todos os problemas em NP, e, portanto, P = NP;
* Se P != NP, então os problemas NP-difíceis não têm soluções em tempo polinomial, uma vez que P = NP não resolve se os problemas NP-difíceis podem ser resolvidos em tempo polinomial;
* Se um problema de otimização H tem uma versão de decisão NP-completo L, então H é NP-difícil. Um erro comum é pensar que NP em NP-difícil representa não-polinomial. Embora seja amplamente suspeito de que não existem algoritmos de tempo polinomial para problemas NP-difíceis, isto nunca foi provado. Além disso, a classe NP contém também todos os problemas que podem ser resolvidos em tempo polinomial.
rdf:langString
В теории сложности вычислений NP-трудность (недетерминированная полиномиальная трудность по времени) является определяющим свойством класса задач, которые, неформально, «по крайней мере так же сложны, как самые сложные задачи в NP». Простым примером NP-трудной задачи является задача о сумме подмножеств. Формальное определение: задача разрешимости является NP-трудной, если любая задача из NP может быть сведена за полиномиальное время к . Эквивалентно условие требует, чтобы каждая задача в NP могла быть решена за полиномиальное время с оракулом для . Как следствие, алгоритм с полиномиальным временем для решения любой NP-трудной задачи даст алгоритмы с полиномиальным временем для всех задач в NP. Считается что алгоритмов с полиномиальным временем для NP-трудных задач не существует, но это не доказано (см. проблему P≠NP). Более того, класс P, в котором все задачи решаются за полиномиальное время, содержится в классе NP. Некоторые NP-трудные задачи оптимизации могут быть полиномиально аппроксимированы до некоторого постоянного (константного) коэффициента аппроксимации (в частности, в APX) или даже до любого коэффициента аппроксимации (в PTAS или FPTAS).
rdf:langString
NP困难（NP-hardness, non-deterministic polynomial-time hardness）问题是计算复杂性理论中最重要的复杂性类之一。如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。 因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。
rdf:langString
NP-складна задача (англ. NP-hard) — задача не менш складна ніж NP-повна. Задача Π є NP-складною, якщо існує NP-повна задача Π1, що зводиться до Π.
xsd:nonNegativeInteger
8845
