NP-hardness (original) (raw)
مسائل NP صعبة في علم التعقيد الحسابي هي مجموعة مسائل حيث انه يمكن اختصار كل المسائل في NP اليها. ولهذه المجموعة اهمية عظيمة في علم الحاسوب والرياضيات لما لها من تاثير على كثير من النواحي العملية فيه إذ انه تمتد هذه المجموعة لمسائل التخطيط ومعالجة الصور الرقمية وتحسين مُصرف... ملاحظة: بشكل عام NP كاملة ≠ NP صعبة لذا يجب الاخذ بالحسبان انه إذا NP = P فهذا لا يعني بالضرورة أنَّ كل المسائل التي هي NP صعبة أيضا يمكن حلها بوقت حدودي (أي انها تابعة ل- P).
| Property | Value |
|---|---|
| dbo:abstract | 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. (ca) مسائل NP صعبة في علم التعقيد الحسابي هي مجموعة مسائل حيث انه يمكن اختصار كل المسائل في NP اليها. ولهذه المجموعة اهمية عظيمة في علم الحاسوب والرياضيات لما لها من تاثير على كثير من النواحي العملية فيه إذ انه تمتد هذه المجموعة لمسائل التخطيط ومعالجة الصور الرقمية وتحسين مُصرف... ملاحظة: بشكل عام NP كاملة ≠ NP صعبة لذا يجب الاخذ بالحسبان انه إذا NP = P فهذا لا يعني بالضرورة أنَّ كل المسائل التي هي NP صعبة أيضا يمكن حلها بوقت حدودي (أي انها تابعة ل- P). (ar) 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. (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. 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. (eo) 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) 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. (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. 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. (en) 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困難な組合せ最適化問題は、一般に最適解を求めるアルゴリズムが計算完了までに指数関数時間を必要とするなどして、非常に困難であると考えられているため、近似アルゴリズムが多数考案されている。また、数理的に解く従来からのアプローチの他に、ディープラーニングの応用なども盛んに行われている。量子コンピュータでは最適解をリアルタイムで求める方法も試みられている。 (ja) 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) 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à. (it) 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. (nl) 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). (pl) 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. (pt) В теории сложности вычислений NP-трудность (недетерминированная полиномиальная трудность по времени) является определяющим свойством класса задач, которые, неформально, «по крайней мере так же сложны, как самые сложные задачи в NP». Простым примером NP-трудной задачи является задача о сумме подмножеств. Формальное определение: задача разрешимости является NP-трудной, если любая задача из NP может быть сведена за полиномиальное время к . Эквивалентно условие требует, чтобы каждая задача в NP могла быть решена за полиномиальное время с оракулом для . Как следствие, алгоритм с полиномиальным временем для решения любой NP-трудной задачи даст алгоритмы с полиномиальным временем для всех задач в NP. Считается что алгоритмов с полиномиальным временем для NP-трудных задач не существует, но это не доказано (см. проблему P≠NP). Более того, класс P, в котором все задачи решаются за полиномиальное время, содержится в классе NP. Некоторые NP-трудные задачи оптимизации могут быть полиномиально аппроксимированы до некоторого постоянного (константного) коэффициента аппроксимации (в частности, в APX) или даже до любого коэффициента аппроксимации (в PTAS или FPTAS). (ru) 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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/P_np_np-complete_np-hard.svg?width=300 |
| dbo:wikiPageID | 54681 (xsd:integer) |
| dbo:wikiPageLength | 8845 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1098421480 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:David_S._Johnson dbr:Approximate_computing dbr:Approximation_algorithm dbr:Decision_problem dbr:Decision_support_system dbr:Cryptography dbr:Oracle_machine dbr:NP-easy dbr:NP-complete dbr:Configuration_management dbc:NP-hard_problems dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Planning dbr:Many-one_reduction dbr:Travelling_salesman_problem dbr:Truth_value dbr:Data_mining dbr:PSPACE dbr:Reduction_(complexity) dbc:Complexity_classes dbr:Halting_problem dbr:APX dbr:Boolean_satisfiability_problem dbr:Phylogenetics dbr:Polynomial-time_approximation_scheme dbr:Polynomial_time dbr:Optimization_problem dbr:Search_problem dbr:Turing_machine dbr:Subset_sum_problem dbr:Schedule dbr:Undecidable_problem dbr:NP-equivalent dbr:NP-intermediate dbr:True_quantified_Boolean_formula dbr:P_versus_NP dbr:Michael_R._Garey dbr:File:P_np_np-complete_np-hard.svg |
| dbp:wikiPageUsesTemplate | dbt:' dbt:Cite_book dbt:For dbt:Reflist dbt:Rp dbt:Short_description dbt:ComplexityClasses |
| dcterms:subject | dbc:NP-hard_problems dbc:Complexity_classes |
| gold:hypernym | dbr:Problems |
| rdf:type | yago:WikicatComplexityClasses yago:WikicatNP-hardProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Class107997703 yago:Collection107951464 yago:Condition113920835 yago:Difficulty114408086 yago:Group100031264 yago:Problem114410605 dbo:Disease yago:State100024720 |
| 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) |
| rdfs:label | مسائل NP صعبة (ar) NP-difícil (ca) NP-Schwere (de) NP-peza (eo) NP-hard (es) NP-difficile (fr) NP-difficile (it) NP困難 (ja) NP-난해 (ko) NP-hardness (en) NP-moeilijk (nl) NP-difícil (pt) Problem NP-trudny (pl) NP-трудность (ru) NP困难 (zh) NP-складна задача (uk) |
| owl:sameAs | freebase:NP-hardness yago-res:NP-hardness wikidata:NP-hardness dbpedia-ar:NP-hardness dbpedia-ca:NP-hardness dbpedia-de:NP-hardness dbpedia-eo:NP-hardness dbpedia-es:NP-hardness dbpedia-fa:NP-hardness dbpedia-fr:NP-hardness dbpedia-he:NP-hardness dbpedia-it:NP-hardness dbpedia-ja:NP-hardness dbpedia-ko:NP-hardness dbpedia-nl:NP-hardness dbpedia-nn:NP-hardness dbpedia-no:NP-hardness dbpedia-pl:NP-hardness dbpedia-pt:NP-hardness dbpedia-ro:NP-hardness dbpedia-ru:NP-hardness dbpedia-simple:NP-hardness dbpedia-sr:NP-hardness dbpedia-uk:NP-hardness dbpedia-vi:NP-hardness dbpedia-zh:NP-hardness https://global.dbpedia.org/id/Bujv |
| prov:wasDerivedFrom | wikipedia-en:NP-hardness?oldid=1098421480&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/P_np_np-complete_np-hard.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:NP-hardness |
| is dbo:wikiPageRedirects of | dbr:NP-hard dbr:Np-hard dbr:NP-HARD dbr:NP-Hard dbr:Np_hard dbr:NP-Hard_Problem dbr:NP-hard_problems dbr:NP_hard |
| is dbo:wikiPageWikiLink of | dbr:Probabilistic_soft_logic dbr:Science_Fell_in_Love,_So_I_Tried_to_Prove_It dbr:Envy_minimization dbr:Approximation_algorithm dbr:Arc_routing dbr:Kyber dbr:Nullspace_property dbr:Compiler dbr:Genome_architecture_mapping dbr:Geometric_set_cover_problem dbr:Glossary_of_artificial_intelligence dbr:NP-hard dbr:MRF_optimization_via_dual_decomposition dbr:Steiner_tree_problem dbr:Clique_percolation_method dbr:Computational_hardness_assumption dbr:Feature_selection dbr:Friction_of_distance dbr:Kronecker_coefficient dbr:Quantum_annealing dbr:PLS_(complexity) dbr:Post-quantum_cryptography dbr:Matching_pursuit dbr:MaxDDBS dbr:Travelling_Salesman_(2012_film) dbr:Travelling_salesman_problem dbr:Dodgson's_method dbr:Game_complexity dbr:K-means_clustering dbr:Las_Vegas_algorithm dbr:Lattice_problem dbr:Minimum_cut dbr:Minimum_relevant_variables_in_linear_system dbr:TFNP dbr:Ailsa_Land dbr:Daniel_J._Hulme dbr:Baruch_Schieber dbr:Np-hard dbr:Knight's_tour dbr:Reductionism dbr:Regularization_(mathematics) dbr:Hash_table dbr:Cost_distance_analysis dbr:Covering_problems dbr:Karmarkar-Karp_bin_packing_algorithms dbr:Bin_covering_problem dbr:Heuristic_(computer_science) dbr:Disjunctive_normal_form dbr:Assembly_line_feeding_problem dbr:Planar_SAT dbr:Point-set_registration dbr:Circuit_satisfiability_problem dbr:Grothendieck_inequality dbr:Capacitated_arc_routing_problem dbr:Medium_access_control dbr:Satisfiability_modulo_theories dbr:System_on_a_chip dbr:Simplex_algorithm dbr:List_of_unsolved_problems_in_fair_division dbr:Exact_algorithm dbr:Tile-matching_video_game dbr:NP-HARD dbr:NP-Hard dbr:Vertex_k-center_problem dbr:Multi-agent_pathfinding dbr:Multiplicative_weight_update_method dbr:Multiway_number_partitioning dbr:Symbolic_regression dbr:Random_oracle dbr:Spaced_seed dbr:Stochastic_transitivity dbr:Np_hard dbr:NP-Hard_Problem dbr:NP-hard_problems dbr:NP_hard |
| is foaf:primaryTopic of | wikipedia-en:NP-hardness |
