"NP-volledigheid is een concept uit de complexiteitstheorie. Het is een beschrijving van het inzicht uit de jaren 70 dat er een bepaald verband is tussen de complexiteit van een groot aantal problemen die in de wiskunde en informatica als \"moeilijk\" worden beschouwd. In formele zin is een probleem NP-volledig (ook soms NP-compleet genoemd) als en slechts als \n* het probleem tot de NP behoort. \n* elk ander probleem in NP in polynomiale tijd naar dit probleem kan worden gereduceerd."@nl . . . . . . "En teor\u00EDa de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisi\u00F3n en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas m\u00E1s dif\u00EDciles de NP y muy probablemente no formen parte de la clase de complejidad P. La raz\u00F3n es que de tenerse una soluci\u00F3n polin\u00F3mica para un problema NP-completo, todos los problemas de NP tendr\u00EDan tambi\u00E9n una soluci\u00F3n en tiempo polin\u00F3mico."@es . . . . . . . . . . "NP-fullst\u00E4ndig"@sv . . . . . "Problem NP-zupe\u0142ny (NPC, ang. NP-Complete) \u2013 w klasie NP, ze wzgl\u0119du na redukcje wielomianowe, to problem, kt\u00F3ry nale\u017Cy do klasy NP oraz dowolny problem nale\u017C\u0105cy do NP mo\u017Ce by\u0107 do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym u\u017Cywa si\u0119 redukcji w pami\u0119ci logarytmicznej. Pytanie, czy s\u0105 to definicje r\u00F3wnowa\u017Cne pozostaje pytaniem otwartym. Taka definicja problem\u00F3w NP-zupe\u0142nych implikuje fakt, \u017Ce je\u015Bli tylko potrafimy rozwi\u0105za\u0107 jakikolwiek problem NP-zupe\u0142ny w czasie wielomianowym, to potrafimy rozwi\u0105za\u0107 w takim czasie wszystkie problemy NP. Problemy NP-zupe\u0142ne mo\u017Cna wi\u0119c traktowa\u0107 jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwi\u0105zywalno\u015Bci). Pierwszym problemem, kt\u00F3rego NP-zupe\u0142no\u015B\u0107 wykazano, by\u0142 problem SAT, czyli problem spe\u0142nialno\u015Bci formu\u0142 zdaniowych. Udowodni\u0142 to w 1971 roku Stephen Cook. Pytanie, czy problemy NP-zupe\u0142ne mo\u017Cna rozwi\u0105zywa\u0107 w czasie wielomianowym, jest najwi\u0119ksz\u0105 zagadk\u0105 informatyki teoretycznej. Ci\u0105gle nie udowodniono tego, i\u017C (nie udowodniono tak\u017Ce przeciwnie, \u017Ce ), kt\u00F3ra jednoznacznie stwierdza\u0142aby, \u017Ce jest to niemo\u017Cliwe. Rozwi\u0105zanie tego problemu znalaz\u0142o si\u0119 na li\u015Bcie problem\u00F3w milenijnych. Mimo ufundowania miliona dolar\u00F3w za rozwi\u0105zanie tak postawionego problemu, nikomu si\u0119 to nie uda\u0142o. Problem nie mo\u017Ce by\u0107 jednocze\u015Bnie NP-zupe\u0142ny i CoNP-zupe\u0142ny, chyba \u017Ce"@pl . . . . . . . . . "23385892"^^ . . . "Problem NP-zupe\u0142ny (NPC, ang. NP-Complete) \u2013 w klasie NP, ze wzgl\u0119du na redukcje wielomianowe, to problem, kt\u00F3ry nale\u017Cy do klasy NP oraz dowolny problem nale\u017C\u0105cy do NP mo\u017Ce by\u0107 do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym u\u017Cywa si\u0119 redukcji w pami\u0119ci logarytmicznej. Pytanie, czy s\u0105 to definicje r\u00F3wnowa\u017Cne pozostaje pytaniem otwartym. Taka definicja problem\u00F3w NP-zupe\u0142nych implikuje fakt, \u017Ce je\u015Bli tylko potrafimy rozwi\u0105za\u0107 jakikolwiek problem NP-zupe\u0142ny w czasie wielomianowym, to potrafimy rozwi\u0105za\u0107 w takim czasie wszystkie problemy NP. Problemy NP-zupe\u0142ne mo\u017Cna wi\u0119c traktowa\u0107 jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwi\u0105zywalno\u015Bci)."@pl . . . . . . . . . . . . "NP-volledigheid is een concept uit de complexiteitstheorie. Het is een beschrijving van het inzicht uit de jaren 70 dat er een bepaald verband is tussen de complexiteit van een groot aantal problemen die in de wiskunde en informatica als \"moeilijk\" worden beschouwd. In formele zin is een probleem NP-volledig (ook soms NP-compleet genoemd) als en slechts als \n* het probleem tot de NP behoort. \n* elk ander probleem in NP in polynomiale tijd naar dit probleem kan worden gereduceerd."@nl . . "NP\u5B8C\u5168\u554F\u984C"@ja . . "NP\u5B8C\u5168\uFF08\u306A\uFF09\u554F\u984C\uFF08\u30A8\u30CC\u30D4\u30FC\u304B\u3093\u305C\u3093\uFF08\u306A\uFF09\u3082\u3093\u3060\u3044\u3001NP-complete problem\uFF09\u3068\u306F\u3001(1) \u30AF\u30E9\u30B9NP\uFF08Non-deterministic Polynomial\uFF09\u306B\u5C5E\u3059\u308B\u6C7A\u5B9A\u554F\u984C\uFF08\u8A00\u8A9E\uFF09\u3067\u3001\u304B\u3064 (2) \u30AF\u30E9\u30B9NP\u306B\u5C5E\u3059\u308B\u4EFB\u610F\u306E\u554F\u984C\u304B\u3089\u591A\u9805\u5F0F\u6642\u9593\u9084\u5143\uFF08\u5E30\u7740\uFF09\u53EF\u80FD\u306A\u3082\u306E\u306E\u3053\u3068\u3067\u3042\u308B\u3002\u6761\u4EF6 (2) \u3092\u6E80\u305F\u3059\u5834\u5408\u306F\u3001\u554F\u984C\u306E\u5B9A\u7FA9\u304C\u6761\u4EF6 (1) \u3092\u6E80\u305F\u3055\u306A\u3044\u5834\u5408\u306B\u3082\u3001NP\u56F0\u96E3\u306A\u554F\u984C\u3068\u3088\u3073\u305D\u306E\u8A08\u7B97\u91CF\u7684\u306A\u56F0\u96E3\u6027\u3092\u7279\u5FB4\u3065\u3051\u3066\u3044\u308B\u3002\u591A\u9805\u5F0F\u6642\u9593\u9084\u5143\u306E\u63A8\u79FB\u6027\u304B\u3089\u3001\u30AF\u30E9\u30B9NP\u306B\u5C5E\u3059\u308B\u554F\u984C\u3067\u3001\u3042\u308B\u4E00\u3064\u306ENP\u5B8C\u5168\u554F\u984C\u304B\u3089\u591A\u9805\u5F0F\u6642\u9593\u9084\u5143\u53EF\u80FD\u306A\u3082\u306E\u3082\u3001\u307E\u305FNP\u5B8C\u5168\u3067\u3042\u308B\u3002\u73FE\u5728\u767A\u898B\u3055\u308C\u3066\u3044\u308BNP\u5B8C\u5168\u554F\u984C\u306E\u8A3C\u660E\u306E\u591A\u304F\u306F\u3053\u306E\u63A8\u79FB\u6027\u306B\u3088\u3063\u3066\u5145\u8DB3\u53EF\u80FD\u6027\u554F\u984C\u306A\u3069\u304B\u3089\u5C0E\u304B\u308C\u3066\u3044\u308B\u3002\u5145\u8DB3\u53EF\u80FD\u6027\u554F\u984C\u304CNP\u5B8C\u5168\u3067\u3042\u308B\u3053\u3068\u306F1971\u5E74\u3001\u30B9\u30C6\u30A3\u30FC\u30D6\u30F3\u30FB\u30AF\u30C3\u30AF\u306B\u3088\u3063\u3066\u8A3C\u660E\u3055\u308C\u3001R. M. \u30AB\u30FC\u30D7\u306E\u5B9A\u7FA9\u3057\u305F\u591A\u9805\u5F0F\u6642\u9593\u9084\u5143\u306B\u3088\u3063\u3066\u591A\u304F\u306E\u8A08\u7B97\u91CF\u7684\u306B\u56F0\u96E3\u306A\u554F\u984C\u304C NP \u5B8C\u5168\u3067\u3042\u308B\u3053\u3068\u304C\u793A\u3055\u308C\u305F\u3002"@ja . "\u0645\u0633\u0623\u0644\u0629 \u0643\u062B\u064A\u0631\u0629 \u062D\u062F\u0648\u062F \u063A\u064A\u0631 \u0642\u0637\u0639\u064A\u0629 \u0643\u0627\u0645\u0644\u0629"@ar . . "In der Informatik bezeichnet man ein Problem als NP-vollst\u00E4ndig (vollst\u00E4ndig f\u00FCr die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit l\u00F6sen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP geh\u00F6rt, also sowohl in NP liegt als auch NP-schwer ist. Dies bedeutet umgangssprachlich, dass es sich vermutlich nicht effizient l\u00F6sen l\u00E4sst. Formal wird NP-Vollst\u00E4ndigkeit nur f\u00FCr Entscheidungsprobleme definiert (m\u00F6gliche L\u00F6sungen nur \u201Eja\u201C oder \u201Enein\u201C), w\u00E4hrend man bei anderen Problemtypen von NP-\u00C4quivalenz spricht (etwa bei Suchproblemen oder Optimierungsproblemen). Umgangssprachlich wird diese Unterscheidung jedoch oft nicht vollzogen, so dass man ganz allgemein von \u201ENP-vollst\u00E4ndigen Problemen\u201C spricht, unabh\u00E4ngig davon, ob ein Entscheidungsproblem vorliegt oder nicht. Dies ist m\u00F6glich, da verschiedene Problemtypen ineinander \u00FCberf\u00FChrbar (aufeinander reduzierbar) sind. Ein Entscheidungsproblem ist NP-vollst\u00E4ndig, wenn es \n* in der Komplexit\u00E4tsklasse NP liegt: Ein deterministisch arbeitender Rechner ben\u00F6tigt nur polynomiell viel Zeit, um zu entscheiden, ob eine vorgeschlagene L\u00F6sung eines zugeh\u00F6rigen Suchproblems tats\u00E4chlich eine L\u00F6sung ist, und \n* zu den NP-schweren Problemen geh\u00F6rt: Alle anderen Probleme, deren L\u00F6sungen deterministisch in polynomieller Zeit \u00FCberpr\u00FCft werden k\u00F6nnen, k\u00F6nnen auf das Problem derart zur\u00FCckgef\u00FChrt werden, dass diese R\u00FCckf\u00FChrung auf einem deterministischen Rechner h\u00F6chstens polynomielle Zeit in Anspruch nimmt. Man spricht von einer Polynomialzeitreduktion. Die Klasse aller NP-vollst\u00E4ndigen Probleme wird mit NP-C (complete) bezeichnet. Die Eigenschaften dieser und anderer Klassen werden in der Komplexit\u00E4tstheorie erforscht, einem Teilgebiet der theoretischen Informatik. NP-vollst\u00E4ndige Probleme lassen sich vermutlich nicht effizient l\u00F6sen, da ihre L\u00F6sung auf realen Rechnern viel Zeit in Anspruch nimmt. In der Praxis wirkt sich dies nicht in jedem Fall negativ aus, das hei\u00DFt, es gibt f\u00FCr viele NP-vollst\u00E4ndige Probleme L\u00F6sungsverfahren, anhand deren sie f\u00FCr in der Praxis auftretende Gr\u00F6\u00DFenordnungen in akzeptabler Zeit l\u00F6sbar sind. Viele in der Praxis auftauchende und wichtige Probleme sind NP-vollst\u00E4ndig, was NP-Vollst\u00E4ndigkeit zu einem zentralen Begriff der Informatik macht. Weiter verst\u00E4rkt wird diese Bedeutung durch das sogenannte P-NP-Problem: 1. \n* F\u00FCr kein NP-vollst\u00E4ndiges Problem konnte bisher nachgewiesen werden, dass es in polynomieller Zeit l\u00F6sbar w\u00E4re. 2. \n* Falls nur ein einziges dieser Probleme in polynomieller Zeit l\u00F6sbar w\u00E4re, dann w\u00E4re jedes Problem in NP in polynomieller Zeit l\u00F6sbar, was gro\u00DFe Bedeutung f\u00FCr die Praxis haben k\u00F6nnte (jedoch nicht notwendigerweise haben muss). Seit der Einf\u00FChrung der NP-Vollst\u00E4ndigkeit durch Cook wurde die Vollst\u00E4ndigkeit zu einem allgemeinen Konzept f\u00FCr beliebige Komplexit\u00E4tsklassen ausgebaut."@de . . . . . . . . . . "NP-\u00FApln\u00E9 (NP-complete, NPC) probl\u00E9my jsou takov\u00E9 nedeterministicky polynomi\u00E1ln\u00ED probl\u00E9my, na kter\u00E9 jsou v\u0161echny ostatn\u00ED probl\u00E9my z NP. To znamen\u00E1, \u017Ee t\u0159\u00EDdu NP-\u00FApln\u00FDch \u00FAloh tvo\u0159\u00ED v jist\u00E9m smyslu ty nejt\u011B\u017E\u0161\u00ED \u00FAlohy z NP. Pokud by byl nalezen polynomi\u00E1ln\u00ED deterministick\u00FD algoritmus pro n\u011Bjakou NP-\u00FAplnou \u00FAlohu, znamenalo by to, \u017Ee v\u0161echny nedeterministicky polynomi\u00E1ln\u00ED probl\u00E9my jsou \u0159e\u0161iteln\u00E9 v polynomi\u00E1ln\u00EDm \u010Dase, tedy \u017Ee t\u0159\u00EDda NP se \u201Ezhrout\u00ED\u201C do t\u0159\u00EDdy P (NP = P). Ot\u00E1zka, zda n\u011Bjak\u00FD takov\u00FD algoritmus existuje, zat\u00EDm nebyla rozhodnuta, p\u0159edpokl\u00E1d\u00E1 se v\u0161ak, \u017Ee NP \u2260 P (je v\u0161ak z\u0159ejm\u00E9, \u017Ee P \u2286 NP). V\u00EDce o tomto probl\u00E9mu najdete v \u010Dl\u00E1nku Probl\u00E9m P versus NP."@cs . . "NP-\uC644\uC804"@ko . . . . . . "NP-\u043F\u043E\u0432\u043D\u0430 \u0437\u0430\u0434\u0430\u0447\u0430"@uk . . "En teor\u00EDa de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisi\u00F3n en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas m\u00E1s dif\u00EDciles de NP y muy probablemente no formen parte de la clase de complejidad P. La raz\u00F3n es que de tenerse una soluci\u00F3n polin\u00F3mica para un problema NP-completo, todos los problemas de NP tendr\u00EDan tambi\u00E9n una soluci\u00F3n en tiempo polin\u00F3mico. Si se demostrase que un problema NP-completo, llam\u00E9moslo A, no se pudiese resolver en tiempo polin\u00F3mico, el resto de los problemas NP-completos tampoco se podr\u00EDan resolver en tiempo polin\u00F3mico. Esto se debe a que si uno de los problemas NP-completos distintos de A, digamos X, se pudiese resolver en tiempo polin\u00F3mico, entonces A se podr\u00EDa resolver en tiempo polin\u00F3mico, por definici\u00F3n de NP-completo. Ahora, pueden existir problemas en NP y que no sean NP-completos para los cuales exista soluci\u00F3n polin\u00F3mica, aun no existiendo soluci\u00F3n para A. Como ejemplo de un problema NP-completo encontramos el problema de la suma de subconjuntos que se puede enunciar como sigue: dado un conjunto S de enteros, \u00BFexiste un subconjunto no vac\u00EDo de S cuyos elementos sumen cero? Es f\u00E1cil verificar si una respuesta es correcta, pero no se conoce mejor soluci\u00F3n que explorar todos los 2n-1 subconjuntos posibles hasta encontrar uno que cumpla con la condici\u00F3n."@es . . . . . . . . . "En complexitat computacional, el conjunt de problemes NP-complet, que son els problemes que pertanyen tant a NP com a NP-hard. En aquest context, NP vol dir \"temps polin\u00F2mic no determinista\". Els problemes NP-complets estan a NP, el conjunt de problemes de decisi\u00F3 la soluci\u00F3 dels quals es pot verificar en temps polin\u00F2mic en una m\u00E0quina de Turing no determinista. Un problema p de NP \u00E9s NP-complet si cada tot altre problema de NP es pot transformar a p en temps polin\u00F2mic."@ca . . . . . . . . . . . . . . . . . . "Na teoria da complexidade computacional, a classe de complexidade \u00E9 o subconjunto dos problemas NP de tal modo que todo problema em NP se pode reduzir, com uma redu\u00E7\u00E3o de tempo polinomial, a um dos problemas NP-completo. Pode-se dizer que os problemas de NP-completo s\u00E3o os problemas mais dif\u00EDceis de NP e muito provavelmente n\u00E3o formem parte da classe de complexidade P. A raz\u00E3o \u00E9 que se conseguisse encontrar uma maneira de resolver qualquer problema NP-completo rapidamente (em tempo polinomial) , ent\u00E3o poderiam ser utilizados algoritmos para resolver todos problemas NP rapidamente. Como exemplo de um problema NP-completo est\u00E1 o problema da soma dos subconjuntos que pode ser enunciado conforme segue: dado um conjunto S de inteiros, determine se h\u00E1 algum conjunto n\u00E3o vazio de S cujos elemento"@pt . . . . . "NP\u5B8C\u5168"@zh . . . . . "NP-completeness"@el . . . "NP-\u00FAplnost"@cs . . "NP-completo"@it . . . . . . . . . . . . . . "NP-\u043F\u043E\u043B\u043D\u0430\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u2014 \u0432 \u0442\u0435\u043E\u0440\u0438\u0438 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u0437\u0430\u0434\u0430\u0447\u0430 \u0441 \u043E\u0442\u0432\u0435\u0442\u043E\u043C \u00AB\u0434\u0430\u00BB \u0438\u043B\u0438 \u00AB\u043D\u0435\u0442\u00BB \u0438\u0437 \u043A\u043B\u0430\u0441\u0441\u0430 NP, \u043A \u043A\u043E\u0442\u043E\u0440\u043E\u0439 \u043C\u043E\u0436\u043D\u043E \u0441\u0432\u0435\u0441\u0442\u0438 \u043B\u044E\u0431\u0443\u044E \u0434\u0440\u0443\u0433\u0443\u044E \u0437\u0430\u0434\u0430\u0447\u0443 \u0438\u0437 \u044D\u0442\u043E\u0433\u043E \u043A\u043B\u0430\u0441\u0441\u0430 \u0437\u0430 \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u043E\u0435 \u0432\u0440\u0435\u043C\u044F (\u0442\u043E \u0435\u0441\u0442\u044C \u043F\u0440\u0438 \u043F\u043E\u043C\u043E\u0449\u0438 \u043E\u043F\u0435\u0440\u0430\u0446\u0438\u0439, \u0447\u0438\u0441\u043B\u043E \u043A\u043E\u0442\u043E\u0440\u044B\u0445 \u043D\u0435 \u043F\u0440\u0435\u0432\u044B\u0448\u0430\u0435\u0442 \u043D\u0435\u043A\u043E\u0442\u043E\u0440\u043E\u0433\u043E \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0430 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043C\u043E\u0441\u0442\u0438 \u043E\u0442 \u0440\u0430\u0437\u043C\u0435\u0440\u0430 \u0438\u0441\u0445\u043E\u0434\u043D\u044B\u0445 \u0434\u0430\u043D\u043D\u044B\u0445). \u0422\u0430\u043A\u0438\u043C \u043E\u0431\u0440\u0430\u0437\u043E\u043C, NP-\u043F\u043E\u043B\u043D\u044B\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043E\u0431\u0440\u0430\u0437\u0443\u044E\u0442 \u0432 \u043D\u0435\u043A\u043E\u0442\u043E\u0440\u043E\u043C \u0441\u043C\u044B\u0441\u043B\u0435 \u043F\u043E\u0434\u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432\u043E \u00AB\u0442\u0438\u043F\u043E\u0432\u044B\u0445\u00BB \u0437\u0430\u0434\u0430\u0447 \u0432 \u043A\u043B\u0430\u0441\u0441\u0435 NP: \u0435\u0441\u043B\u0438 \u0434\u043B\u044F \u043A\u0430\u043A\u043E\u0439-\u0442\u043E \u0438\u0437 \u043D\u0438\u0445 \u043D\u0430\u0439\u0434\u0435\u043D \u00AB\u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u043E \u0431\u044B\u0441\u0442\u0440\u044B\u0439\u00BB \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0440\u0435\u0448\u0435\u043D\u0438\u044F, \u0442\u043E \u0438 \u043B\u044E\u0431\u0430\u044F \u0434\u0440\u0443\u0433\u0430\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u0438\u0437 \u043A\u043B\u0430\u0441\u0441\u0430 NP \u043C\u043E\u0436\u0435\u0442 \u0431\u044B\u0442\u044C \u0440\u0435\u0448\u0435\u043D\u0430 \u0442\u0430\u043A \u0436\u0435 \u00AB\u0431\u044B\u0441\u0442\u0440\u043E\u00BB."@ru . . "NP-complet"@ca . "1123204053"^^ . "\u0641\u064A \u0627\u0644\u0631\u064A\u0627\u0636\u064A\u0627\u062A \u0635\u0646\u0641 \u0627\u0644\u062A\u0639\u0642\u064A\u062F\u060C \u062A\u0639\u0631\u0641 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0643\u062B\u064A\u0631\u0629 \u0627\u0644\u062D\u062F\u0648\u062F \u063A\u064A\u0631 \u0627\u0644\u0642\u0637\u0639\u064A\u0629 \u0627\u0644\u0643\u0627\u0645\u0644\u0629 (NP-complete problems)\u060C \u0628\u0623\u0646\u0647\u0627 \u0643\u0644 \u0645\u0627 \u064A\u062D\u0642\u0642 \u0627\u0644\u0634\u0631\u0637\u064A\u0646 \u0627\u0644\u0622\u062A\u064A\u064A\u0646: \n* \u0644\u0643\u0644 \u0644\u063A\u0629\u060CL, \u0645\u0648\u062C\u0648\u062F\u0629 \u0641\u064A NP \u064A\u0648\u062C\u062F \u062F\u0627\u0644\u0629 \u0628\u062D\u064A\u062B \u0627\u0646 \u0639\u062F\u062F \u0627\u0644\u062D\u0633\u0627\u0628\u0627\u062A \u0627\u0644\u062A\u064A \u062A\u0642\u0648\u0645 \u0628\u0647\u0627 \u0647\u0648 \u062F\u0627\u0644\u0629 \u0645\u062A\u0639\u062F\u062F\u0629 \u0627\u0644\u062D\u062F\u0648\u062F \u0628\u0627\u0644\u0646\u0633\u0628\u0629 \u0644\u0645\u062F\u062E\u0644\u0647\u0627\u060C \u0628\u062D\u064A\u062B \u0627\u0646 f : \u0625\u0630\u0627 \u0648\u0625\u0630\u0627 \n* \u0627\u0644\u0645\u0633\u0623\u0644\u0629 A \u0645\u0646 \u0635\u0646\u0641 NP \u0623\u064A \u064A\u0645\u0643\u0646 \u0628\u0646\u0627\u0621 \u0622\u0644\u0629 \u062A\u0648\u0631\u0646\u063A \u063A\u064A\u0631 \u062D\u062A\u0645\u064A\u0629 \u062A\u0642\u0631\u0631 \u0627\u0644\u0644\u063A\u0629 A. \u0623\u0648\u0644 \u0644\u063A\u0629 \u0639\u0631\u0641\u062A \u0628\u0627\u0646\u0647\u0627 NP \u0643\u0627\u0645\u0644\u0629 \u0647\u064A SAT \u062D\u064A\u062B \u0642\u0627\u0645 \u0643\u0644 \u0645\u0646 \u0643\u0648\u0643 \u0648\u0644\u064A\u0641\u064A\u0646 \u0628\u0627\u062B\u0628\u0627\u062A \u0647\u0630\u0627 \u0643\u0644 \u0639\u0644\u0649 \u062D\u062F\u0627\u060C \u0648\u0645\u0646\u0630 \u0630\u0644\u0643 \u0627\u0644\u062D\u064A\u0646 \u0643\u062B\u064A\u0631 \u0645\u0646 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0639\u064F\u0631\u0641 \u0627\u0646\u0647\u0627 NP \u0643\u0627\u0645\u0644\u0629."@ar . . . . . . . . . . . . "NP-completo"@es . . "NP\u5B8C\u5168\uFF08\u306A\uFF09\u554F\u984C\uFF08\u30A8\u30CC\u30D4\u30FC\u304B\u3093\u305C\u3093\uFF08\u306A\uFF09\u3082\u3093\u3060\u3044\u3001NP-complete problem\uFF09\u3068\u306F\u3001(1) \u30AF\u30E9\u30B9NP\uFF08Non-deterministic Polynomial\uFF09\u306B\u5C5E\u3059\u308B\u6C7A\u5B9A\u554F\u984C\uFF08\u8A00\u8A9E\uFF09\u3067\u3001\u304B\u3064 (2) \u30AF\u30E9\u30B9NP\u306B\u5C5E\u3059\u308B\u4EFB\u610F\u306E\u554F\u984C\u304B\u3089\u591A\u9805\u5F0F\u6642\u9593\u9084\u5143\uFF08\u5E30\u7740\uFF09\u53EF\u80FD\u306A\u3082\u306E\u306E\u3053\u3068\u3067\u3042\u308B\u3002\u6761\u4EF6 (2) \u3092\u6E80\u305F\u3059\u5834\u5408\u306F\u3001\u554F\u984C\u306E\u5B9A\u7FA9\u304C\u6761\u4EF6 (1) \u3092\u6E80\u305F\u3055\u306A\u3044\u5834\u5408\u306B\u3082\u3001NP\u56F0\u96E3\u306A\u554F\u984C\u3068\u3088\u3073\u305D\u306E\u8A08\u7B97\u91CF\u7684\u306A\u56F0\u96E3\u6027\u3092\u7279\u5FB4\u3065\u3051\u3066\u3044\u308B\u3002\u591A\u9805\u5F0F\u6642\u9593\u9084\u5143\u306E\u63A8\u79FB\u6027\u304B\u3089\u3001\u30AF\u30E9\u30B9NP\u306B\u5C5E\u3059\u308B\u554F\u984C\u3067\u3001\u3042\u308B\u4E00\u3064\u306ENP\u5B8C\u5168\u554F\u984C\u304B\u3089\u591A\u9805\u5F0F\u6642\u9593\u9084\u5143\u53EF\u80FD\u306A\u3082\u306E\u3082\u3001\u307E\u305FNP\u5B8C\u5168\u3067\u3042\u308B\u3002\u73FE\u5728\u767A\u898B\u3055\u308C\u3066\u3044\u308BNP\u5B8C\u5168\u554F\u984C\u306E\u8A3C\u660E\u306E\u591A\u304F\u306F\u3053\u306E\u63A8\u79FB\u6027\u306B\u3088\u3063\u3066\u5145\u8DB3\u53EF\u80FD\u6027\u554F\u984C\u306A\u3069\u304B\u3089\u5C0E\u304B\u308C\u3066\u3044\u308B\u3002\u5145\u8DB3\u53EF\u80FD\u6027\u554F\u984C\u304CNP\u5B8C\u5168\u3067\u3042\u308B\u3053\u3068\u306F1971\u5E74\u3001\u30B9\u30C6\u30A3\u30FC\u30D6\u30F3\u30FB\u30AF\u30C3\u30AF\u306B\u3088\u3063\u3066\u8A3C\u660E\u3055\u308C\u3001R. M. \u30AB\u30FC\u30D7\u306E\u5B9A\u7FA9\u3057\u305F\u591A\u9805\u5F0F\u6642\u9593\u9084\u5143\u306B\u3088\u3063\u3066\u591A\u304F\u306E\u8A08\u7B97\u91CF\u7684\u306B\u56F0\u96E3\u306A\u554F\u984C\u304C NP \u5B8C\u5168\u3067\u3042\u308B\u3053\u3068\u304C\u793A\u3055\u308C\u305F\u3002"@ja . "NP-fullst\u00E4ndiga problem (p\u00E5 engelska NP complete ibland NPC, fr\u00E5n nondeterministic polynomial) \u00E4r en klass av matematiska problem f\u00F6r vilka effektiva l\u00F6sningar saknas. Den enda l\u00F6sningen man funnit p\u00E5 ett godtyckligt NP-fullst\u00E4ndigt problem \u00E4r i princip att g\u00E5 igenom alla t\u00E4nkbara l\u00F6sningar och j\u00E4mf\u00F6ra dem, vilket \u00E4r og\u00F6rligt f\u00F6r andra \u00E4n sm\u00E5 probleminstanser."@sv . . "Nella teoria della complessit\u00E0 computazionale i problemi NP-completi sono i pi\u00F9 difficili problemi nella classe NP (\" in tempo polinomiale\") nel senso che, se si trovasse un algoritmo in grado di risolvere \"velocemente\" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere \"velocemente\" ogni problema in NP. La classe di complessit\u00E0 che contiene tutti i problemi NP-completi \u00E8 spesso indicata con NP-C. Un esempio di problema NP-completo \u00E8 il problema delle somme parziali, cio\u00E8: dato un insieme finito di numeri interi, determinare se esiste un sottoinsieme tale che la somma dei suoi elementi sia zero. \u00C8 evidente che \u00E8 facile verificare velocemente se un sottoinsieme \u00E8 o meno una soluzione del problema, ma non \u00E8 noto alcun metodo per trovare una soluzione che sia sensibilmente pi\u00F9 veloce di provare tutti i possibili sottoinsiemi tranne i due che contengono tutti numeri concordi (tutti negativi o tutti positivi), quelli formati da un solo numero negativo e da tutti numeri positivi maggiori in valore assoluto al numero negativo e quelli formati da un solo numero positivo e da tutti numeri negativi maggiori in valore assoluto al numero positivo."@it . . "NP-\u043F\u043E\u0432\u043D\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 (\u0430\u043D\u0433\u043B. NP-complete) \u2014 \u0432 \u0442\u0435\u043E\u0440\u0456\u0457 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0456\u0432 \u0442\u0430 \u0442\u0435\u043E\u0440\u0456\u0457 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456 \u0446\u0435 \u0437\u0430\u0434\u0430\u0447\u0430, \u0449\u043E \u043D\u0430\u043B\u0435\u0436\u0438\u0442\u044C \u0434\u043E \u043A\u043B\u0430\u0441\u0443 NP \u0442\u0430 \u0432\u0441\u0456 \u0437\u0430\u0434\u0430\u0447\u0456 \u0437 \u043A\u043B\u0430\u0441\u0443 NP \u043C\u043E\u0436\u043D\u0430 \u0437\u0432\u0435\u0441\u0442\u0438 \u0434\u043E \u043D\u0435\u0457 \u0437\u0430 \u043F\u043E\u043B\u0456\u043D\u043E\u043C\u0456\u0430\u043B\u044C\u043D\u0438\u0439 \u0447\u0430\u0441."@uk . "NP-Vollst\u00E4ndigkeit"@de . . . . . "En th\u00E9orie de la complexit\u00E9, un probl\u00E8me NP-complet ou probl\u00E8me NPC (c'est-\u00E0-dire un probl\u00E8me complet pour la classe NP) est un probl\u00E8me de d\u00E9cision v\u00E9rifiant les propri\u00E9t\u00E9s suivantes : \n* il est possible de v\u00E9rifier une solution efficacement (en temps polynomial) ; la classe des probl\u00E8mes v\u00E9rifiant cette propri\u00E9t\u00E9 est not\u00E9e NP ; \n* tous les probl\u00E8mes de la classe NP se ram\u00E8nent \u00E0 celui-ci via une r\u00E9duction polynomiale ; cela signifie que le probl\u00E8me est au moins aussi difficile que tous les autres probl\u00E8mes de la classe NP. Un probl\u00E8me NP-difficile est un probl\u00E8me qui remplit la seconde condition, et donc peut \u00EAtre dans une classe de probl\u00E8me plus large et donc plus difficile que la classe NP. Bien qu'on puisse v\u00E9rifier rapidement toute solution propos\u00E9e d'un probl\u00E8me NP-complet, on ne sait pas en trouver efficacement. C'est le cas, par exemple, du probl\u00E8me du voyageur de commerce ou de celui du probl\u00E8me du sac \u00E0 dos. Tous les algorithmes connus pour r\u00E9soudre des probl\u00E8mes NP-complets ont un temps d'ex\u00E9cution exponentiel en fonction de la taille des donn\u00E9es d'entr\u00E9e dans le pire des cas, et sont donc inexploitables en pratique m\u00EAme pour des instances de taille mod\u00E9r\u00E9e. La seconde propri\u00E9t\u00E9 de la d\u00E9finition implique que s'il existe un algorithme polynomial pour r\u00E9soudre un quelconque des probl\u00E8mes NP-complets, alors tous les probl\u00E8mes de la classe NP peuvent \u00EAtre r\u00E9solus en temps polynomial. Trouver un algorithme polynomial pour un probl\u00E8me NP-complet ou prouver qu'il n'en existe pas permettrait de savoir si P = NP ou P \u2260 NP, une question ouverte qui fait partie des probl\u00E8mes non r\u00E9solus en math\u00E9matiques les plus importants \u00E0 ce jour. En pratique, les informaticiens et les d\u00E9veloppeurs sont souvent confront\u00E9s \u00E0 des probl\u00E8mes NP-complets. Dans ce cas, savoir que le probl\u00E8me sur lequel on travaille est NP-complet est une indication du fait que le probl\u00E8me est difficile \u00E0 r\u00E9soudre, donc qu'il vaut mieux chercher des solutions approch\u00E9es en utilisant des algorithmes d'approximation ou utiliser des heuristiques pour trouver des solutions exactes."@fr . "NP\u5B8C\u5168\u6216NP\u5B8C\u5907 \uFF08NP-Complete\uFF0C\u7E2E\u5BEB\u70BANP-C\u6216NPC\uFF09\uFF0C\u662F\u8A08\u7B97\u8907\u96DC\u5EA6\u7406\u8AD6\u4E2D\uFF0C\u6C7A\u5B9A\u6027\u554F\u984C\u7684\u7B49\u7D1A\u4E4B\u4E00\u3002NP\u5B8C\u5907\u662FNP\u4E0ENP\u56F0\u96BE\u554F\u984C\u7684\u4EA4\u96C6\uFF0C\u662FNP\u4E2D\u6700\u96E3\u7684\u6C7A\u5B9A\u6027\u554F\u984C\uFF0C\u6240\u6709NP\u554F\u984C\u90FD\u53EF\u4EE5\u5728\u591A\u9805\u5F0F\u6642\u9593\u5167\u88AB\u6B78\u7D04\uFF08reduce to\uFF09\u70BANP\u5B8C\u5099\u554F\u984C\u3002\u5018\u82E5\u4EFB\u4F55NP\u5B8C\u5099\u554F\u984C\u5F97\u5230\u591A\u9805\u5F0F\u6642\u9593\u5167\u7684\u89E3\u6CD5\uFF0C\u5247\u8A72\u89E3\u6CD5\u5C31\u53EF\u61C9\u7528\u5728\u6240\u6709NP\u554F\u984C\u4E0A\uFF0C\u4EA6\u53EF\u8B49\u660ENP\u554F\u984C\u7B49\u65BCP\u554F\u984C\uFF0C\u7136\u800C\u76EE\u524D\u70BA\u6B62\u4E26\u672A\u767C\u73FE\u4EFB\u4F55\u80FD\u5728\u591A\u9805\u5F0F\u6642\u9593\u5167\u89E3\u6C7ANP\u5B8C\u5099\u554F\u984C\u7684\u65B9\u6CD5\u3002"@zh . "NP-\uC644\uC804(NP-complete, NP-C, NPC)\uC740 NP \uC9D1\uD569\uC5D0 \uC18D\uD558\uB294 \uACB0\uC815 \uBB38\uC81C \uC911\uC5D0\uC11C \uAC00\uC7A5 \uC5B4\uB824\uC6B4 \uBB38\uC81C\uC758 \uBD80\uBD84\uC9D1\uD569\uC73C\uB85C, \uBAA8\uB4E0 NP \uBB38\uC81C\uB97C \uB2E4\uD56D \uC2DC\uAC04 \uB0B4\uC5D0 NP-\uC644\uC804 \uBB38\uC81C\uB85C \uD658\uC0B0\uD560 \uC218 \uC788\uB2E4. NP-\uC644\uC804 \uBB38\uC81C \uC911 \uD558\uB098\uB77C\uB3C4 P\uC5D0 \uC18D\uD55C\uB2E4\uB294 \uAC83\uC744 \uC99D\uBA85\uD55C\uB2E4\uBA74 \uBAA8\uB4E0 NP \uBB38\uC81C\uAC00 P\uC5D0 \uC18D\uD558\uAE30 \uB54C\uBB38\uC5D0, P-NP \uBB38\uC81C\uAC00 P=NP\uC758 \uD615\uD0DC\uB85C \uD480\uB9AC\uAC8C \uB41C\uB2E4. \uBC18\uB300\uB85C NP-\uC644\uC804 \uBB38\uC81C \uC911\uC758 \uD558\uB098\uAC00 P\uC5D0 \uC18D\uD558\uC9C0 \uC54A\uB294\uB2E4\uB294 \uAC83\uC774 \uC99D\uBA85\uB41C\uB2E4\uBA74 P=NP\uC5D0 \uB300\uD55C \uBC18\uB840\uAC00 \uB418\uC5B4 P-NP \uBB38\uC81C\uB294 P\u2260NP\uC758 \uD615\uD0DC\uB85C \uD480\uB9AC\uAC8C \uB41C\uB2E4."@ko . "NP-\u00FApln\u00E9 (NP-complete, NPC) probl\u00E9my jsou takov\u00E9 nedeterministicky polynomi\u00E1ln\u00ED probl\u00E9my, na kter\u00E9 jsou v\u0161echny ostatn\u00ED probl\u00E9my z NP. To znamen\u00E1, \u017Ee t\u0159\u00EDdu NP-\u00FApln\u00FDch \u00FAloh tvo\u0159\u00ED v jist\u00E9m smyslu ty nejt\u011B\u017E\u0161\u00ED \u00FAlohy z NP. Pokud by byl nalezen polynomi\u00E1ln\u00ED deterministick\u00FD algoritmus pro n\u011Bjakou NP-\u00FAplnou \u00FAlohu, znamenalo by to, \u017Ee v\u0161echny nedeterministicky polynomi\u00E1ln\u00ED probl\u00E9my jsou \u0159e\u0161iteln\u00E9 v polynomi\u00E1ln\u00EDm \u010Dase, tedy \u017Ee t\u0159\u00EDda NP se \u201Ezhrout\u00ED\u201C do t\u0159\u00EDdy P (NP = P). Ot\u00E1zka, zda n\u011Bjak\u00FD takov\u00FD algoritmus existuje, zat\u00EDm nebyla rozhodnuta, p\u0159edpokl\u00E1d\u00E1 se v\u0161ak, \u017Ee NP \u2260 P (je v\u0161ak z\u0159ejm\u00E9, \u017Ee P \u2286 NP). V\u00EDce o tomto probl\u00E9mu najdete v \u010Dl\u00E1nku Probl\u00E9m P versus NP. Vztah mezi P a NP je jedn\u00EDm ze sedmi probl\u00E9m\u016F tis\u00EDcilet\u00ED, kter\u00E9 vypsal Clay\u016Fv matematick\u00FD \u00FAstav 24. kv\u011Btna 2000. Za rozhodnut\u00ED vztahu nab\u00EDz\u00ED 1 000 000 dolar\u016F."@cs . . . . . . . . . "NP-completeness"@en . . . . . . . . . . . . . . . . . . . . . "NP-completo"@pt . . . . . . . . . . . . . . . "NP-\u043F\u043E\u043B\u043D\u0430\u044F \u0437\u0430\u0434\u0430\u0447\u0430"@ru . . "NP-\uC644\uC804(NP-complete, NP-C, NPC)\uC740 NP \uC9D1\uD569\uC5D0 \uC18D\uD558\uB294 \uACB0\uC815 \uBB38\uC81C \uC911\uC5D0\uC11C \uAC00\uC7A5 \uC5B4\uB824\uC6B4 \uBB38\uC81C\uC758 \uBD80\uBD84\uC9D1\uD569\uC73C\uB85C, \uBAA8\uB4E0 NP \uBB38\uC81C\uB97C \uB2E4\uD56D \uC2DC\uAC04 \uB0B4\uC5D0 NP-\uC644\uC804 \uBB38\uC81C\uB85C \uD658\uC0B0\uD560 \uC218 \uC788\uB2E4. NP-\uC644\uC804 \uBB38\uC81C \uC911 \uD558\uB098\uB77C\uB3C4 P\uC5D0 \uC18D\uD55C\uB2E4\uB294 \uAC83\uC744 \uC99D\uBA85\uD55C\uB2E4\uBA74 \uBAA8\uB4E0 NP \uBB38\uC81C\uAC00 P\uC5D0 \uC18D\uD558\uAE30 \uB54C\uBB38\uC5D0, P-NP \uBB38\uC81C\uAC00 P=NP\uC758 \uD615\uD0DC\uB85C \uD480\uB9AC\uAC8C \uB41C\uB2E4. \uBC18\uB300\uB85C NP-\uC644\uC804 \uBB38\uC81C \uC911\uC758 \uD558\uB098\uAC00 P\uC5D0 \uC18D\uD558\uC9C0 \uC54A\uB294\uB2E4\uB294 \uAC83\uC774 \uC99D\uBA85\uB41C\uB2E4\uBA74 P=NP\uC5D0 \uB300\uD55C \uBC18\uB840\uAC00 \uB418\uC5B4 P-NP \uBB38\uC81C\uB294 P\u2260NP\uC758 \uD615\uD0DC\uB85C \uD480\uB9AC\uAC8C \uB41C\uB2E4."@ko . "Probl\u00E8me NP-complet"@fr . "30665"^^ . . . . . . . . . . . . . "NP-\u043F\u043E\u043B\u043D\u0430\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u2014 \u0432 \u0442\u0435\u043E\u0440\u0438\u0438 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u0437\u0430\u0434\u0430\u0447\u0430 \u0441 \u043E\u0442\u0432\u0435\u0442\u043E\u043C \u00AB\u0434\u0430\u00BB \u0438\u043B\u0438 \u00AB\u043D\u0435\u0442\u00BB \u0438\u0437 \u043A\u043B\u0430\u0441\u0441\u0430 NP, \u043A \u043A\u043E\u0442\u043E\u0440\u043E\u0439 \u043C\u043E\u0436\u043D\u043E \u0441\u0432\u0435\u0441\u0442\u0438 \u043B\u044E\u0431\u0443\u044E \u0434\u0440\u0443\u0433\u0443\u044E \u0437\u0430\u0434\u0430\u0447\u0443 \u0438\u0437 \u044D\u0442\u043E\u0433\u043E \u043A\u043B\u0430\u0441\u0441\u0430 \u0437\u0430 \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u043E\u0435 \u0432\u0440\u0435\u043C\u044F (\u0442\u043E \u0435\u0441\u0442\u044C \u043F\u0440\u0438 \u043F\u043E\u043C\u043E\u0449\u0438 \u043E\u043F\u0435\u0440\u0430\u0446\u0438\u0439, \u0447\u0438\u0441\u043B\u043E \u043A\u043E\u0442\u043E\u0440\u044B\u0445 \u043D\u0435 \u043F\u0440\u0435\u0432\u044B\u0448\u0430\u0435\u0442 \u043D\u0435\u043A\u043E\u0442\u043E\u0440\u043E\u0433\u043E \u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0430 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043C\u043E\u0441\u0442\u0438 \u043E\u0442 \u0440\u0430\u0437\u043C\u0435\u0440\u0430 \u0438\u0441\u0445\u043E\u0434\u043D\u044B\u0445 \u0434\u0430\u043D\u043D\u044B\u0445). \u0422\u0430\u043A\u0438\u043C \u043E\u0431\u0440\u0430\u0437\u043E\u043C, NP-\u043F\u043E\u043B\u043D\u044B\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043E\u0431\u0440\u0430\u0437\u0443\u044E\u0442 \u0432 \u043D\u0435\u043A\u043E\u0442\u043E\u0440\u043E\u043C \u0441\u043C\u044B\u0441\u043B\u0435 \u043F\u043E\u0434\u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432\u043E \u00AB\u0442\u0438\u043F\u043E\u0432\u044B\u0445\u00BB \u0437\u0430\u0434\u0430\u0447 \u0432 \u043A\u043B\u0430\u0441\u0441\u0435 NP: \u0435\u0441\u043B\u0438 \u0434\u043B\u044F \u043A\u0430\u043A\u043E\u0439-\u0442\u043E \u0438\u0437 \u043D\u0438\u0445 \u043D\u0430\u0439\u0434\u0435\u043D \u00AB\u043F\u043E\u043B\u0438\u043D\u043E\u043C\u0438\u0430\u043B\u044C\u043D\u043E \u0431\u044B\u0441\u0442\u0440\u044B\u0439\u00BB \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0440\u0435\u0448\u0435\u043D\u0438\u044F, \u0442\u043E \u0438 \u043B\u044E\u0431\u0430\u044F \u0434\u0440\u0443\u0433\u0430\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u0438\u0437 \u043A\u043B\u0430\u0441\u0441\u0430 NP \u043C\u043E\u0436\u0435\u0442 \u0431\u044B\u0442\u044C \u0440\u0435\u0448\u0435\u043D\u0430 \u0442\u0430\u043A \u0436\u0435 \u00AB\u0431\u044B\u0441\u0442\u0440\u043E\u00BB."@ru . "NP-\u043F\u043E\u0432\u043D\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 (\u0430\u043D\u0433\u043B. NP-complete) \u2014 \u0432 \u0442\u0435\u043E\u0440\u0456\u0457 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0456\u0432 \u0442\u0430 \u0442\u0435\u043E\u0440\u0456\u0457 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456 \u0446\u0435 \u0437\u0430\u0434\u0430\u0447\u0430, \u0449\u043E \u043D\u0430\u043B\u0435\u0436\u0438\u0442\u044C \u0434\u043E \u043A\u043B\u0430\u0441\u0443 NP \u0442\u0430 \u0432\u0441\u0456 \u0437\u0430\u0434\u0430\u0447\u0456 \u0437 \u043A\u043B\u0430\u0441\u0443 NP \u043C\u043E\u0436\u043D\u0430 \u0437\u0432\u0435\u0441\u0442\u0438 \u0434\u043E \u043D\u0435\u0457 \u0437\u0430 \u043F\u043E\u043B\u0456\u043D\u043E\u043C\u0456\u0430\u043B\u044C\u043D\u0438\u0439 \u0447\u0430\u0441."@uk . . . . . "\u0641\u064A \u0627\u0644\u0631\u064A\u0627\u0636\u064A\u0627\u062A \u0635\u0646\u0641 \u0627\u0644\u062A\u0639\u0642\u064A\u062F\u060C \u062A\u0639\u0631\u0641 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0643\u062B\u064A\u0631\u0629 \u0627\u0644\u062D\u062F\u0648\u062F \u063A\u064A\u0631 \u0627\u0644\u0642\u0637\u0639\u064A\u0629 \u0627\u0644\u0643\u0627\u0645\u0644\u0629 (NP-complete problems)\u060C \u0628\u0623\u0646\u0647\u0627 \u0643\u0644 \u0645\u0627 \u064A\u062D\u0642\u0642 \u0627\u0644\u0634\u0631\u0637\u064A\u0646 \u0627\u0644\u0622\u062A\u064A\u064A\u0646: \n* \u0644\u0643\u0644 \u0644\u063A\u0629\u060CL, \u0645\u0648\u062C\u0648\u062F\u0629 \u0641\u064A NP \u064A\u0648\u062C\u062F \u062F\u0627\u0644\u0629 \u0628\u062D\u064A\u062B \u0627\u0646 \u0639\u062F\u062F \u0627\u0644\u062D\u0633\u0627\u0628\u0627\u062A \u0627\u0644\u062A\u064A \u062A\u0642\u0648\u0645 \u0628\u0647\u0627 \u0647\u0648 \u062F\u0627\u0644\u0629 \u0645\u062A\u0639\u062F\u062F\u0629 \u0627\u0644\u062D\u062F\u0648\u062F \u0628\u0627\u0644\u0646\u0633\u0628\u0629 \u0644\u0645\u062F\u062E\u0644\u0647\u0627\u060C \u0628\u062D\u064A\u062B \u0627\u0646 f : \u0625\u0630\u0627 \u0648\u0625\u0630\u0627 \n* \u0627\u0644\u0645\u0633\u0623\u0644\u0629 A \u0645\u0646 \u0635\u0646\u0641 NP \u0623\u064A \u064A\u0645\u0643\u0646 \u0628\u0646\u0627\u0621 \u0622\u0644\u0629 \u062A\u0648\u0631\u0646\u063A \u063A\u064A\u0631 \u062D\u062A\u0645\u064A\u0629 \u062A\u0642\u0631\u0631 \u0627\u0644\u0644\u063A\u0629 A. \u0623\u0648\u0644 \u0644\u063A\u0629 \u0639\u0631\u0641\u062A \u0628\u0627\u0646\u0647\u0627 NP \u0643\u0627\u0645\u0644\u0629 \u0647\u064A SAT \u062D\u064A\u062B \u0642\u0627\u0645 \u0643\u0644 \u0645\u0646 \u0643\u0648\u0643 \u0648\u0644\u064A\u0641\u064A\u0646 \u0628\u0627\u062B\u0628\u0627\u062A \u0647\u0630\u0627 \u0643\u0644 \u0639\u0644\u0649 \u062D\u062F\u0627\u060C \u0648\u0645\u0646\u0630 \u0630\u0644\u0643 \u0627\u0644\u062D\u064A\u0646 \u0643\u062B\u064A\u0631 \u0645\u0646 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0639\u064F\u0631\u0641 \u0627\u0646\u0647\u0627 NP \u0643\u0627\u0645\u0644\u0629."@ar . . . . . . . . . . "Nella teoria della complessit\u00E0 computazionale i problemi NP-completi sono i pi\u00F9 difficili problemi nella classe NP (\" in tempo polinomiale\") nel senso che, se si trovasse un algoritmo in grado di risolvere \"velocemente\" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere \"velocemente\" ogni problema in NP. La classe di complessit\u00E0 che contiene tutti i problemi NP-completi \u00E8 spesso indicata con NP-C."@it . . . . . . "En complexitat computacional, el conjunt de problemes NP-complet, que son els problemes que pertanyen tant a NP com a NP-hard. En aquest context, NP vol dir \"temps polin\u00F2mic no determinista\". Els problemes NP-complets estan a NP, el conjunt de problemes de decisi\u00F3 la soluci\u00F3 dels quals es pot verificar en temps polin\u00F2mic en una m\u00E0quina de Turing no determinista. Un problema p de NP \u00E9s NP-complet si cada tot altre problema de NP es pot transformar a p en temps polin\u00F2mic."@ca . . "Na teoria da complexidade computacional, a classe de complexidade \u00E9 o subconjunto dos problemas NP de tal modo que todo problema em NP se pode reduzir, com uma redu\u00E7\u00E3o de tempo polinomial, a um dos problemas NP-completo. Pode-se dizer que os problemas de NP-completo s\u00E3o os problemas mais dif\u00EDceis de NP e muito provavelmente n\u00E3o formem parte da classe de complexidade P. A raz\u00E3o \u00E9 que se conseguisse encontrar uma maneira de resolver qualquer problema NP-completo rapidamente (em tempo polinomial) , ent\u00E3o poderiam ser utilizados algoritmos para resolver todos problemas NP rapidamente. Como exemplo de um problema NP-completo est\u00E1 o problema da soma dos subconjuntos que pode ser enunciado conforme segue: dado um conjunto S de inteiros, determine se h\u00E1 algum conjunto n\u00E3o vazio de S cujos elementos somem zero. \u00C9 f\u00E1cil de verificar se uma resposta \u00E9 correta, mas n\u00E3o se conhece uma solu\u00E7\u00E3o significativamente mais r\u00E1pida para resolver este problema do que testar todos os subconjuntos poss\u00EDveis, at\u00E9 encontrar um que cumpra com a condi\u00E7\u00E3o.Na pr\u00E1tica, o conhecimento de NP-completo pode evitar que se desperdice tempo tentando encontrar um algoritmo de tempo polinomial para resolver um problema quando esse algoritmo n\u00E3o existe."@pt . . . . . . . . . "NP-volledig"@nl . . . . "In computational complexity theory, a problem is NP-complete when: 1. \n* it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. 2. \n* the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified."@en . . . "In der Informatik bezeichnet man ein Problem als NP-vollst\u00E4ndig (vollst\u00E4ndig f\u00FCr die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit l\u00F6sen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP geh\u00F6rt, also sowohl in NP liegt als auch NP-schwer ist. Dies bedeutet umgangssprachlich, dass es sich vermutlich nicht effizient l\u00F6sen l\u00E4sst. Ein Entscheidungsproblem ist NP-vollst\u00E4ndig, wenn es Seit der Einf\u00FChrung der NP-Vollst\u00E4ndigkeit durch Cook wurde die Vollst\u00E4ndigkeit zu einem allgemeinen Konzept f\u00FCr beliebige Komplexit\u00E4tsklassen ausgebaut."@de . "NP\u5B8C\u5168\u6216NP\u5B8C\u5907 \uFF08NP-Complete\uFF0C\u7E2E\u5BEB\u70BANP-C\u6216NPC\uFF09\uFF0C\u662F\u8A08\u7B97\u8907\u96DC\u5EA6\u7406\u8AD6\u4E2D\uFF0C\u6C7A\u5B9A\u6027\u554F\u984C\u7684\u7B49\u7D1A\u4E4B\u4E00\u3002NP\u5B8C\u5907\u662FNP\u4E0ENP\u56F0\u96BE\u554F\u984C\u7684\u4EA4\u96C6\uFF0C\u662FNP\u4E2D\u6700\u96E3\u7684\u6C7A\u5B9A\u6027\u554F\u984C\uFF0C\u6240\u6709NP\u554F\u984C\u90FD\u53EF\u4EE5\u5728\u591A\u9805\u5F0F\u6642\u9593\u5167\u88AB\u6B78\u7D04\uFF08reduce to\uFF09\u70BANP\u5B8C\u5099\u554F\u984C\u3002\u5018\u82E5\u4EFB\u4F55NP\u5B8C\u5099\u554F\u984C\u5F97\u5230\u591A\u9805\u5F0F\u6642\u9593\u5167\u7684\u89E3\u6CD5\uFF0C\u5247\u8A72\u89E3\u6CD5\u5C31\u53EF\u61C9\u7528\u5728\u6240\u6709NP\u554F\u984C\u4E0A\uFF0C\u4EA6\u53EF\u8B49\u660ENP\u554F\u984C\u7B49\u65BCP\u554F\u984C\uFF0C\u7136\u800C\u76EE\u524D\u70BA\u6B62\u4E26\u672A\u767C\u73FE\u4EFB\u4F55\u80FD\u5728\u591A\u9805\u5F0F\u6642\u9593\u5167\u89E3\u6C7ANP\u5B8C\u5099\u554F\u984C\u7684\u65B9\u6CD5\u3002"@zh . . . . "Problem NP-zupe\u0142ny"@pl . . . "En th\u00E9orie de la complexit\u00E9, un probl\u00E8me NP-complet ou probl\u00E8me NPC (c'est-\u00E0-dire un probl\u00E8me complet pour la classe NP) est un probl\u00E8me de d\u00E9cision v\u00E9rifiant les propri\u00E9t\u00E9s suivantes : \n* il est possible de v\u00E9rifier une solution efficacement (en temps polynomial) ; la classe des probl\u00E8mes v\u00E9rifiant cette propri\u00E9t\u00E9 est not\u00E9e NP ; \n* tous les probl\u00E8mes de la classe NP se ram\u00E8nent \u00E0 celui-ci via une r\u00E9duction polynomiale ; cela signifie que le probl\u00E8me est au moins aussi difficile que tous les autres probl\u00E8mes de la classe NP."@fr . "In computational complexity theory, a problem is NP-complete when: 1. \n* it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. 2. \n* the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. The name \"NP-complete\" is short for \"nondeterministic polynomial-time complete\". In this name, \"nondeterministic\" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered \"quick\" for a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search. \"Complete\" refers to the property of being able to simulate everything in the same complexity class. More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly (in polynomial time), such that the output for any input is \"yes\" if the solution set is non-empty and \"no\" if it is empty. The complexity class of problems of this form is called NP, an abbreviation for \"nondeterministic polynomial time\". A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it even though it may not be in NP. Conversely, a problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If some NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC. Although a solution to an NP-complete problem can be verified \"quickly\", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the fundamental unsolved problems in computer science today. While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms."@en . . . . . . . "NP-fullst\u00E4ndiga problem (p\u00E5 engelska NP complete ibland NPC, fr\u00E5n nondeterministic polynomial) \u00E4r en klass av matematiska problem f\u00F6r vilka effektiva l\u00F6sningar saknas. Den enda l\u00F6sningen man funnit p\u00E5 ett godtyckligt NP-fullst\u00E4ndigt problem \u00E4r i princip att g\u00E5 igenom alla t\u00E4nkbara l\u00F6sningar och j\u00E4mf\u00F6ra dem, vilket \u00E4r og\u00F6rligt f\u00F6r andra \u00E4n sm\u00E5 probleminstanser."@sv .