"8845"^^ . . . . "Problem NP-trudny (NPH, ang. NP-Hard) \u2013 problem obliczeniowy, kt\u00F3rego rozwi\u0105zanie jest co najmniej tak trudne, jak rozwi\u0105zanie ka\u017Cdego problemu z klasy NP (ca\u0142ej klasy NP). Formalna definicja problemu NP-trudnego jest nast\u0119puj\u0105ca: Problem jest NP-trudny, je\u017Celi pewien problem NP-zupe\u0142ny jest do niego redukowalny wielomianow\u0105 transformacj\u0105 Turinga. Innymi s\u0142owy, problem NP-zupe\u0142ny mo\u017Cna rozwi\u0105za\u0107 w wielomianowym czasie algorytmem rozwi\u0105zuj\u0105cym problem NP-trudny przez wykorzystanie hipotetycznej procedury sprowadzaj\u0105cej problem NP-zupe\u0142ny do problemu NP-trudnego je\u017Celi tylko daje si\u0119 wykona\u0107 w wielomianowym czasie. NP-trudno\u015B\u0107 mo\u017Cna zdefiniowa\u0107 tak\u017Ce w kategorii j\u0119zyk\u00F3w formalnych (a nie problem\u00F3w). Do klasy problem\u00F3w NP-trudnych mog\u0105 nale\u017Ce\u0107 problemy r\u00F3\u017Cnego typu: decyzyjne, , optymalizacyjne. Wraz z definicjami klas problem\u00F3w NP i NP-zupe\u0142nych ma to nast\u0119puj\u0105ce konsekwencje: \n* problem optymalizacyjny, kt\u00F3rego wersja decyzyjna jest NP-zupe\u0142na, jest problemem NP-trudnym; \n* NP-trudny problem jest co najmniej tak trudny, jak problem \n* poniewa\u017C jest problemem NP-zupe\u0142nym, tote\u017C nale\u017Cy on do problem\u00F3w najtrudniejszych w klasie NP, dlatego NP-trudny problem jest co najmniej tak trudny, jak ca\u0142a klasa NP; \n* poniewa\u017C wszystkie problemy NP-zupe\u0142ne transformuj\u0105 si\u0119 wzajemnie do siebie (zwyk\u0142\u0105) transformacj\u0105 wielomianow\u0105 (nie Turinga), to r\u00F3wnie\u017C wszystkie problemy NP-zupe\u0142ne mo\u017Cna rozwi\u0105za\u0107 przez redukcj\u0119 do NP-trudnego problemu \n* ponadto, je\u015Bli to problemy NP-trudne nie maj\u0105 rozwi\u0105za\u0144 w czasie wielomianowym, natomiast rozstrzygni\u0119cie nie przes\u0105dza o wielomianowej rozwi\u0105zywalno\u015Bci wszystkich problem\u00F3w NP-trudnych; \n* je\u017Celi problem nale\u017Cy do klasy NP, to jest te\u017C problemem NP-zupe\u0142nym (gdy\u017C wraz z istniej\u0105c\u0105 transformacj\u0105 Turinga spe\u0142nia definicj\u0119 problemu NP-zupe\u0142nego)."@pl . "NP\u56F0\u96E3"@ja . . "En teoria de la complexitat, la classe de complexitat NP-Hard \u00E9s el conjunt dels problemes de decisi\u00F3 tals que si H \u00E9s un problema d'aquesta classe, tot problema L de NP es pot transformar en H en temps polin\u00F2mic. Es pot veure aquesta classe com el conjunt de problemes com a m\u00EDnim tan dif\u00EDcils com els NP. Com a conseq\u00FC\u00E8ncia de la seva definici\u00F3, si es troba un algorisme de temps polin\u00F2mic que solucioni un problema NP-hard, donaria una soluci\u00F3 polin\u00F2mica a tots els problemes NP, cosa poc probable, ja que tots es consideren massa dif\u00EDcils. Com classes similars, la NP de NP-hard vol dir que el problema \u00E9s acceptat en temps polin\u00F2mic per una m\u00E0quina de Turing no determinista."@ca . "NP-Schwere bezeichnet die Eigenschaft eines algorithmischen Problems, mindestens so schwer l\u00F6sbar zu sein wie die Probleme der Klasse NP. Die Komplexit\u00E4tstheorie, ein Teilgebiet der theoretischen Informatik, besch\u00E4ftigt sich mit der Klassifizierung von Problemen bez\u00FCglich ihrer Komplexit\u00E4t, d. h. der algorithmischen Schwierigkeit, sie zu l\u00F6sen. Eine wichtige Problemklasse ist die Komplexit\u00E4tsklasse NP, die Klasse der Probleme, die mit einer nichtdeterministischen Turingmaschine in Polynomialzeit gel\u00F6st werden k\u00F6nnen. Anschaulich ist NP die Klasse aller Entscheidungsprobleme, f\u00FCr die eine gefundene L\u00F6sung effizient \u00FCberpr\u00FCft werden kann. Ein NP-schweres Problem ist nun mindestens so \u201Eschwer\u201C wie alle Probleme in NP. Das bedeutet, dass ein Algorithmus, der ein NP-schweres Problem effizient ("@de . . . . . . "NP-difficile"@it . . . "NP-\uB09C\uD574, NP-hard\uB294 NP\uC5D0 \uC18D\uD558\uB294 \uBAA8\uB4E0 \uD310\uC815 \uBB38\uC81C\uB97C \uB2E4\uD56D \uC2DC\uAC04\uC5D0 \uB2E4\uB300\uC77C \uD658\uC0B0\uD560 \uC218 \uC788\uB294 \uBB38\uC81C\uB4E4\uC758 \uC9D1\uD569\uC774\uB2E4. \uB2E4\uC2DC \uB9D0\uD558\uBA74, NP-\uB09C\uD574\uB294 \uC801\uC5B4\uB3C4 \uBAA8\uB4E0 NP \uBB38\uC81C\uB9CC\uD07C\uC740 \uC5B4\uB824\uC6B4 \uBB38\uC81C\uB4E4\uC758 \uC9D1\uD569\uC774\uB2E4. NP-\uB09C\uD574 \uC9D1\uD569\uC5D0 \uC18D\uD558\uB294 \uBB38\uC81C\uAC00 NP\uC5D0\uB3C4 \uC18D\uD558\uBA74 NP-\uC644\uC804\uC5D0 \uC18D\uD55C\uB2E4. \uC989, NP-\uC644\uC804\uC740 NP\uC640 NP-\uB09C\uD574\uC758 \uAD50\uC9D1\uD569\uC774\uB2E4. \uB9CC\uC57D P-NP \uBB38\uC81C\uAC00 P=NP\uB85C \uD480\uB9B0\uB2E4\uBA74 P=NP=NP-\uC644\uC804\uC774\uBBC0\uB85C P\uC640 NP\uB294 NP-\uB09C\uD574\uC758 \uBD80\uBD84\uC9D1\uD569\uC774 \uB418\uACE0, P\u2260NP\uC778 \uACBD\uC6B0\uB294 P\uC640 NP-\uB09C\uD574\uB294 \uC11C\uB85C\uC18C\uAC00 \uB41C\uB2E4. NP-\uB09C\uD574 \uC9D1\uD569\uC740 NP\uC5D0 \uC18D\uD558\uC9C0\uB294 \uC54A\uB294\uB2E4. NP\uC5D0 \uC18D\uD558\uC9C0 \uC54A\uB294 NP-\uB09C\uD574 \uBB38\uC81C\uC758 \uD55C \uC608\uB85C\uB294 \uC815\uC9C0 \uBB38\uC81C\uAC00 \uC788\uB2E4. \uB610\uD55C, NP-\uB09C\uD574 \uC9D1\uD569\uC740 \uD310\uC815 \uBB38\uC81C \uBFD0\uB9CC\uC774 \uC544\uB2C8\uB77C \uCD5C\uC801\uD654 \uBB38\uC81C \uB4F1 \uB2E4\uB978 \uD615\uD0DC\uC758 \uBB38\uC81C\uAC00 \uD3EC\uD568\uB41C\uB2E4."@ko . . . . . . . . . . . "En , NP-peza (Ne-determina Polinomo-tempo peza) nomas la klason de , kiu enhavas \u0109iujn problemojn H, tia, ke por \u0109iu decida problemo L en ekzistas al H, skribata kiel . Neformale, \u0109i tiu klaso povas esti priskribita kiel enhavanta la decidajn problemojn, kiuj estas \"almena\u016D kiel peza kiel problemoj en \". \u0108i tiu intuicio estas subtenata per la fakto, ke se ni povas trovi algoritmon A, kiu solvas unu el \u0109i tiuj problemoj H en polinoma tempo, ni povas konstrui polinom-tempan algoritmon por \u0109iu problemo L en NP per unue plenumo de la malpligrandi\u011Do de L al H kaj tiam ruligo la algoritmo A. Do, formale, lingvo L estas NP-peza se \u2200L' en NP, . Se \u011Di estas anka\u016D 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\u016D pli pezaj. Komuna eraro estas, pensi, ke la \"NP\" en \"NP-peza\" staras por \"ne-polinomo\". Kvankam \u011Di estas lar\u011De suspektite, ke ne estas polinomo-tempaj algoritmoj por \u0109i tiuj problemoj, tio ne estis pruvita."@eo . . "In teoria della complessit\u00E0, 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\u00F2 essere definita informalmente come la classe dei problemi almeno difficili come i pi\u00F9 difficili problemi delle classi di complessit\u00E0 P e NP. Pi\u00F9 formalmente, un problema \u00E8 NP-difficile se e solo se ogni problema NP \u00E8 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\u00F9 difficili delle classi P/NP. La categoria dei problemi NP-difficili, a differenza delle classi P, NP e degli NP-completi, non \u00E8 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 \u00E8 equivalente a un problema notoriamente NP-difficile significa dimostrare che \u00E8 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 \u00E8 un elemento essenziale della ricerca su alcuni dei principali problemi aperti della complessit\u00E0."@it . . . "NP-\u0441\u043A\u043B\u0430\u0434\u043D\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 (\u0430\u043D\u0433\u043B. NP-hard) \u2014 \u0437\u0430\u0434\u0430\u0447\u0430 \u043D\u0435 \u043C\u0435\u043D\u0448 \u0441\u043A\u043B\u0430\u0434\u043D\u0430 \u043D\u0456\u0436 NP-\u043F\u043E\u0432\u043D\u0430. \u0417\u0430\u0434\u0430\u0447\u0430 \u03A0 \u0454 NP-\u0441\u043A\u043B\u0430\u0434\u043D\u043E\u044E, \u044F\u043A\u0449\u043E \u0456\u0441\u043D\u0443\u0454 NP-\u043F\u043E\u0432\u043D\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u03A01, \u0449\u043E \u0437\u0432\u043E\u0434\u0438\u0442\u044C\u0441\u044F \u0434\u043E \u03A0."@uk . . "1098421480"^^ . . "Problem NP-trudny (NPH, ang. NP-Hard) \u2013 problem obliczeniowy, kt\u00F3rego rozwi\u0105zanie jest co najmniej tak trudne, jak rozwi\u0105zanie ka\u017Cdego problemu z klasy NP (ca\u0142ej klasy NP). Formalna definicja problemu NP-trudnego jest nast\u0119puj\u0105ca: Problem jest NP-trudny, je\u017Celi pewien problem NP-zupe\u0142ny jest do niego redukowalny wielomianow\u0105 transformacj\u0105 Turinga. Wraz z definicjami klas problem\u00F3w NP i NP-zupe\u0142nych ma to nast\u0119puj\u0105ce konsekwencje:"@pl . . "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\u2260NP, 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 . "En teoria de la complexitat, la classe de complexitat NP-Hard \u00E9s el conjunt dels problemes de decisi\u00F3 tals que si H \u00E9s un problema d'aquesta classe, tot problema L de NP es pot transformar en H en temps polin\u00F2mic. Es pot veure aquesta classe com el conjunt de problemes com a m\u00EDnim tan dif\u00EDcils com els NP. Com a conseq\u00FC\u00E8ncia de la seva definici\u00F3, si es troba un algorisme de temps polin\u00F2mic que solucioni un problema NP-hard, donaria una soluci\u00F3 polin\u00F2mica a tots els problemes NP, cosa poc probable, ja que tots es consideren massa dif\u00EDcils."@ca . . "En , NP-peza (Ne-determina Polinomo-tempo peza) nomas la klason de , kiu enhavas \u0109iujn problemojn H, tia, ke por \u0109iu decida problemo L en ekzistas al H, skribata kiel . Neformale, \u0109i tiu klaso povas esti priskribita kiel enhavanta la decidajn problemojn, kiuj estas \"almena\u016D kiel peza kiel problemoj en \". \u0108i tiu intuicio estas subtenata per la fakto, ke se ni povas trovi algoritmon A, kiu solvas unu el \u0109i tiuj problemoj H en polinoma tempo, ni povas konstrui polinom-tempan algoritmon por \u0109iu problemo L en NP per unue plenumo de la malpligrandi\u011Do de L al H kaj tiam ruligo la algoritmo A."@eo . "NP-dif\u00EDcil (ou NP-hard, ou NP-complexo) na teoria da complexidade computacional, \u00E9 uma classe de problemas que s\u00E3o, informalmente, \"Pelo menos t\u00E3o dif\u00EDceis quanto os problemas mais dif\u00EDceis em NP\". Um problema H \u00E9 NP-dif\u00EDcil se e somente se (sse) existe um problema NP-completo L que \u00E9 para H (i.e., L?=?TH). Em outras palavras, L pode ser resolvido em por uma M\u00E1quina de Turing n\u00E3o determin\u00EDstica com um or\u00E1culo para H. Informalmente, podemos pensar em um algoritmo que pode chamar tal M\u00E1quina de Turing N\u00E3o-Determin\u00EDstica 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\u00EDceis podem ser de qualquer tipo: problemas de decis\u00E3o, problemas de pesquisa ou problemas de otimiza\u00E7\u00E3o."@pt . . . . "54681"^^ . . . . "\u0645\u0633\u0627\u0626\u0644 NP \u0635\u0639\u0628\u0629 \u0641\u064A \u0639\u0644\u0645 \u0627\u0644\u062A\u0639\u0642\u064A\u062F \u0627\u0644\u062D\u0633\u0627\u0628\u064A \u0647\u064A \u0645\u062C\u0645\u0648\u0639\u0629 \u0645\u0633\u0627\u0626\u0644 \u062D\u064A\u062B \u0627\u0646\u0647 \u064A\u0645\u0643\u0646 \u0627\u062E\u062A\u0635\u0627\u0631 \u0643\u0644 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0641\u064A NP \u0627\u0644\u064A\u0647\u0627. \u0648\u0644\u0647\u0630\u0647 \u0627\u0644\u0645\u062C\u0645\u0648\u0639\u0629 \u0627\u0647\u0645\u064A\u0629 \u0639\u0638\u064A\u0645\u0629 \u0641\u064A \u0639\u0644\u0645 \u0627\u0644\u062D\u0627\u0633\u0648\u0628 \u0648\u0627\u0644\u0631\u064A\u0627\u0636\u064A\u0627\u062A \u0644\u0645\u0627 \u0644\u0647\u0627 \u0645\u0646 \u062A\u0627\u062B\u064A\u0631 \u0639\u0644\u0649 \u0643\u062B\u064A\u0631 \u0645\u0646 \u0627\u0644\u0646\u0648\u0627\u062D\u064A \u0627\u0644\u0639\u0645\u0644\u064A\u0629 \u0641\u064A\u0647 \u0625\u0630 \u0627\u0646\u0647 \u062A\u0645\u062A\u062F \u0647\u0630\u0647 \u0627\u0644\u0645\u062C\u0645\u0648\u0639\u0629 \u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u062A\u062E\u0637\u064A\u0637 \u0648\u0645\u0639\u0627\u0644\u062C\u0629 \u0627\u0644\u0635\u0648\u0631 \u0627\u0644\u0631\u0642\u0645\u064A\u0629 \u0648\u062A\u062D\u0633\u064A\u0646 \u0645\u064F\u0635\u0631\u0641... \u0645\u0644\u0627\u062D\u0638\u0629: \u0628\u0634\u0643\u0644 \u0639\u0627\u0645 NP \u0643\u0627\u0645\u0644\u0629 \u2260 NP \u0635\u0639\u0628\u0629 \u0644\u0630\u0627 \u064A\u062C\u0628 \u0627\u0644\u0627\u062E\u0630 \u0628\u0627\u0644\u062D\u0633\u0628\u0627\u0646 \u0627\u0646\u0647 \u0625\u0630\u0627 NP = P \u0641\u0647\u0630\u0627 \u0644\u0627 \u064A\u0639\u0646\u064A \u0628\u0627\u0644\u0636\u0631\u0648\u0631\u0629 \u0623\u0646\u064E\u0651 \u0643\u0644 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u062A\u064A \u0647\u064A NP \u0635\u0639\u0628\u0629 \u0623\u064A\u0636\u0627 \u064A\u0645\u0643\u0646 \u062D\u0644\u0647\u0627 \u0628\u0648\u0642\u062A \u062D\u062F\u0648\u062F\u064A (\u0623\u064A \u0627\u0646\u0647\u0627 \u062A\u0627\u0628\u0639\u0629 \u0644- P)."@ar . . "NP-\u0442\u0440\u0443\u0434\u043D\u043E\u0441\u0442\u044C"@ru . . "\u0645\u0633\u0627\u0626\u0644 NP \u0635\u0639\u0628\u0629 \u0641\u064A \u0639\u0644\u0645 \u0627\u0644\u062A\u0639\u0642\u064A\u062F \u0627\u0644\u062D\u0633\u0627\u0628\u064A \u0647\u064A \u0645\u062C\u0645\u0648\u0639\u0629 \u0645\u0633\u0627\u0626\u0644 \u062D\u064A\u062B \u0627\u0646\u0647 \u064A\u0645\u0643\u0646 \u0627\u062E\u062A\u0635\u0627\u0631 \u0643\u0644 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0641\u064A NP \u0627\u0644\u064A\u0647\u0627. \u0648\u0644\u0647\u0630\u0647 \u0627\u0644\u0645\u062C\u0645\u0648\u0639\u0629 \u0627\u0647\u0645\u064A\u0629 \u0639\u0638\u064A\u0645\u0629 \u0641\u064A \u0639\u0644\u0645 \u0627\u0644\u062D\u0627\u0633\u0648\u0628 \u0648\u0627\u0644\u0631\u064A\u0627\u0636\u064A\u0627\u062A \u0644\u0645\u0627 \u0644\u0647\u0627 \u0645\u0646 \u062A\u0627\u062B\u064A\u0631 \u0639\u0644\u0649 \u0643\u062B\u064A\u0631 \u0645\u0646 \u0627\u0644\u0646\u0648\u0627\u062D\u064A \u0627\u0644\u0639\u0645\u0644\u064A\u0629 \u0641\u064A\u0647 \u0625\u0630 \u0627\u0646\u0647 \u062A\u0645\u062A\u062F \u0647\u0630\u0647 \u0627\u0644\u0645\u062C\u0645\u0648\u0639\u0629 \u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u062A\u062E\u0637\u064A\u0637 \u0648\u0645\u0639\u0627\u0644\u062C\u0629 \u0627\u0644\u0635\u0648\u0631 \u0627\u0644\u0631\u0642\u0645\u064A\u0629 \u0648\u062A\u062D\u0633\u064A\u0646 \u0645\u064F\u0635\u0631\u0641... \u0645\u0644\u0627\u062D\u0638\u0629: \u0628\u0634\u0643\u0644 \u0639\u0627\u0645 NP \u0643\u0627\u0645\u0644\u0629 \u2260 NP \u0635\u0639\u0628\u0629 \u0644\u0630\u0627 \u064A\u062C\u0628 \u0627\u0644\u0627\u062E\u0630 \u0628\u0627\u0644\u062D\u0633\u0628\u0627\u0646 \u0627\u0646\u0647 \u0625\u0630\u0627 NP = P \u0641\u0647\u0630\u0627 \u0644\u0627 \u064A\u0639\u0646\u064A \u0628\u0627\u0644\u0636\u0631\u0648\u0631\u0629 \u0623\u0646\u064E\u0651 \u0643\u0644 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u062A\u064A \u0647\u064A NP \u0635\u0639\u0628\u0629 \u0623\u064A\u0636\u0627 \u064A\u0645\u0643\u0646 \u062D\u0644\u0647\u0627 \u0628\u0648\u0642\u062A \u062D\u062F\u0648\u062F\u064A (\u0623\u064A \u0627\u0646\u0647\u0627 \u062A\u0627\u0628\u0639\u0629 \u0644- P)."@ar . . "NP\u56F0\u96E3\uFF08\u30A8\u30CC\u30D4\u30FC\u3053\u3093\u306A\u3093\u3001\u82F1: NP-hard\uFF09\u3068\u306F\u8A08\u7B97\u91CF\u7406\u8AD6\u306B\u304A\u3044\u3066\u3001\u554F\u984C\u304C\u300CNP\u306B\u5C5E\u3059\u308B\u4EFB\u610F\u306E\u554F\u984C\u3068\u6BD4\u3079\u3066\u3001\u5C11\u306A\u304F\u3068\u3082\u540C\u7B49\u4EE5\u4E0A\u306B\u96E3\u3057\u3044\u300D\u3053\u3068\u3067\u3042\u308B\u3002\u6B63\u78BA\u306B\u3044\u3046\u3068\u3001\u3042\u308B\u554F\u984C H \u304CNP\u56F0\u96E3\u3067\u3042\u308B\u3068\u306F\u3001\u300CNP\u306B\u5C5E\u3059\u308B\u4EFB\u610F\u306E\u554F\u984C L \u304C H \u3078\u5E30\u7740\u53EF\u80FD\u3067\u3042\u308B\u300D\u3068\u5B9A\u7FA9\u3055\u308C\u308B\u3002\u3053\u306E\u300C\u5E30\u7740\u300D\u306E\u5B9A\u7FA9\u3068\u3057\u3066\u4F55\u3092\u7528\u3044\u308B\u304B\u306B\u3088\u308A\u5FAE\u5999\u306B\u5B9A\u7FA9\u304C\u7570\u306A\u308B\u3053\u3068\u306B\u306A\u308B\u304C\u3001\u4F8B\u3048\u3070\u591A\u9805\u5F0F\u6642\u9593\u591A\u5BFE\u4E00\u5E30\u7740\u3084\u591A\u9805\u5F0F\u6642\u9593\u30C1\u30E5\u30FC\u30EA\u30F3\u30B0\u5E30\u7740\u3092\u7528\u3044\u308B\u3002\u3082\u3057\u3082\u3042\u308BNP\u56F0\u96E3\u554F\u984C\u3092\u89E3\u3051\u308B\u591A\u9805\u5F0F\u6642\u9593\u306E\u6A5F\u68B0\u304C\u5B58\u5728\u3059\u308C\u3070\u3001\u305D\u308C\u3092\u5229\u7528\u3059\u308C\u3070NP\u306B\u5C5E\u3059\u308B\u4EFB\u610F\u306E\u554F\u984C\u3092\u591A\u9805\u5F0F\u6642\u9593\u3067\u89E3\u304F\u3053\u3068\u304C\u3067\u304D\u308B\u3002 NP\u5B8C\u5168\u554F\u984C\u3068\u306F\u3001NP\u56F0\u96E3\u3067\u3042\u308A\u3001\u304B\u3064NP\u306B\u5C5E\u3059\u308B\u554F\u984C\u3067\u3042\u308B\u3002\u3053\u308C\u3068\u306F\u7570\u306A\u308A\u3001\u3042\u308B\u554F\u984C\u304CNP\u56F0\u96E3\u3067\u3042\u3063\u3066\u3082NP\u306B\u5C5E\u3059\u308B\u3068\u306F\u9650\u3089\u306A\u3044\u3002NP\u306F\u6C7A\u5B9A\u554F\u984C\u306E\u30AF\u30E9\u30B9\u306A\u306E\u3067NP\u5B8C\u5168\u3082\u307E\u305F\u6C7A\u5B9A\u554F\u984C\u306B\u9650\u3089\u308C\u308B\u304C\u3001\u5B9A\u7FA9\u306B\u7528\u3044\u308B\u5E30\u7740\u306E\u7A2E\u985E\u306B\u3088\u3063\u3066\u306FNP\u56F0\u96E3\u306B\u306F\u6C7A\u5B9A\u554F\u984C\u3001(en)\u3001\u7D44\u5408\u305B\u6700\u9069\u5316\u554F\u984C\u306A\u3069\u69D8\u3005\u306A\u554F\u984C\u304C\u5C5E\u3057\u3046\u308B\u3002 \u4E0A\u306B\u6319\u3052\u305F\u5B9A\u7FA9\u304B\u3089\u3001\u554F\u984C H \u304CNP\u56F0\u96E3\u3067\u3042\u308B\u3068\u304D\u306B\u306F\u6B21\u306E\u3053\u3068\u304C\u8A00\u3048\u308B\uFF08\u4EE5\u4E0B\u306F\u5B9A\u7FA9\u3067\u306F\u306A\u304F\u4E3B\u5F35\uFF09\u3002 \n* \u3059\u3079\u3066\u306ENP\u5B8C\u5168\u554F\u984C\u306F H \u306B\u9084\u5143\u3057\u3066\u591A\u9805\u5F0F\u6642\u9593\u3067\u89E3\u3051\u308B\u3002\u307E\u305FNP\u306B\u5C5E\u3059\u308B\u5168\u3066\u306E\u554F\u984C\u3082 H \u306B\u9084\u5143\u3067\u304D\u308B\u3002 \n* \u3082\u3057\u6700\u9069\u5316\u554F\u984C H \u306E\u7279\u6B8A\u4F8B\u3068\u3057\u3066NP\u5B8C\u5168\u306A\u6C7A\u5B9A\u554F\u984C L \u3092\u8003\u3048\u3089\u308C\u308B\u306A\u3089\u3001H \u306FNP\u56F0\u96E3\u3067\u3042\u308B\u3002 NP\u56F0\u96E3\u306A\u7D44\u5408\u305B\u6700\u9069\u5316\u554F\u984C\u306F\u3001\u4E00\u822C\u306B\u6700\u9069\u89E3\u3092\u6C42\u3081\u308B\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u304C\u8A08\u7B97\u5B8C\u4E86\u307E\u3067\u306B\u6307\u6570\u95A2\u6570\u6642\u9593\u3092\u5FC5\u8981\u3068\u3059\u308B\u306A\u3069\u3057\u3066\u3001\u975E\u5E38\u306B\u56F0\u96E3\u3067\u3042\u308B\u3068\u8003\u3048\u3089\u308C\u3066\u3044\u308B\u305F\u3081\u3001\u8FD1\u4F3C\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u304C\u591A\u6570\u8003\u6848\u3055\u308C\u3066\u3044\u308B\u3002\u307E\u305F\u3001\u6570\u7406\u7684\u306B\u89E3\u304F\u5F93\u6765\u304B\u3089\u306E\u30A2\u30D7\u30ED\u30FC\u30C1\u306E\u4ED6\u306B\u3001\u30C7\u30A3\u30FC\u30D7\u30E9\u30FC\u30CB\u30F3\u30B0\u306E\u5FDC\u7528\u306A\u3069\u3082\u76DB\u3093\u306B\u884C\u308F\u308C\u3066\u3044\u308B\u3002\u91CF\u5B50\u30B3\u30F3\u30D4\u30E5\u30FC\u30BF\u3067\u306F\u6700\u9069\u89E3\u3092\u30EA\u30A2\u30EB\u30BF\u30A4\u30E0\u3067\u6C42\u3081\u308B\u65B9\u6CD5\u3082\u8A66\u307F\u3089\u308C\u3066\u3044\u308B\u3002"@ja . . . . . "NP-\uB09C\uD574"@ko . "NP-\u0441\u043A\u043B\u0430\u0434\u043D\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 (\u0430\u043D\u0433\u043B. NP-hard) \u2014 \u0437\u0430\u0434\u0430\u0447\u0430 \u043D\u0435 \u043C\u0435\u043D\u0448 \u0441\u043A\u043B\u0430\u0434\u043D\u0430 \u043D\u0456\u0436 NP-\u043F\u043E\u0432\u043D\u0430. \u0417\u0430\u0434\u0430\u0447\u0430 \u03A0 \u0454 NP-\u0441\u043A\u043B\u0430\u0434\u043D\u043E\u044E, \u044F\u043A\u0449\u043E \u0456\u0441\u043D\u0443\u0454 NP-\u043F\u043E\u0432\u043D\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u03A01, \u0449\u043E \u0437\u0432\u043E\u0434\u0438\u0442\u044C\u0441\u044F \u0434\u043E \u03A0."@uk . . . . "NP-\u0441\u043A\u043B\u0430\u0434\u043D\u0430 \u0437\u0430\u0434\u0430\u0447\u0430"@uk . . . . . "NP\u56F0\u96BE\uFF08NP-hardness, non-deterministic polynomial-time hardness\uFF09\u95EE\u9898\u662F\u8BA1\u7B97\u590D\u6742\u6027\u7406\u8BBA\u4E2D\u6700\u91CD\u8981\u7684\u590D\u6742\u6027\u7C7B\u4E4B\u4E00\u3002\u5982\u679C\u6240\u6709NP\u95EE\u9898\u90FD\u53EF\u4EE5\u591A\u9879\u5F0F\u65F6\u95F4\u5F52\u7EA6\u5230\u67D0\u4E2A\u95EE\u9898\uFF0C\u5219\u79F0\u8BE5\u95EE\u9898\u4E3ANP\u56F0\u96BE\u3002 \u56E0\u4E3ANP\u56F0\u96BE\u95EE\u9898\u672A\u5FC5\u53EF\u4EE5\u5728\u591A\u9879\u5F0F\u65F6\u95F4\u5185\u9A8C\u8BC1\u4E00\u4E2A\u89E3\u7684\u6B63\u786E\u6027\uFF08\u5373\u4E0D\u4E00\u5B9A\u662FNP\u95EE\u9898\uFF09\uFF0C\u56E0\u6B64\u5373\u4F7FNP\u5B8C\u5168\u95EE\u9898\u6709\u591A\u9879\u5F0F\u65F6\u95F4\u7684\u89E3\uFF08P=NP\uFF09\uFF0CNP\u56F0\u96BE\u95EE\u9898\u4F9D\u7136\u53EF\u80FD\u6CA1\u6709\u591A\u9879\u5F0F\u65F6\u95F4\u7684\u89E3\u3002\u56E0\u6B64NP\u56F0\u96BE\u95EE\u9898\u201C\u81F3\u5C11\u4E0ENP\u5B8C\u5168\u95EE\u9898\u4E00\u6837\u96BE\u201D\u3002"@zh . "Problem NP-trudny"@pl . . "NP-dif\u00EDcil"@ca . "NP\u56F0\u96BE"@zh . . . . . . . "NP\u56F0\u96BE\uFF08NP-hardness, non-deterministic polynomial-time hardness\uFF09\u95EE\u9898\u662F\u8BA1\u7B97\u590D\u6742\u6027\u7406\u8BBA\u4E2D\u6700\u91CD\u8981\u7684\u590D\u6742\u6027\u7C7B\u4E4B\u4E00\u3002\u5982\u679C\u6240\u6709NP\u95EE\u9898\u90FD\u53EF\u4EE5\u591A\u9879\u5F0F\u65F6\u95F4\u5F52\u7EA6\u5230\u67D0\u4E2A\u95EE\u9898\uFF0C\u5219\u79F0\u8BE5\u95EE\u9898\u4E3ANP\u56F0\u96BE\u3002 \u56E0\u4E3ANP\u56F0\u96BE\u95EE\u9898\u672A\u5FC5\u53EF\u4EE5\u5728\u591A\u9879\u5F0F\u65F6\u95F4\u5185\u9A8C\u8BC1\u4E00\u4E2A\u89E3\u7684\u6B63\u786E\u6027\uFF08\u5373\u4E0D\u4E00\u5B9A\u662FNP\u95EE\u9898\uFF09\uFF0C\u56E0\u6B64\u5373\u4F7FNP\u5B8C\u5168\u95EE\u9898\u6709\u591A\u9879\u5F0F\u65F6\u95F4\u7684\u89E3\uFF08P=NP\uFF09\uFF0CNP\u56F0\u96BE\u95EE\u9898\u4F9D\u7136\u53EF\u80FD\u6CA1\u6709\u591A\u9879\u5F0F\u65F6\u95F4\u7684\u89E3\u3002\u56E0\u6B64NP\u56F0\u96BE\u95EE\u9898\u201C\u81F3\u5C11\u4E0ENP\u5B8C\u5168\u95EE\u9898\u4E00\u6837\u96BE\u201D\u3002"@zh . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0432\u044B\u0447\u0438\u0441\u043B\u0435\u043D\u0438\u0439 NP-\u0442\u0440\u0443\u0434\u043D\u043E\u0441\u0442\u044C (\u043D\u0435\u0434\u0435\u0442\u0435\u0440\u043C\u0438\u043D\u0438\u0440\u043E\u0432\u0430\u043D\u043D\u0430\u044F \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u0430\u044F \u0442\u0440\u0443\u0434\u043D\u043E\u0441\u0442\u044C \u043F\u043E \u0432\u0440\u0435\u043C\u0435\u043D\u0438) \u044F\u0432\u043B\u044F\u0435\u0442\u0441\u044F \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u044F\u044E\u0449\u0438\u043C \u0441\u0432\u043E\u0439\u0441\u0442\u0432\u043E\u043C \u043A\u043B\u0430\u0441\u0441\u0430 \u0437\u0430\u0434\u0430\u0447, \u043A\u043E\u0442\u043E\u0440\u044B\u0435, \u043D\u0435\u0444\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u043E, \u00AB\u043F\u043E \u043A\u0440\u0430\u0439\u043D\u0435\u0439 \u043C\u0435\u0440\u0435 \u0442\u0430\u043A \u0436\u0435 \u0441\u043B\u043E\u0436\u043D\u044B, \u043A\u0430\u043A \u0441\u0430\u043C\u044B\u0435 \u0441\u043B\u043E\u0436\u043D\u044B\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0432 NP\u00BB. \u041F\u0440\u043E\u0441\u0442\u044B\u043C \u043F\u0440\u0438\u043C\u0435\u0440\u043E\u043C NP-\u0442\u0440\u0443\u0434\u043D\u043E\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u044F\u0432\u043B\u044F\u0435\u0442\u0441\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u043E \u0441\u0443\u043C\u043C\u0435 \u043F\u043E\u0434\u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432. \u0421\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044F \u0447\u0442\u043E \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u0441 \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u044B\u043C \u0432\u0440\u0435\u043C\u0435\u043D\u0435\u043C \u0434\u043B\u044F NP-\u0442\u0440\u0443\u0434\u043D\u044B\u0445 \u0437\u0430\u0434\u0430\u0447 \u043D\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u043D\u043E \u044D\u0442\u043E \u043D\u0435 \u0434\u043E\u043A\u0430\u0437\u0430\u043D\u043E (\u0441\u043C. \u043F\u0440\u043E\u0431\u043B\u0435\u043C\u0443 P\u2260NP). \u0411\u043E\u043B\u0435\u0435 \u0442\u043E\u0433\u043E, \u043A\u043B\u0430\u0441\u0441 P, \u0432 \u043A\u043E\u0442\u043E\u0440\u043E\u043C \u0432\u0441\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0440\u0435\u0448\u0430\u044E\u0442\u0441\u044F \u0437\u0430 \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u043E\u0435 \u0432\u0440\u0435\u043C\u044F, \u0441\u043E\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044F \u0432 \u043A\u043B\u0430\u0441\u0441\u0435 NP."@ru . "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 \u2014 per definitie \u2014 wel het geval. Voorbeelden van NP-moeilijke beslissingsproblemen zijn MAX-SAT en het handelsreizigersprobleem."@nl . "En teor\u00EDa de la complejidad computacional, la clase de complejidad NP-hard (o NP-complejo, o NP-dif\u00EDcil) es el conjunto de los problemas de decisi\u00F3n 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\u00F3n que son como m\u00EDnimo tan dif\u00EDciles como un problema de NP. Esta afirmaci\u00F3n se justifica porque si podemos encontrar un algoritmo A que resuelve uno de los problemas H de NP-hard en tiempo polin\u00F3mico, entonces es posible construir un algoritmo que trabaje en tiempo polin\u00F3mico para cualquier problema de NP ejecutando primero la reducci\u00F3n de este problema en H y luego ejecutando el algoritmo A. Asumiendo que el lenguaje L es NP-completo, 1. L est\u00E1 en NP2. \u2200L' en NP, L' \u2264 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\u00F3n entre NP y NP-hard. Algunas consecuencias de la definici\u00F3n son: \n* Como NP-completo es el tipo m\u00E1s costoso de la clase NP, el problema H es al menos tan costoso como NP, pero H no tiene por qu\u00E9 estar en NP y por tanto no tiene por qu\u00E9 ser un problema de decisi\u00F3n. \n* Los problemas NP-completos se pueden transformar unos en otros por una reducci\u00F3n polin\u00F3mica, los problemas NP-completos pueden ser resueltos en tiempo polin\u00F3mico por reducci\u00F3n a H, as\u00ED que todos los problemas de NP se reducen a H; sin embargo, esto implica utilizar dos tipos diferentes de transformaciones: de problemas de decisi\u00F3n NP-completos a un problema NP-completo L por transformaciones polin\u00F3micas, y de L a H por reducci\u00F3n polin\u00F3mica de Turing. \n* Si hay alg\u00FAn algoritmo polin\u00F3mico para resolver un problema NP-hard, entonces hay algoritmos para resolver todos los problemas de NP en tiempo polin\u00F3mico, esto significar\u00EDa que P=NP. \n* Si un problema de optimizaci\u00F3n H tiene una versi\u00F3n NP-completa, entonces H es NP-hard. \n* Si H pertenece a NP, entonces H pertenece tambi\u00E9n a NP-completo porque en este caso existe una transformaci\u00F3n polin\u00F3mica de Turing que cumple los requisitos de las transformaciones polin\u00F3micas. Un error com\u00FAn es pensar que NP en NP-hard quiere decir no polin\u00F3mico, ya que aunque hay serias sospechas sobre que no existen algoritmos para resolver estos problemas en tiempo polin\u00F3mico, esto nunca ha sido demostrado."@es . "In teoria della complessit\u00E0, 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\u00F2 essere definita informalmente come la classe dei problemi almeno difficili come i pi\u00F9 difficili problemi delle classi di complessit\u00E0 P e NP. Pi\u00F9 formalmente, un problema \u00E8 NP-difficile se e solo se ogni problema NP \u00E8 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\u00F9 difficili delle classi P/NP."@it . . . "NP\u56F0\u96E3\uFF08\u30A8\u30CC\u30D4\u30FC\u3053\u3093\u306A\u3093\u3001\u82F1: NP-hard\uFF09\u3068\u306F\u8A08\u7B97\u91CF\u7406\u8AD6\u306B\u304A\u3044\u3066\u3001\u554F\u984C\u304C\u300CNP\u306B\u5C5E\u3059\u308B\u4EFB\u610F\u306E\u554F\u984C\u3068\u6BD4\u3079\u3066\u3001\u5C11\u306A\u304F\u3068\u3082\u540C\u7B49\u4EE5\u4E0A\u306B\u96E3\u3057\u3044\u300D\u3053\u3068\u3067\u3042\u308B\u3002\u6B63\u78BA\u306B\u3044\u3046\u3068\u3001\u3042\u308B\u554F\u984C H \u304CNP\u56F0\u96E3\u3067\u3042\u308B\u3068\u306F\u3001\u300CNP\u306B\u5C5E\u3059\u308B\u4EFB\u610F\u306E\u554F\u984C L \u304C H \u3078\u5E30\u7740\u53EF\u80FD\u3067\u3042\u308B\u300D\u3068\u5B9A\u7FA9\u3055\u308C\u308B\u3002\u3053\u306E\u300C\u5E30\u7740\u300D\u306E\u5B9A\u7FA9\u3068\u3057\u3066\u4F55\u3092\u7528\u3044\u308B\u304B\u306B\u3088\u308A\u5FAE\u5999\u306B\u5B9A\u7FA9\u304C\u7570\u306A\u308B\u3053\u3068\u306B\u306A\u308B\u304C\u3001\u4F8B\u3048\u3070\u591A\u9805\u5F0F\u6642\u9593\u591A\u5BFE\u4E00\u5E30\u7740\u3084\u591A\u9805\u5F0F\u6642\u9593\u30C1\u30E5\u30FC\u30EA\u30F3\u30B0\u5E30\u7740\u3092\u7528\u3044\u308B\u3002\u3082\u3057\u3082\u3042\u308BNP\u56F0\u96E3\u554F\u984C\u3092\u89E3\u3051\u308B\u591A\u9805\u5F0F\u6642\u9593\u306E\u6A5F\u68B0\u304C\u5B58\u5728\u3059\u308C\u3070\u3001\u305D\u308C\u3092\u5229\u7528\u3059\u308C\u3070NP\u306B\u5C5E\u3059\u308B\u4EFB\u610F\u306E\u554F\u984C\u3092\u591A\u9805\u5F0F\u6642\u9593\u3067\u89E3\u304F\u3053\u3068\u304C\u3067\u304D\u308B\u3002 NP\u5B8C\u5168\u554F\u984C\u3068\u306F\u3001NP\u56F0\u96E3\u3067\u3042\u308A\u3001\u304B\u3064NP\u306B\u5C5E\u3059\u308B\u554F\u984C\u3067\u3042\u308B\u3002\u3053\u308C\u3068\u306F\u7570\u306A\u308A\u3001\u3042\u308B\u554F\u984C\u304CNP\u56F0\u96E3\u3067\u3042\u3063\u3066\u3082NP\u306B\u5C5E\u3059\u308B\u3068\u306F\u9650\u3089\u306A\u3044\u3002NP\u306F\u6C7A\u5B9A\u554F\u984C\u306E\u30AF\u30E9\u30B9\u306A\u306E\u3067NP\u5B8C\u5168\u3082\u307E\u305F\u6C7A\u5B9A\u554F\u984C\u306B\u9650\u3089\u308C\u308B\u304C\u3001\u5B9A\u7FA9\u306B\u7528\u3044\u308B\u5E30\u7740\u306E\u7A2E\u985E\u306B\u3088\u3063\u3066\u306FNP\u56F0\u96E3\u306B\u306F\u6C7A\u5B9A\u554F\u984C\u3001(en)\u3001\u7D44\u5408\u305B\u6700\u9069\u5316\u554F\u984C\u306A\u3069\u69D8\u3005\u306A\u554F\u984C\u304C\u5C5E\u3057\u3046\u308B\u3002 \u4E0A\u306B\u6319\u3052\u305F\u5B9A\u7FA9\u304B\u3089\u3001\u554F\u984C H \u304CNP\u56F0\u96E3\u3067\u3042\u308B\u3068\u304D\u306B\u306F\u6B21\u306E\u3053\u3068\u304C\u8A00\u3048\u308B\uFF08\u4EE5\u4E0B\u306F\u5B9A\u7FA9\u3067\u306F\u306A\u304F\u4E3B\u5F35\uFF09\u3002 \n* \u3059\u3079\u3066\u306ENP\u5B8C\u5168\u554F\u984C\u306F H \u306B\u9084\u5143\u3057\u3066\u591A\u9805\u5F0F\u6642\u9593\u3067\u89E3\u3051\u308B\u3002\u307E\u305FNP\u306B\u5C5E\u3059\u308B\u5168\u3066\u306E\u554F\u984C\u3082 H \u306B\u9084\u5143\u3067\u304D\u308B\u3002 \n* \u3082\u3057\u6700\u9069\u5316\u554F\u984C H \u306E\u7279\u6B8A\u4F8B\u3068\u3057\u3066NP\u5B8C\u5168\u306A\u6C7A\u5B9A\u554F\u984C L \u3092\u8003\u3048\u3089\u308C\u308B\u306A\u3089\u3001H \u306FNP\u56F0\u96E3\u3067\u3042\u308B\u3002"@ja . . . . "NP-hard"@es . . . . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0432\u044B\u0447\u0438\u0441\u043B\u0435\u043D\u0438\u0439 NP-\u0442\u0440\u0443\u0434\u043D\u043E\u0441\u0442\u044C (\u043D\u0435\u0434\u0435\u0442\u0435\u0440\u043C\u0438\u043D\u0438\u0440\u043E\u0432\u0430\u043D\u043D\u0430\u044F \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u0430\u044F \u0442\u0440\u0443\u0434\u043D\u043E\u0441\u0442\u044C \u043F\u043E \u0432\u0440\u0435\u043C\u0435\u043D\u0438) \u044F\u0432\u043B\u044F\u0435\u0442\u0441\u044F \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u044F\u044E\u0449\u0438\u043C \u0441\u0432\u043E\u0439\u0441\u0442\u0432\u043E\u043C \u043A\u043B\u0430\u0441\u0441\u0430 \u0437\u0430\u0434\u0430\u0447, \u043A\u043E\u0442\u043E\u0440\u044B\u0435, \u043D\u0435\u0444\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u043E, \u00AB\u043F\u043E \u043A\u0440\u0430\u0439\u043D\u0435\u0439 \u043C\u0435\u0440\u0435 \u0442\u0430\u043A \u0436\u0435 \u0441\u043B\u043E\u0436\u043D\u044B, \u043A\u0430\u043A \u0441\u0430\u043C\u044B\u0435 \u0441\u043B\u043E\u0436\u043D\u044B\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0432 NP\u00BB. \u041F\u0440\u043E\u0441\u0442\u044B\u043C \u043F\u0440\u0438\u043C\u0435\u0440\u043E\u043C NP-\u0442\u0440\u0443\u0434\u043D\u043E\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u044F\u0432\u043B\u044F\u0435\u0442\u0441\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u043E \u0441\u0443\u043C\u043C\u0435 \u043F\u043E\u0434\u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432. \u0424\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u043E\u0435 \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u0435\u043D\u0438\u0435: \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0430\u0437\u0440\u0435\u0448\u0438\u043C\u043E\u0441\u0442\u0438 \u044F\u0432\u043B\u044F\u0435\u0442\u0441\u044F NP-\u0442\u0440\u0443\u0434\u043D\u043E\u0439, \u0435\u0441\u043B\u0438 \u043B\u044E\u0431\u0430\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u0438\u0437 NP \u043C\u043E\u0436\u0435\u0442 \u0431\u044B\u0442\u044C \u0441\u0432\u0435\u0434\u0435\u043D\u0430 \u0437\u0430 \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u043E\u0435 \u0432\u0440\u0435\u043C\u044F \u043A . \u042D\u043A\u0432\u0438\u0432\u0430\u043B\u0435\u043D\u0442\u043D\u043E \u0443\u0441\u043B\u043E\u0432\u0438\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442, \u0447\u0442\u043E\u0431\u044B \u043A\u0430\u0436\u0434\u0430\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u0432 NP \u043C\u043E\u0433\u043B\u0430 \u0431\u044B\u0442\u044C \u0440\u0435\u0448\u0435\u043D\u0430 \u0437\u0430 \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u043E\u0435 \u0432\u0440\u0435\u043C\u044F \u0441 \u043E\u0440\u0430\u043A\u0443\u043B\u043E\u043C \u0434\u043B\u044F . \u041A\u0430\u043A \u0441\u043B\u0435\u0434\u0441\u0442\u0432\u0438\u0435, \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0441 \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u044B\u043C \u0432\u0440\u0435\u043C\u0435\u043D\u0435\u043C \u0434\u043B\u044F \u0440\u0435\u0448\u0435\u043D\u0438\u044F \u043B\u044E\u0431\u043E\u0439 NP-\u0442\u0440\u0443\u0434\u043D\u043E\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0434\u0430\u0441\u0442 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u044B \u0441 \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u044B\u043C \u0432\u0440\u0435\u043C\u0435\u043D\u0435\u043C \u0434\u043B\u044F \u0432\u0441\u0435\u0445 \u0437\u0430\u0434\u0430\u0447 \u0432 NP. \u0421\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044F \u0447\u0442\u043E \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u0441 \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u044B\u043C \u0432\u0440\u0435\u043C\u0435\u043D\u0435\u043C \u0434\u043B\u044F NP-\u0442\u0440\u0443\u0434\u043D\u044B\u0445 \u0437\u0430\u0434\u0430\u0447 \u043D\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u043D\u043E \u044D\u0442\u043E \u043D\u0435 \u0434\u043E\u043A\u0430\u0437\u0430\u043D\u043E (\u0441\u043C. \u043F\u0440\u043E\u0431\u043B\u0435\u043C\u0443 P\u2260NP). \u0411\u043E\u043B\u0435\u0435 \u0442\u043E\u0433\u043E, \u043A\u043B\u0430\u0441\u0441 P, \u0432 \u043A\u043E\u0442\u043E\u0440\u043E\u043C \u0432\u0441\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0440\u0435\u0448\u0430\u044E\u0442\u0441\u044F \u0437\u0430 \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u043E\u0435 \u0432\u0440\u0435\u043C\u044F, \u0441\u043E\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044F \u0432 \u043A\u043B\u0430\u0441\u0441\u0435 NP. \u041D\u0435\u043A\u043E\u0442\u043E\u0440\u044B\u0435 NP-\u0442\u0440\u0443\u0434\u043D\u044B\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043E\u043F\u0442\u0438\u043C\u0438\u0437\u0430\u0446\u0438\u0438 \u043C\u043E\u0433\u0443\u0442 \u0431\u044B\u0442\u044C \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u043E \u0430\u043F\u043F\u0440\u043E\u043A\u0441\u0438\u043C\u0438\u0440\u043E\u0432\u0430\u043D\u044B \u0434\u043E \u043D\u0435\u043A\u043E\u0442\u043E\u0440\u043E\u0433\u043E \u043F\u043E\u0441\u0442\u043E\u044F\u043D\u043D\u043E\u0433\u043E (\u043A\u043E\u043D\u0441\u0442\u0430\u043D\u0442\u043D\u043E\u0433\u043E) \u043A\u043E\u044D\u0444\u0444\u0438\u0446\u0438\u0435\u043D\u0442\u0430 \u0430\u043F\u043F\u0440\u043E\u043A\u0441\u0438\u043C\u0430\u0446\u0438\u0438 (\u0432 \u0447\u0430\u0441\u0442\u043D\u043E\u0441\u0442\u0438, \u0432 APX) \u0438\u043B\u0438 \u0434\u0430\u0436\u0435 \u0434\u043E \u043B\u044E\u0431\u043E\u0433\u043E \u043A\u043E\u044D\u0444\u0444\u0438\u0446\u0438\u0435\u043D\u0442\u0430 \u0430\u043F\u043F\u0440\u043E\u043A\u0441\u0438\u043C\u0430\u0446\u0438\u0438 (\u0432 PTAS \u0438\u043B\u0438 FPTAS)."@ru . . . . . . "\u0645\u0633\u0627\u0626\u0644 NP \u0635\u0639\u0628\u0629"@ar . "NP-Schwere"@de . "NP-dif\u00EDcil (ou NP-hard, ou NP-complexo) na teoria da complexidade computacional, \u00E9 uma classe de problemas que s\u00E3o, informalmente, \"Pelo menos t\u00E3o dif\u00EDceis quanto os problemas mais dif\u00EDceis em NP\". Um problema H \u00E9 NP-dif\u00EDcil se e somente se (sse) existe um problema NP-completo L que \u00E9 para H (i.e., L?=?TH). Em outras palavras, L pode ser resolvido em por uma M\u00E1quina de Turing n\u00E3o determin\u00EDstica com um or\u00E1culo para H. Informalmente, podemos pensar em um algoritmo que pode chamar tal M\u00E1quina de Turing N\u00E3o-Determin\u00EDstica 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\u00EDceis podem ser de qualquer tipo: problemas de decis\u00E3o, problemas de pesquisa ou problemas de otimiza\u00E7\u00E3o. Como conseq\u00FC\u00EAncias da defini\u00E7\u00E3o, temos que (note que estas afirma\u00E7\u00F5es n\u00E3o s\u00E3o defini\u00E7\u00F5es): \n* O problema H \u00E9 pelo menos t\u00E3o dif\u00EDcil quanto L, porque H pode ser usado para resolver L; \n* Como L \u00E9 NP-completo e, portanto, o mais dif\u00EDcil na classe NP, tamb\u00E9m o problema H \u00E9 pelo menos t\u00E3o dif\u00EDcil quanto um NP, mas H n\u00E3o tem que estar em NP e, consequentemente, n\u00E3o tem de ser um problema de decis\u00E3o (mesmo que seja um problema de decis\u00E3o, ele n\u00E3o precisa estar em NP); \n* Uma vez que os problemas NP-completos transformam-se uns aos outros por (tamb\u00E9m chamada de transforma\u00E7\u00E3o polinomial), todos os problemas NP-completos podem ser resolvidos em tempo polinomial por uma redu\u00E7\u00E3o para H, Assim, todos os problemas em NP reduzem para H; note-se, por\u00E9m, que isso envolve a combina\u00E7\u00E3o de duas transforma\u00E7\u00F5es diferentes: de problemas de decis\u00E3o NP-completos para o problema NP-completo L por transforma\u00E7\u00E3o polinomial, e de L para H pela redu\u00E7\u00E3o em tempo polinomial de Turing; \n* Se existe um algoritmo polinomial para qualquer problema NP-dif\u00EDcil, ent\u00E3o existem algoritmos polinomiais para todos os problemas em NP, e, portanto, P = NP; \n* Se P != NP, ent\u00E3o os problemas NP-dif\u00EDceis n\u00E3o t\u00EAm solu\u00E7\u00F5es em tempo polinomial, uma vez que P = NP n\u00E3o resolve se os problemas NP-dif\u00EDceis podem ser resolvidos em tempo polinomial; \n* Se um problema de otimiza\u00E7\u00E3o H tem uma vers\u00E3o de decis\u00E3o NP-completo L, ent\u00E3o H \u00E9 NP-dif\u00EDcil. Um erro comum \u00E9 pensar que NP em NP-dif\u00EDcil representa n\u00E3o-polinomial. Embora seja amplamente suspeito de que n\u00E3o existem algoritmos de tempo polinomial para problemas NP-dif\u00EDceis, isto nunca foi provado. Al\u00E9m disso, a classe NP cont\u00E9m tamb\u00E9m todos os problemas que podem ser resolvidos em tempo polinomial."@pt . "NP-dif\u00EDcil"@pt . . "NP-hardness"@en . "En teor\u00EDa de la complejidad computacional, la clase de complejidad NP-hard (o NP-complejo, o NP-dif\u00EDcil) es el conjunto de los problemas de decisi\u00F3n 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\u00F3n que son como m\u00EDnimo tan dif\u00EDciles como un problema de NP. Esta afirmaci\u00F3n se justifica porque si podemos encontrar un algoritmo A que resuelve uno de los problemas H de NP-hard en tiempo polin\u00F3mico, entonces es posible construir un algoritmo que trabaje en tiempo polin\u00F3mico para cualquier problema de NP ejecutando primero la reducci\u00F3n de este problema en H y luego ejecutando el algoritmo A."@es . . . . . . . "En informatique th\u00E9orique, un probl\u00E8me NP-difficile est un probl\u00E8me vers lequel on peut ramener tout probl\u00E8me de la classe NP par une r\u00E9duction polynomiale. S'il est \u00E9galement dans la classe NP, on dit que c'est un probl\u00E8me NP-complet. \n* Portail de l'informatique th\u00E9orique"@fr . "NP-\uB09C\uD574, NP-hard\uB294 NP\uC5D0 \uC18D\uD558\uB294 \uBAA8\uB4E0 \uD310\uC815 \uBB38\uC81C\uB97C \uB2E4\uD56D \uC2DC\uAC04\uC5D0 \uB2E4\uB300\uC77C \uD658\uC0B0\uD560 \uC218 \uC788\uB294 \uBB38\uC81C\uB4E4\uC758 \uC9D1\uD569\uC774\uB2E4. \uB2E4\uC2DC \uB9D0\uD558\uBA74, NP-\uB09C\uD574\uB294 \uC801\uC5B4\uB3C4 \uBAA8\uB4E0 NP \uBB38\uC81C\uB9CC\uD07C\uC740 \uC5B4\uB824\uC6B4 \uBB38\uC81C\uB4E4\uC758 \uC9D1\uD569\uC774\uB2E4. NP-\uB09C\uD574 \uC9D1\uD569\uC5D0 \uC18D\uD558\uB294 \uBB38\uC81C\uAC00 NP\uC5D0\uB3C4 \uC18D\uD558\uBA74 NP-\uC644\uC804\uC5D0 \uC18D\uD55C\uB2E4. \uC989, NP-\uC644\uC804\uC740 NP\uC640 NP-\uB09C\uD574\uC758 \uAD50\uC9D1\uD569\uC774\uB2E4. \uB9CC\uC57D P-NP \uBB38\uC81C\uAC00 P=NP\uB85C \uD480\uB9B0\uB2E4\uBA74 P=NP=NP-\uC644\uC804\uC774\uBBC0\uB85C P\uC640 NP\uB294 NP-\uB09C\uD574\uC758 \uBD80\uBD84\uC9D1\uD569\uC774 \uB418\uACE0, P\u2260NP\uC778 \uACBD\uC6B0\uB294 P\uC640 NP-\uB09C\uD574\uB294 \uC11C\uB85C\uC18C\uAC00 \uB41C\uB2E4. NP-\uB09C\uD574 \uC9D1\uD569\uC740 NP\uC5D0 \uC18D\uD558\uC9C0\uB294 \uC54A\uB294\uB2E4. NP\uC5D0 \uC18D\uD558\uC9C0 \uC54A\uB294 NP-\uB09C\uD574 \uBB38\uC81C\uC758 \uD55C \uC608\uB85C\uB294 \uC815\uC9C0 \uBB38\uC81C\uAC00 \uC788\uB2E4. \uB610\uD55C, NP-\uB09C\uD574 \uC9D1\uD569\uC740 \uD310\uC815 \uBB38\uC81C \uBFD0\uB9CC\uC774 \uC544\uB2C8\uB77C \uCD5C\uC801\uD654 \uBB38\uC81C \uB4F1 \uB2E4\uB978 \uD615\uD0DC\uC758 \uBB38\uC81C\uAC00 \uD3EC\uD568\uB41C\uB2E4."@ko . "En informatique th\u00E9orique, un probl\u00E8me NP-difficile est un probl\u00E8me vers lequel on peut ramener tout probl\u00E8me de la classe NP par une r\u00E9duction polynomiale. S'il est \u00E9galement dans la classe NP, on dit que c'est un probl\u00E8me NP-complet. \n* Portail de l'informatique th\u00E9orique"@fr . . "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 . "NP-difficile"@fr . . "NP-peza"@eo . . "NP-moeilijk"@nl . . . . . "NP-Schwere bezeichnet die Eigenschaft eines algorithmischen Problems, mindestens so schwer l\u00F6sbar zu sein wie die Probleme der Klasse NP. Die Komplexit\u00E4tstheorie, ein Teilgebiet der theoretischen Informatik, besch\u00E4ftigt sich mit der Klassifizierung von Problemen bez\u00FCglich ihrer Komplexit\u00E4t, d. h. der algorithmischen Schwierigkeit, sie zu l\u00F6sen. Eine wichtige Problemklasse ist die Komplexit\u00E4tsklasse NP, die Klasse der Probleme, die mit einer nichtdeterministischen Turingmaschine in Polynomialzeit gel\u00F6st werden k\u00F6nnen. Anschaulich ist NP die Klasse aller Entscheidungsprobleme, f\u00FCr die eine gefundene L\u00F6sung effizient \u00FCberpr\u00FCft werden kann. Ein NP-schweres Problem ist nun mindestens so \u201Eschwer\u201C wie alle Probleme in NP. Das bedeutet, dass ein Algorithmus, der ein NP-schweres Problem effizient (also deterministisch in Polynomialzeit) l\u00F6st, mithilfe einer Polynomialzeitreduktion genutzt werden kann, um ein beliebiges Problem in NP effizient zu l\u00F6sen. Der umgangssprachlich auftretende Begriff NP-H\u00E4rte ist eine Fehl\u00FCbersetzung des englischen NP-hard."@de . . . . . . . "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 \u2014 per definitie \u2014 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 . . . . . .