CINXE.COM

<!DOCTYPE html> <html class="client-nojs" lang="ru" dir="ltr"> <head> <meta charset="UTF-8"> <title>NP-полная задача — Википедия</title> <script>(function(){var className="client-js";var cookie=document.cookie.match(/(?:^|; )ruwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t."," \t,"],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","январь","февраль","март","апрель","май","июнь","июль","август","сентябрь","октябрь","ноябрь","декабрь"],"wgRequestId":"3db49f88-d5ca-4cc2-a888-b805ceacc0d3","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"NP-полная_задача","wgTitle":"NP-полная задача","wgCurRevisionId":139421010,"wgRevisionId":139421010,"wgArticleId":162247,"wgIsArticle":true ,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Страницы, использующие расширение JsonConfig","Википедия:Страницы с модулем Hatnote с готовым форматированием","Википедия:Статьи без источников (не распределённые по типам)","Википедия:Нет источников с июля 2017","Википедия:Статьи с утверждениями без источников более 14 дней","Страницы, использующие волшебные ссылки ISBN","NP-полные задачи"],"wgPageViewLanguage":"ru","wgPageContentLanguage":"ru","wgPageContentModel":"wikitext","wgRelevantPageName":"NP-полная_задача","wgRelevantArticleId":162247,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject": "wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"accuracy":{"levels":1}}},"wgStableRevisionId":130991241,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"ru","pageLanguageDir":"ltr","pageVariantFallbacks":"ru"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":10000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":true,"wgVector2022LanguageInHeader":false,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q215206","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false} ;RLSTATE={"ext.gadget.common-site":"ready","ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","skins.vector.styles.legacy":"ready","ext.flaggedRevs.basic":"ready","mediawiki.codex.messagebox.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","codex-search-styles":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.legacy.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.flaggedRevs.advanced","ext.gadget.collapserefs","ext.gadget.directLinkToCommons","ext.gadget.referenceTooltips","ext.gadget.logo","ext.gadget.edittop","ext.gadget.navboxDefaultGadgets","ext.gadget.wikibugs","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap", "ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.compactlinks","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","oojs-ui.styles.icons-media","oojs-ui-core.icons"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=ru&modules=codex-search-styles%7Cext.cite.styles%7Cext.flaggedRevs.basic%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cmediawiki.codex.messagebox.styles%7Cskins.vector.styles.legacy%7Cwikibase.client.init&only=styles&skin=vector"> <script async="" src="/w/load.php?lang=ru&modules=startup&only=scripts&raw=1&skin=vector"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=ru&modules=ext.gadget.common-site&only=styles&skin=vector"> <link rel="stylesheet" href="/w/load.php?lang=ru&modules=site.styles&only=styles&skin=vector"> <noscript><link rel="stylesheet" href="/w/load.php?lang=ru&modules=noscript&only=styles&skin=vector"></noscript> <meta name="generator" content="MediaWiki 1.44.0-wmf.18"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/1200px-P_np_np-complete_np-hard.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="750"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/800px-P_np_np-complete_np-hard.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="500"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/640px-P_np_np-complete_np-hard.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="400"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="NP-полная задача — Википедия"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//ru.m.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0"> <link rel="alternate" type="application/x-wiki" title="Править" href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Википедия (ru)"> <link rel="EditURI" type="application/rsd+xml" href="//ru.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.ru"> <link rel="alternate" type="application/atom+xml" title="Википедия — Atom-лента" href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%B2%D0%B5%D0%B6%D0%B8%D0%B5_%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B8&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin-vector-legacy mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-NP-полная_задача rootpage-NP-полная_задача skin-vector action-view"><div id="mw-page-base" class="noprint"></div> <div id="mw-head-base" class="noprint"></div> <div id="content" class="mw-body" role="main"> <a id="top"></a> <div id="siteNotice"></div> <div class="mw-indicators"> </div> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">NP-полная задача</span></h1> <div id="bodyContent" class="vector-body"> <div id="siteSub" class="noprint">Материал из Википедии — свободной энциклопедии</div> <div id="contentSub"><div id="mw-content-subtitle"><div id="mw-fr-revision-messages"><div class="cdx-message mw-fr-message-box cdx-message--block cdx-message--notice mw-fr-basic mw-fr-draft-not-synced plainlinks noprint"><span class="cdx-message__icon"></span><div class="cdx-message__content">Текущая версия страницы пока <a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0_%D1%81%D1%82%D0%B0%D1%82%D0%B5%D0%B9/%D0%9F%D0%BE%D1%8F%D1%81%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B4%D0%BB%D1%8F_%D1%87%D0%B8%D1%82%D0%B0%D1%82%D0%B5%D0%BB%D0%B5%D0%B9" title="Википедия:Проверка статей/Пояснение для читателей">не проверялась</a> опытными участниками и может значительно отличаться от <a class="external text" href="https://ru.wikipedia.org/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&stable=1">версии, проверенной 12 июня 2023 года</a>; проверки требуют <a class="external text" href="https://ru.wikipedia.org/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&oldid=130991241&diff=cur&diffonly=0">3 правки</a>.</div></div></div></div></div> <div id="contentSub2"></div> <div id="jump-to-nav"></div> <a class="mw-jump-link" href="#mw-head">Перейти к навигации</a> <a class="mw-jump-link" href="#searchInput">Перейти к поиску</a> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="ru" dir="ltr"><figure typeof="mw:File/Thumb"><a href="/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:P_np_np-complete_np-hard.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/400px-P_np_np-complete_np-hard.svg.png" decoding="async" width="400" height="250" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/600px-P_np_np-complete_np-hard.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/800px-P_np_np-complete_np-hard.svg.png 2x" data-file-width="800" data-file-height="500" /></a><figcaption>Взаимоотношение между классами P, NP, NP-complete (NP-полными задачами), NP-hard (NP-трудными задачами) в случае, если <a href="/wiki/%D0%A0%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2_P_%D0%B8_NP" title="Равенство классов P и NP">P≠NP</a> и если P=NP</figcaption></figure> <p><b>NP-полная задача</b> — в <a href="/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2" title="Теория алгоритмов">теории алгоритмов</a> <a href="/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8" class="mw-redirect" title="Проблема разрешимости">задача с ответом «да» или «нет»</a> из <a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_NP" title="Класс NP">класса NP</a>, к которой можно свести любую другую задачу из этого класса за <a href="/wiki/%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%B2%D1%80%D0%B5%D0%BC%D1%8F" class="mw-redirect" title="Полиномиальное время">полиномиальное время</a> (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных). Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них будет найден «полиномиально быстрый» алгоритм решения, то и любую другую задачу из класса NP можно будет решить так же «быстро». </p> <div id="toc" class="toc" role="navigation" aria-labelledby="mw-toc-heading"><input type="checkbox" role="button" id="toctogglecheckbox" class="toctogglecheckbox" style="display:none" /><div class="toctitle" lang="ru" dir="ltr"><h2 id="mw-toc-heading">Содержание</h2><span class="toctogglespan"><label class="toctogglelabel" for="toctogglecheckbox"></label></span></div> <ul> <li class="toclevel-1 tocsection-1"><a href="#Формальное_определение"><span class="tocnumber">1</span> <span class="toctext">Формальное определение</span></a> <ul> <li class="toclevel-2 tocsection-2"><a href="#NP-полнота_в_сильном_смысле"><span class="tocnumber">1.1</span> <span class="toctext">NP-полнота в сильном смысле</span></a></li> </ul> </li> <li class="toclevel-1 tocsection-3"><a href="#Гипотеза_P_≠_NP"><span class="tocnumber">2</span> <span class="toctext">Гипотеза P ≠ NP</span></a></li> <li class="toclevel-1 tocsection-4"><a href="#Примеры_NP-полных_задач"><span class="tocnumber">3</span> <span class="toctext">Примеры NP-полных задач</span></a></li> <li class="toclevel-1 tocsection-5"><a href="#См._также"><span class="tocnumber">4</span> <span class="toctext">См. также</span></a></li> <li class="toclevel-1 tocsection-6"><a href="#Примечания"><span class="tocnumber">5</span> <span class="toctext">Примечания</span></a></li> <li class="toclevel-1 tocsection-7"><a href="#Литература"><span class="tocnumber">6</span> <span class="toctext">Литература</span></a></li> <li class="toclevel-1 tocsection-8"><a href="#Ссылки"><span class="tocnumber">7</span> <span class="toctext">Ссылки</span></a></li> </ul> </div> <div class="mw-heading mw-heading2"><h2 id="Формальное_определение"><span id=".D0.A4.D0.BE.D1.80.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5"></span>Формальное определение</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&veaction=edit&section=1" title="Редактировать раздел «Формальное определение»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit&section=1" title="Редактировать код раздела «Формальное определение»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b><a href="/wiki/%D0%90%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)" class="mw-redirect" title="Алфавит (математика)">Алфавитом</a></b> называется всякое конечное <a href="/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE" title="Множество">множество</a> <a href="/wiki/%D0%A1%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB" title="Символ">символов</a> (например, {<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {0,1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> <mo>,</mo> <mn>1</mn> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {0,1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a019735e07635e5a74673d6e1a34919027e645f5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.359ex; height:2.509ex;" alt="{\displaystyle {0,1}}" /></span>} или {<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {a,b,c}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo>,</mo> <mi>c</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {a,b,c}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3179f0a5b2567df61173909e8f8ea64b228e3365" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.302ex; height:2.509ex;" alt="{\displaystyle {a,b,c}}" /></span>}). Множество всех возможных <b><a href="/wiki/%D0%A1%D0%BB%D0%BE%D0%B2%D0%BE_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)" class="mw-redirect" title="Слово (математика)">слов</a></b> (конечных <a href="/wiki/%D0%A1%D1%82%D1%80%D0%BE%D0%BA%D0%BE%D0%B2%D1%8B%D0%B9_%D1%82%D0%B8%D0%BF" title="Строковый тип">строк</a>, составленных из символов этого алфавита) над некоторым алфавитом <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Σ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e1f558f53cda207614abdf90162266c70bc5c1e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" /></span> обозначается <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma ^{*}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi mathvariant="normal">Σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma ^{*}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/807344600a40f1de7136f8b54576e12e9428bef4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.732ex; height:2.343ex;" alt="{\displaystyle \Sigma ^{*}}" /></span>. <b><a href="/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA" title="Формальный язык">Языком</a></b> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" /></span> над алфавитом <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Σ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e1f558f53cda207614abdf90162266c70bc5c1e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" /></span> называется всякое <a href="/wiki/%D0%9F%D0%BE%D0%B4%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE" title="Подмножество">подмножество</a> множества <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma ^{*}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi mathvariant="normal">Σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma ^{*}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/807344600a40f1de7136f8b54576e12e9428bef4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.732ex; height:2.343ex;" alt="{\displaystyle \Sigma ^{*}}" /></span>, то есть <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\subset \Sigma ^{*}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo>⊂</mo> <msup> <mi mathvariant="normal">Σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L\subset \Sigma ^{*}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec1c407e999a4dd1ae0f1cd964530fee037128ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.414ex; height:2.343ex;" alt="{\displaystyle L\subset \Sigma ^{*}}" /></span>. </p><p><b>Задачей распознавания</b> для языка <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" /></span> называется определение того, принадлежит ли данное слово языку <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" /></span>. </p><p>Пусть <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e79dc1b001f8b923df475ed14de023cbc456013" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{1}}" /></span> и <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a952cfe42c86b7741f55a817da0e251793a358" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{2}}" /></span> — два языка над алфавитом <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Σ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e1f558f53cda207614abdf90162266c70bc5c1e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" /></span>. Язык <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e79dc1b001f8b923df475ed14de023cbc456013" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{1}}" /></span> называется <a href="/wiki/%D0%A1%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%9A%D0%B0%D1%80%D0%BF%D1%83" class="mw-redirect" title="Сведение по Карпу">сводимым (по Карпу)</a> к языку <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a952cfe42c86b7741f55a817da0e251793a358" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{2}}" /></span>, если существует <a href="/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)" title="Функция (математика)">функция</a>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\colon \Sigma ^{*}\to \Sigma ^{*}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo>:</mo> <msup> <mi mathvariant="normal">Σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mo stretchy="false">→</mo> <msup> <mi mathvariant="normal">Σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f\colon \Sigma ^{*}\to \Sigma ^{*}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b376f5a33738dd7e54e169dd61d0608ea325be4f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.391ex; height:2.676ex;" alt="{\displaystyle f\colon \Sigma ^{*}\to \Sigma ^{*}}" /></span>, вычислимая за <a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P" title="Класс P">полиномиальное время</a>, обладающая следующим свойством: </p> <ul><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in L_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de8423376297b3dd2ef4ee4ef988eeb9f45e2126" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.807ex; height:2.509ex;" alt="{\displaystyle x\in L_{1}}" /></span> тогда и только тогда, когда <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)\in L_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)\in L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48801c82facd52c025ec13a6f45abec35f42049c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.895ex; height:2.843ex;" alt="{\displaystyle f(x)\in L_{2}}" /></span>. Сводимость по Карпу обозначается как <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{1}{\leq }_{p}L_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mrow class="MJX-TeXAtom-ORD"> <mo>≤</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> </mrow> </msub> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}{\leq }_{p}L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83fffbaf5b748705af37fb1ef4c1343b46fdf793" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.141ex; height:2.843ex;" alt="{\displaystyle L_{1}{\leq }_{p}L_{2}}" /></span> или <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{1}\varpropto L_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>∝</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}\varpropto L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9a159fc99bfc7aa9213abf7ad9b8782260a2aee9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.373ex; height:2.509ex;" alt="{\displaystyle L_{1}\varpropto L_{2}}" /></span>.</li></ul> <p>Язык <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a952cfe42c86b7741f55a817da0e251793a358" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{2}}" /></span> называется <b><span id="NP-hard" class="highlight-target">NP-трудным</span></b>, если любой язык из класса NP сводится к нему. Язык называют <b>NP-полным</b>, если он NP-труден, и при этом сам лежит в классе NP. </p><p>Неформально говоря, то что задача <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" /></span> сводится к задаче <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" /></span>, означает, что задача <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" /></span> «не сложнее» задачи <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" /></span> (так как, если мы можем решить <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" /></span>, то можем решить и <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" /></span>). Таким образом, класс NP-трудных задач включает NP-полные задачи и задачи, которые «сложнее» их (то есть те задачи, к которым могут быть сведены NP-полные задачи). Класс NP включает NP-полные задачи и задачи, которые «легче» их (то есть те задачи, которые сводятся к NP-полным задачам). </p><p>Из определения следует, что, если будет найден алгоритм, решающий некоторую (любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в <a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P" title="Класс P">классе P</a>, то есть будут решаться за полиномиальное время. </p> <div class="mw-heading mw-heading3"><h3 id="NP-полнота_в_сильном_смысле"><span id="NP-.D0.BF.D0.BE.D0.BB.D0.BD.D0.BE.D1.82.D0.B0_.D0.B2_.D1.81.D0.B8.D0.BB.D1.8C.D0.BD.D0.BE.D0.BC_.D1.81.D0.BC.D1.8B.D1.81.D0.BB.D0.B5"></span>NP-полнота в сильном смысле</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&veaction=edit&section=2" title="Редактировать раздел «NP-полнота в сильном смысле»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit&section=2" title="Редактировать код раздела «NP-полнота в сильном смысле»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <div role="note" class="hatnote navigation-not-searchable ts-main"><style data-mw-deduplicate="TemplateStyles:r142002967">.mw-parser-output .ts-main a{font-weight:bold}.mw-parser-output .ts-main a.new,.mw-parser-output .ts-main a.extiw,.mw-parser-output .ts-main a.external{font-weight:normal}</style>Основная статья: <span data-interwiki-lang="en" data-interwiki-article="Strong NP-completeness"><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B0_%D0%B2_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC_%D1%81%D0%BC%D1%8B%D1%81%D0%BB%D0%B5&action=edit&redlink=1" class="new" title="NP-полнота в сильном смысле (страница отсутствует)">NP-полнота в сильном смысле</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/Strong_NP-completeness" class="extiw" title="en:Strong NP-completeness"><span title="Strong NP-completeness — версия статьи «NP-полнота в сильном смысле» на английском языке">[англ.]</span></a></sup></div> <p>Задача называется <b>NP-полной в сильном смысле</b>, если у неё существует подзадача, которая: </p> <ol><li>не является <a href="/w/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D1%81_%D1%87%D0%B8%D1%81%D0%BB%D0%BE%D0%B2%D1%8B%D0%BC%D0%B8_%D0%BF%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D0%B0%D0%BC%D0%B8&action=edit&redlink=1" class="new" title="Задача с числовыми параметрами (страница отсутствует)">задачей с числовыми параметрами</a> (то есть максимальное значение величин, встречающихся в этой задаче, ограничено сверху полиномом от длины входа)</li> <li>является NP-полной.</li></ol> <p>Класс таких задач называется <b>NPCS</b>. Если <a href="/wiki/%D0%A0%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2_P_%D0%B8_NP" title="Равенство классов P и NP">гипотеза P ≠ NP</a> верна, то для NPCS-задачи не существует <a href="/wiki/%D0%9F%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D0%BF%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC" title="Псевдополиномиальный алгоритм">псевдополиномиального алгоритма</a><style data-mw-deduplicate="TemplateStyles:r141254988">.mw-parser-output .ts-fix-template{font-style:normal;font-weight:normal;white-space:nowrap}.mw-parser-output .ts-fix-error{font-size:inherit}@media screen{.mw-parser-output .ts-fix-text{border:1px solid var(--border-color-base,#a2a9b1);box-decoration-break:clone;margin:0 -0.1em;padding:0 0.1em;transition:background 0.1s}.mw-parser-output .ts-fix-text:hover{background:#fee7e6}html.skin-theme-clientpref-night .mw-parser-output .ts-fix-text:hover{background:#4f1312}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .ts-fix-text:hover{background:#4f1312}}@media screen and (hover:hover){.mw-parser-output .ts-fix-comment,.mw-parser-output .ts-fix-commented>a:not(:hover){border-bottom:1px dotted;text-decoration:none}}</style><sup class="ts-fix-template noprint">[<i><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%81%D1%8B%D0%BB%D0%BA%D0%B8_%D0%BD%D0%B0_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8" title="Википедия:Ссылки на источники"><span title="нет источника (12 июля 2017)">источник не указан 2790 дней</span></a></i>]</sup>. </p> <div class="mw-heading mw-heading2"><h2 id="Гипотеза_P_≠_NP"><span id=".D0.93.D0.B8.D0.BF.D0.BE.D1.82.D0.B5.D0.B7.D0.B0_P_.E2.89.A0_NP"></span>Гипотеза P ≠ NP</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&veaction=edit&section=3" title="Редактировать раздел «Гипотеза P ≠ NP»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit&section=3" title="Редактировать код раздела «Гипотеза P ≠ NP»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <div role="note" class="hatnote navigation-not-searchable ts-main"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r142002967" />Основная статья: <a href="/wiki/%D0%A0%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2_P_%D0%B8_NP" title="Равенство классов P и NP">Равенство классов P и NP</a></div> <p>Вопрос о совпадении классов P и NP уже более пятидесяти лет является одной из центральных <a href="/wiki/%D0%9E%D1%82%D0%BA%D1%80%D1%8B%D1%82%D0%B0%D1%8F_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0" class="mw-redirect" title="Открытая проблема">открытых проблем</a>. Научное сообщество склоняется к отрицательному ответу на этот вопрос<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> — в этом случае решать NP-полные задачи за полиномиальное время не удастся. </p> <div class="mw-heading mw-heading2"><h2 id="Примеры_NP-полных_задач"><span id=".D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.80.D1.8B_NP-.D0.BF.D0.BE.D0.BB.D0.BD.D1.8B.D1.85_.D0.B7.D0.B0.D0.B4.D0.B0.D1.87"></span>Примеры NP-полных задач</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&veaction=edit&section=4" title="Редактировать раздел «Примеры NP-полных задач»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit&section=4" title="Редактировать код раздела «Примеры NP-полных задач»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <div role="note" class="hatnote navigation-not-searchable ts-main"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r142002967" />Основная статья: <span data-interwiki-lang="en" data-interwiki-article="List of NP-complete problems"><a href="/w/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87&action=edit&redlink=1" class="new" title="Список NP-полных задач (страница отсутствует)">Список NP-полных задач</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/List_of_NP-complete_problems" class="extiw" title="en:List of NP-complete problems"><span title="List of NP-complete problems — версия статьи «Список NP-полных задач» на английском языке">[англ.]</span></a></sup></div> <div class="columns" style=";column-width: 30em;"> <ul><li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B2%D1%8B%D0%BF%D0%BE%D0%BB%D0%BD%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D1%8B%D1%85_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB" title="Задача выполнимости булевых формул">Задача о выполнимости булевых формул</a></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0" title="Задача коммивояжёра">Задача коммивояжёра</a></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B8" title="Задача о вершинном покрытии">Задача о вершинном покрытии</a></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0" title="Задача о покрытии множества">Задача о покрытии множества</a></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D0%BC_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B5" title="Задача о независимом множестве">Задача о независимом множестве</a></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BA%D0%BB%D0%B8%D0%BA%D0%B5" title="Задача о клике">Задача о клике</a></li> <li><a href="/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%A8%D1%82%D0%B5%D0%B9%D0%BD%D0%B5%D1%80%D0%B0" class="mw-redirect" title="Проблема Штейнера">Проблема Штейнера</a></li> <li><a href="/wiki/%D0%A0%D0%B0%D1%81%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%B0" class="mw-redirect" title="Раскраска графа">Проблема раскраски графа</a></li> <li><a href="/wiki/%D0%98%D0%B3%D1%80%D0%B0_%D0%B2_15" title="Игра в 15">Пятнашки</a></li> <li><a href="/wiki/%D0%A1%D1%83%D0%B4%D0%BE%D0%BA%D1%83" title="Судоку">Судоку</a></li> <li><a href="/wiki/%D0%A1%D0%B0%D0%BF%D1%91%D1%80_(%D0%B8%D0%B3%D1%80%D0%B0)" title="Сапёр (игра)">Сапёр</a></li> <li><a href="/wiki/%D0%A2%D0%B5%D1%82%D1%80%D0%B8%D1%81" title="Тетрис">Тетрис</a><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></li> <li><a href="/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D0%BA-%D0%B7%D0%BC%D0%B5%D0%B9%D0%BA%D0%B0" title="Кубик-змейка">Кубик-змейка</a><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="См._также"><span id=".D0.A1.D0.BC._.D1.82.D0.B0.D0.BA.D0.B6.D0.B5"></span>См. также</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&veaction=edit&section=5" title="Редактировать раздел «См. также»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit&section=5" title="Редактировать код раздела «См. также»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/%D0%A0%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2_P_%D0%B8_NP" title="Равенство классов P и NP">Равенство классов P и NP</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Примечания"><span id=".D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.87.D0.B0.D0.BD.D0.B8.D1.8F"></span>Примечания</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&veaction=edit&section=6" title="Редактировать раздел «Примечания»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit&section=6" title="Редактировать код раздела «Примечания»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="reflist columns" style="list-style-type: decimal;"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><span class="citation"><i>William I. Gasarch.</i> <a rel="nofollow" class="external text" href="http://www.cs.umd.edu/~gasarch/papers/poll.pdf">The P=?NP poll.</a> <small class="ref-info" style="cursor:help;" title="на неопределённом языке">(неопр.)</small> // SIGACT News. — 2002. — <span class="nowrap">Т. 33</span>, <span class="nowrap">№ 2</span>. — <span class="nowrap">С. 34—47</span>. — <a href="/wiki/Doi" class="mw-redirect" title="Doi">doi</a>:<a rel="nofollow" class="external text" href="https://dx.doi.org/10.1145%2F1052796.1052804">10.1145/1052796.1052804</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20070615132837/http://www.cs.umd.edu/~gasarch/papers/poll.pdf">Архивировано</a> 15 июня 2007 года.</span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. <a rel="nofollow" class="external text" href="http://arxiv.org/abs/cs.CC/0210020">Tetris is Hard, Even to Approximate</a> <small class="ref-info" style="cursor:help;" title="на английском языке">(англ.)</small>. preprint.</span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r141305934">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a::after,.mw-parser-output .id-lock-limited a::after,.mw-parser-output .id-lock-registration a::after,.mw-parser-output .id-lock-subscription a::after,.mw-parser-output .cs1-ws-icon a::after{content:"";width:1.1em;height:1.1em;display:inline-block;vertical-align:middle;background-position:center;background-repeat:no-repeat;background-size:contain}.mw-parser-output .id-lock-free.id-lock-free a::after{background-image:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")}.mw-parser-output .id-lock-limited.id-lock-limited a::after,.mw-parser-output .id-lock-registration.id-lock-registration a::after{background-image:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")}.mw-parser-output .id-lock-subscription.id-lock-subscription a::after{background-image:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")}.mw-parser-output .cs1-ws-icon a::after{background-image:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}html.skin-theme-clientpref-night .mw-parser-output .id-lock-free a::after,html.skin-theme-clientpref-night .mw-parser-output .id-lock-limited a::after,html.skin-theme-clientpref-night .mw-parser-output .id-lock-registration a::after,html.skin-theme-clientpref-night .mw-parser-output .id-lock-subscription a::after{filter:invert(1)hue-rotate(180deg)}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}html.skin-theme-clientpref-os .mw-parser-output .id-lock-free a::after,html.skin-theme-clientpref-os .mw-parser-output .id-lock-limited a::after,html.skin-theme-clientpref-os .mw-parser-output .id-lock-registration a::after,html.skin-theme-clientpref-os .mw-parser-output .id-lock-subscription a::after{filter:invert(1)hue-rotate(180deg)}}</style><cite id="CITEREFAbelDemaineDemaineEisenstat2013" class="citation journal cs1">Abel, Z.; Demaine, E.D.; Demaine, M.L.; Eisenstat, S.; Lynch, J.; Schardl, T.B. (2013). <a rel="nofollow" class="external text" href="https://www.jstage.jst.go.jp/article/ipsjjip/21/3/21_368/_article">Finding a Hamiltonian Path in a Cube with Specified Turns is Hard</a>. <i>Journal of Information Processing</i>. <b>21</b> (3): <span class="nowrap">368–</span>377. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20231205122650/https://www.jstage.jst.go.jp/article/ipsjjip/21/3/21_368/_article">Архивировано</a> 5 декабря 2023<span class="reference-accessdate">. Дата обращения: 5 декабря 2023</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Information+Processing&rft.atitle=Finding+a+Hamiltonian+Path+in+a+Cube+with+Specified+Turns+is+Hard&rft.volume=21&rft.issue=3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E368-%3C%2Fspan%3E377&rft.date=2013&rft.aulast=Abel&rft.aufirst=Z.&rft.au=Demaine%2C+E.D.&rft.au=Demaine%2C+M.L.&rft.au=Eisenstat%2C+S.&rft.au=Lynch%2C+J.&rft.au=Schardl%2C+T.B.&rft_id=https%3A%2F%2Fwww.jstage.jst.go.jp%2Farticle%2Fipsjjip%2F21%2F3%2F21_368%2F_article&rfr_id=info%3Asid%2Fru.wikipedia.org%3ANP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F+%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Литература"><span id=".D0.9B.D0.B8.D1.82.D0.B5.D1.80.D0.B0.D1.82.D1.83.D1.80.D0.B0"></span>Литература</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&veaction=edit&section=7" title="Редактировать раздел «Литература»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit&section=7" title="Редактировать код раздела «Литература»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><i>Гэри М., Джонсон Д.</i> <a rel="nofollow" class="external text" href="http://trpl7.ru/t-books/NP-book126.pdf">Вычислительные машины и труднорешаемые задачи</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20191104180723/http://trpl7.ru/t-books/NP-book126.pdf">Архивная копия</a> от 4 ноября 2019 на <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>. М.: Мир, 1982.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r141305934" /><span class="citation no-wikidata" data-wikidata-property-id="P1343"><i>Томас Х. Кормен и др.</i> <span data-wikidata-qualifier-id="P248"><b>Глава 34. NP-полнота</b></span> // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — <abbr title="Москва">М.</abbr>: <a href="/w/index.php?title=%D0%92%D0%B8%D0%BB%D1%8C%D1%8F%D0%BC%D1%81_(%D0%B8%D0%B7%D0%B4%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE)&action=edit&redlink=1" class="new" title="Вильямс (издательство) (страница отсутствует)">«Вильямс»</a>, 2006. — 1296 с. — <a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%98%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8_%D0%BA%D0%BD%D0%B8%D0%B3/0070131511" class="internal mw-magiclink-isbn">ISBN 0-07-013151-1</a>.</span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r141305934" /><span class="citation no-wikidata" data-wikidata-property-id="P1343"><i><a href="/wiki/%D0%94%D0%B6%D0%BE%D0%BD_%D0%A5%D0%BE%D0%BF%D0%BA%D1%80%D0%BE%D1%84%D1%82" class="mw-redirect" title="Джон Хопкрофт">Джон Хопкрофт</a>, Раджив Мотвани, Джеффри Ульман.</i> Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — <abbr title="Москва">М.</abbr>: <a href="/w/index.php?title=%D0%92%D0%B8%D0%BB%D1%8C%D1%8F%D0%BC%D1%81_(%D0%B8%D0%B7%D0%B4%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE)&action=edit&redlink=1" class="new" title="Вильямс (издательство) (страница отсутствует)">«Вильямс»</a>, 2002. — 528 с. — <a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%98%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8_%D0%BA%D0%BD%D0%B8%D0%B3/0201441241" class="internal mw-magiclink-isbn">ISBN 0-201-44124-1</a>.</span></li></ul> <div class="mw-heading mw-heading2"><h2 id="Ссылки"><span id=".D0.A1.D1.81.D1.8B.D0.BB.D0.BA.D0.B8"></span>Ссылки</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&veaction=edit&section=8" title="Редактировать раздел «Ссылки»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit&section=8" title="Редактировать код раздела «Ссылки»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20070616041921/http://rain.ifmo.ru/cat/view.php/theory/algorithm-analysis/np-completeness-2004">NP-полнота</a></li> <li><a rel="nofollow" class="external text" href="http://www.ics.uci.edu/~eppstein/cgt/hard.html">Вычислительная сложность игр и головоломок</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20061206012118/http://www.ics.uci.edu/~eppstein/cgt/hard.html">Архивная копия</a> от 6 декабря 2006 на <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> <small class="ref-info" style="cursor:help;" title="на английском языке">(англ.)</small></li> <li><a rel="nofollow" class="external text" href="http://www.nada.kth.se/~viggo/problemlist/compendium.html">A compendium of NP optimization problems. Editors — Pierluigi Crescenzi, Viggo Kann</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20061205232508/http://www.nada.kth.se/~viggo/problemlist/compendium.html">Архивная копия</a> от 5 декабря 2006 на <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> <small class="ref-info" style="cursor:help;" title="на английском языке">(англ.)</small></li></ul> <p><br /> </p> <div role="navigation" class="navbox" aria-labelledby="Классы_сложности_алгоритмов" data-name="Классы сложности"><table class="nowraplinks collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="colgroup" class="navbox-title" colspan="2"><span class="navbox-gear" style="float:left;text-align:left;width:5em;margin-right:0.5em"><span class="noprint skin-invert-image" typeof="mw:File"><a href="/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D1%8B_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8" title="Перейти к шаблону «Классы сложности»"><img alt="Перейти к шаблону «Классы сложности»" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/14px-Wikipedia_interwiki_section_gear_icon.svg.png" decoding="async" width="14" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/21px-Wikipedia_interwiki_section_gear_icon.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/28px-Wikipedia_interwiki_section_gear_icon.svg.png 2x" data-file-width="14" data-file-height="14" /></a></span></span><div id="Классы_сложности_алгоритмов" style="font-size:114%;margin:0 5em"><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8" title="Класс сложности">Классы сложности</a> <a href="/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC" title="Алгоритм">алгоритмов</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1px">Считаются лёгкими</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><span data-interwiki-lang="en" data-interwiki-article="DLOGTIME"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_DLOGTIME&action=edit&redlink=1" class="new" title="Класс DLOGTIME (страница отсутствует)">DLOGTIME</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/DLOGTIME" class="extiw" title="en:DLOGTIME"><span title="DLOGTIME — версия статьи «Класс DLOGTIME» на английском языке">[англ.]</span></a></sup></li> <li><span data-interwiki-lang="en" data-interwiki-article="AC0"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_AC0&action=edit&redlink=1" class="new" title="Класс AC0 (страница отсутствует)">AC<sup>0</sup></a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/AC0" class="extiw" title="en:AC0"><span title="AC0 — версия статьи «Класс AC0» на английском языке">[англ.]</span></a></sup></li> <li><span data-interwiki-lang="en" data-interwiki-article="ACC0"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_ACC0&action=edit&redlink=1" class="new" title="Класс ACC0 (страница отсутствует)">ACC<sup>0</sup></a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/ACC0" class="extiw" title="en:ACC0"><span title="ACC0 — версия статьи «Класс ACC0» на английском языке">[англ.]</span></a></sup></li> <li><span data-interwiki-lang="en" data-interwiki-article="TC0"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_TC0&action=edit&redlink=1" class="new" title="Класс TC0 (страница отсутствует)">TC<sup>0</sup></a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/TC0" class="extiw" title="en:TC0"><span title="TC0 — версия статьи «Класс TC0» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_L" class="mw-redirect" title="Класс L">L</a></li> <li><span data-interwiki-lang="en" data-interwiki-article="SL (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_SL&action=edit&redlink=1" class="new" title="Класс SL (страница отсутствует)">SL</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/SL_(complexity)" class="extiw" title="en:SL (complexity)"><span title="SL (complexity) — версия статьи «Класс SL» на английском языке">[англ.]</span></a></sup></li> <li><span data-interwiki-lang="en" data-interwiki-article="RL (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_RL&action=edit&redlink=1" class="new" title="Класс RL (страница отсутствует)">RL</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/RL_(complexity)" class="extiw" title="en:RL (complexity)"><span title="RL (complexity) — версия статьи «Класс RL» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_NL" class="mw-redirect" title="Класс NL">NL</a></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_NC" title="Класс NC">NC</a></li> <li><span data-interwiki-lang="en" data-interwiki-article="SC (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_SC&action=edit&redlink=1" class="new" title="Класс SC (страница отсутствует)">SC</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/SC_(complexity)" class="extiw" title="en:SC (complexity)"><span title="SC (complexity) — версия статьи «Класс SC» на английском языке">[англ.]</span></a></sup></li> <li><span data-interwiki-lang="en" data-interwiki-article="CC (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_CC&action=edit&redlink=1" class="new" title="Класс CC (страница отсутствует)">CC</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/CC_(complexity)" class="extiw" title="en:CC (complexity)"><span title="CC (complexity) — версия статьи «Класс CC» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P" title="Класс P">P</a> <ul><li><span data-interwiki-lang="en" data-interwiki-article="P-complete"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P-complete&action=edit&redlink=1" class="new" title="Класс P-complete (страница отсутствует)">P-complete</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/P-complete" class="extiw" title="en:P-complete"><span title="P-complete — версия статьи «Класс P-complete» на английском языке">[англ.]</span></a></sup></li></ul></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_ZPP" title="Класс ZPP">ZPP</a></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_RP" title="Класс RP">RP</a></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_BPP" title="Класс BPP">BPP</a></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_BQP" title="Класс BQP">BQP</a></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_EQP" title="Класс EQP">EQP</a></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_APX" title="Класс APX">APX</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px">Предполагаются сложными</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><span data-interwiki-lang="en" data-interwiki-article="UP (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_UP&action=edit&redlink=1" class="new" title="Класс UP (страница отсутствует)">UP</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/UP_(complexity)" class="extiw" title="en:UP (complexity)"><span title="UP (complexity) — версия статьи «Класс UP» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_NP" title="Класс NP">NP</a> <ul><li><a class="mw-selflink selflink">NP-complete</a></li></ul></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_co-NP" title="Класс co-NP">co-NP</a> <ul><li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_co-NP-complete" title="Класс co-NP-complete">co-NP-complete</a></li></ul></li> <li><span data-interwiki-lang="en" data-interwiki-article="AM (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_AM&action=edit&redlink=1" class="new" title="Класс AM (страница отсутствует)">AM</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/AM_(complexity)" class="extiw" title="en:AM (complexity)"><span title="AM (complexity) — версия статьи «Класс AM» на английском языке">[англ.]</span></a></sup></li> <li><span data-interwiki-lang="en" data-interwiki-article="MA (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_MA&action=edit&redlink=1" class="new" title="Класс MA (страница отсутствует)">MA</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/MA_(complexity)" class="extiw" title="en:MA (complexity)"><span title="MA (complexity) — версия статьи «Класс MA» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_QMA" title="Класс QMA">QMA</a></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_PH" title="Класс PH">PH</a></li> <li><span data-interwiki-lang="en" data-interwiki-article="Parity P"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_%E2%8A%95P&action=edit&redlink=1" class="new" title="Класс ⊕P (страница отсутствует)">⊕P</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/Parity_P" class="extiw" title="en:Parity P"><span title="Parity P — версия статьи «Класс ⊕P» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_PP" title="Класс PP">PP</a></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_%E2%99%AFP" title="Класс ♯P">#P</a> <ul><li><span data-interwiki-lang="en" data-interwiki-article="♯P-complete"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_%E2%99%AFP-complete&action=edit&redlink=1" class="new" title="Класс ♯P-complete (страница отсутствует)">#P-complete</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/%E2%99%AFP-complete" class="extiw" title="en:♯P-complete"><span title="♯P-complete — версия статьи «Класс ♯P-complete» на английском языке">[англ.]</span></a></sup></li></ul></li> <li><span data-interwiki-lang="en" data-interwiki-article="IP (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_IP&action=edit&redlink=1" class="new" title="Класс IP (страница отсутствует)">IP</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/IP_(complexity)" class="extiw" title="en:IP (complexity)"><span title="IP (complexity) — версия статьи «Класс IP» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_PSPACE" title="Класс PSPACE">PSPACE</a> <ul><li><span data-interwiki-lang="en" data-interwiki-article="PSPACE-complete"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_PSPACE-complete&action=edit&redlink=1" class="new" title="Класс PSPACE-complete (страница отсутствует)">PSPACE-complete</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/PSPACE-complete" class="extiw" title="en:PSPACE-complete"><span title="PSPACE-complete — версия статьи «Класс PSPACE-complete» на английском языке">[англ.]</span></a></sup></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px">Считаются сложными</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_EXPTIME" title="Класс EXPTIME">EXPTIME</a></li> <li><span data-interwiki-lang="en" data-interwiki-article="NEXPTIME"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_NEXPTIME&action=edit&redlink=1" class="new" title="Класс NEXPTIME (страница отсутствует)">NEXPTIME</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/NEXPTIME" class="extiw" title="en:NEXPTIME"><span title="NEXPTIME — версия статьи «Класс NEXPTIME» на английском языке">[англ.]</span></a></sup></li> <li><span data-interwiki-lang="en" data-interwiki-article="EXPSPACE"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_EXPSPACE&action=edit&redlink=1" class="new" title="Класс EXPSPACE (страница отсутствует)">EXPSPACE</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/EXPSPACE" class="extiw" title="en:EXPSPACE"><span title="EXPSPACE — версия статьи «Класс EXPSPACE» на английском языке">[англ.]</span></a></sup></li> <li><span data-interwiki-lang="en" data-interwiki-article="2-EXPTIME"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_2-EXPTIME&action=edit&redlink=1" class="new" title="Класс 2-EXPTIME (страница отсутствует)">2-EXPTIME</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/2-EXPTIME" class="extiw" title="en:2-EXPTIME"><span title="2-EXPTIME — версия статьи «Класс 2-EXPTIME» на английском языке">[англ.]</span></a></sup></li> <li><span data-interwiki-lang="en" data-interwiki-article="ELEMENTARY"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_ELEMENTARY&action=edit&redlink=1" class="new" title="Класс ELEMENTARY (страница отсутствует)">ELEMENTARY</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/ELEMENTARY" class="extiw" title="en:ELEMENTARY"><span title="ELEMENTARY — версия статьи «Класс ELEMENTARY» на английском языке">[англ.]</span></a></sup></li> <li><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_R&action=edit&redlink=1" class="new" title="Класс R (страница отсутствует)">R</a></li> <li><span data-interwiki-lang="en" data-interwiki-article="PR (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_PR&action=edit&redlink=1" class="new" title="Класс PR (страница отсутствует)">PR</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/PR_(complexity)" class="extiw" title="en:PR (complexity)"><span title="PR (complexity) — версия статьи «Класс PR» на английском языке">[англ.]</span></a></sup></li> <li><span data-interwiki-lang="en" data-interwiki-article="RE (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_RE&action=edit&redlink=1" class="new" title="Класс RE (страница отсутствует)">RE</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/RE_(complexity)" class="extiw" title="en:RE (complexity)"><span title="RE (complexity) — версия статьи «Класс RE» на английском языке">[англ.]</span></a></sup> <ul><li><span data-interwiki-lang="en" data-interwiki-article="RE-complete"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_RE-complete&action=edit&redlink=1" class="new" title="Класс RE-complete (страница отсутствует)">RE-complete</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/RE-complete" class="extiw" title="en:RE-complete"><span title="RE-complete — версия статьи «Класс RE-complete» на английском языке">[англ.]</span></a></sup></li></ul></li> <li><span data-interwiki-lang="en" data-interwiki-article="co-RE"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_Co-RE&action=edit&redlink=1" class="new" title="Класс Co-RE (страница отсутствует)">Co-RE</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/co-RE" class="extiw" title="en:co-RE"><span title="co-RE — версия статьи «Класс Co-RE» на английском языке">[англ.]</span></a></sup> <ul><li><span data-interwiki-lang="en" data-interwiki-article="Co-RE-complete"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_Co-RE-complete&action=edit&redlink=1" class="new" title="Класс Co-RE-complete (страница отсутствует)">Co-RE-complete</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/Co-RE-complete" class="extiw" title="en:Co-RE-complete"><span title="Co-RE-complete — версия статьи «Класс Co-RE-complete» на английском языке">[англ.]</span></a></sup></li></ul></li> <li><span data-interwiki-lang="en" data-interwiki-article="ALL (complexity)"><a href="/w/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_ALL&action=edit&redlink=1" class="new" title="Класс ALL (страница отсутствует)">ALL</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/ALL_(complexity)" class="extiw" title="en:ALL (complexity)"><span title="ALL (complexity) — версия статьи «Класс ALL» на английском языке">[англ.]</span></a></sup></li></ul> </div></td></tr></tbody></table></div> <div role="navigation" class="navbox" aria-labelledby="NP-полные_задачи" data-name="NP-полные задачи"><table class="nowraplinks collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="colgroup" class="navbox-title" colspan="2"><span class="navbox-gear" style="float:left;text-align:left;width:5em;margin-right:0.5em"><span class="noprint skin-invert-image" typeof="mw:File"><a href="/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:NP-%D0%BF%D0%BE%D0%BB%D0%BD%D1%8B%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8" title="Перейти к шаблону «NP-полные задачи»"><img alt="Перейти к шаблону «NP-полные задачи»" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/14px-Wikipedia_interwiki_section_gear_icon.svg.png" decoding="async" width="14" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/21px-Wikipedia_interwiki_section_gear_icon.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/28px-Wikipedia_interwiki_section_gear_icon.svg.png 2x" data-file-width="14" data-file-height="14" /></a></span></span><div id="NP-полные_задачи" style="font-size:114%;margin:0 5em"><a class="mw-selflink selflink">NP-полные задачи</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/w/index.php?title=%D0%9C%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit&redlink=1" class="new" title="Максимизационная задача (страница отсутствует)">Максимизационная задача</a><br /><a href="/wiki/%D0%A3%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B0" title="Упаковка">укладки (упаковки)</a></th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE%D0%B1_%D1%83%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B5_%D0%B2_%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%B9%D0%BD%D0%B5%D1%80%D1%8B" title="Задача об упаковке в контейнеры">Упаковка в контейнеры</a> <ul><li><a href="/w/index.php?title=%D0%94%D0%B2%D1%83%D0%BC%D0%B5%D1%80%D0%BD%D0%B0%D1%8F_%D1%83%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B0&action=edit&redlink=1" class="new" title="Двумерная упаковка (страница отсутствует)">двумерная упаковка</a></li> <li><a href="/w/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%83%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B0&action=edit&redlink=1" class="new" title="Линейная упаковка (страница отсутствует)">линейная упаковка</a></li> <li><a href="/w/index.php?title=%D0%A3%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D0%BE_%D0%B2%D0%B5%D1%81%D1%83&action=edit&redlink=1" class="new" title="Упаковка по весу (страница отсутствует)">упаковка по весу</a></li> <li><a href="/w/index.php?title=%D0%A3%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D0%BE_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8&action=edit&redlink=1" class="new" title="Упаковка по стоимости (страница отсутствует)">упаковка по стоимости</a></li></ul></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5" title="Задача о рюкзаке">Задача о рюкзаке</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2" title="Теория графов">Теория графов</a><br /><a href="/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2" title="Теория множеств">теория множеств</a></th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B8" title="Задача о вершинном покрытии">Задача о вершинном покрытии</a></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BA%D0%BB%D0%B8%D0%BA%D0%B5" title="Задача о клике">Задача о клике</a></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D0%BC_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B5" title="Задача о независимом множестве">Задача о независимом множестве (наборе)</a></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0" title="Задача о покрытии множества">Задача о покрытии множества</a></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%A8%D1%82%D0%B5%D0%B9%D0%BD%D0%B5%D1%80%D0%B0_%D0%BE_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5" title="Задача Штейнера о минимальном дереве">Задача Штейнера</a></li> <li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0" title="Задача коммивояжёра">Задача коммивояжёра</a></li> <li><a href="/wiki/%D0%9E%D0%B1%D0%BE%D0%B1%D1%89%D1%91%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0" title="Обобщённая задача коммивояжёра">Обобщённая задача коммивояжёра</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9" title="Теория сложности вычислений">Алгоритмические задачи</a></th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B2%D1%8B%D0%BF%D0%BE%D0%BB%D0%BD%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D1%8B%D1%85_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB" title="Задача выполнимости булевых формул">Задача выполнимости булевых формул (в конъюнктивной нормальной форме)</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/wiki/%D0%98%D0%B3%D1%80%D0%B0#Логические_игры" title="Игра">Логические игры</a><br /><a href="/wiki/%D0%93%D0%BE%D0%BB%D0%BE%D0%B2%D0%BE%D0%BB%D0%BE%D0%BC%D0%BA%D0%B0" title="Головоломка">и головоломки</a></th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%98%D0%B3%D1%80%D0%B0_%D0%B2_15" title="Игра в 15">Обобщённые пятнашки (игра в <i>N</i><sup>2</sup>-1)</a> <ul><li><a href="/w/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BA%D1%80%D0%B0%D1%82%D1%87%D0%B0%D0%B9%D1%88%D0%B5%D0%B3%D0%BE_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D1%8F&action=edit&redlink=1" class="new" title="Задача поиска кратчайшего решения (страница отсутствует)">задача поиска кратчайшего решения</a></li></ul></li> <li><a href="/wiki/%D0%A2%D0%B5%D1%82%D1%80%D0%B8%D1%81#Теоретические_проблемы" title="Тетрис">Задачи, решения которых применяются в Тетрис</a></li> <li><a href="/wiki/%D0%9E%D0%B1%D0%BE%D0%B1%D1%89%D1%91%D0%BD%D0%BD%D0%BE%D0%B5_%D1%81%D1%83%D0%B4%D0%BE%D0%BA%D1%83" title="Обобщённое судоку">Задача обобщённого судоку</a></li> <li><a href="/wiki/%D0%9B%D0%B0%D1%82%D0%B8%D0%BD%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82" title="Латинский квадрат">Задача о заполнении латинского квадрата</a></li> <li><a href="/wiki/%D0%9A%D0%B0%D0%BA%D1%83%D1%80%D0%BE" title="Какуро">Задача какуро</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2"><div> <ul><li><a href="/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8" title="Класс сложности">Классы сложности</a></li> <li><a href="/wiki/%D0%98%D1%81%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9" title="Исследование операций">Исследование операций</a></li> <li><a href="/wiki/%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)" title="Оптимизация (математика)">Оптимизация</a></li> <li><a href="/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%BD%D0%B0%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F" title="Комбинаторная оптимизация">Комбинаторная оптимизация</a></li> <li><a href="/wiki/%D0%9F%D1%80%D0%B8%D0%BA%D0%BB%D0%B0%D0%B4%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0" title="Прикладная математика">Прикладная математика</a></li> <li><a href="/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2" title="Теория алгоритмов">Теория алгоритмов</a></li> <li><a href="/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5" title="Динамическое программирование">Динамическое программирование</a></li> <li><a href="/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%9A%D0%B0%D1%80%D0%BF%D0%B0" title="Список Карпа">21 NP-полная задача Карпа</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Источник — <a dir="ltr" href="https://ru.wikipedia.org/w/index.php?title=NP-полная_задача&oldid=139421010">https://ru.wikipedia.org/w/index.php?title=NP-полная_задача&oldid=139421010</a></div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B8" title="Служебная:Категории">Категория</a>: <ul><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:NP-%D0%BF%D0%BE%D0%BB%D0%BD%D1%8B%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8" title="Категория:NP-полные задачи">NP-полные задачи</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Скрытые категории: <ul><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A1%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B,_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D1%83%D1%8E%D1%89%D0%B8%D0%B5_%D1%80%D0%B0%D1%81%D1%88%D0%B8%D1%80%D0%B5%D0%BD%D0%B8%D0%B5_JsonConfig" title="Категория:Страницы, использующие расширение JsonConfig">Страницы, использующие расширение JsonConfig</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B_%D1%81_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D0%B5%D0%BC_Hatnote_%D1%81_%D0%B3%D0%BE%D1%82%D0%BE%D0%B2%D1%8B%D0%BC_%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC" title="Категория:Википедия:Страницы с модулем Hatnote с готовым форматированием">Википедия:Страницы с модулем Hatnote с готовым форматированием</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D0%B1%D0%B5%D0%B7_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2_(%D0%BD%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D1%91%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE_%D1%82%D0%B8%D0%BF%D0%B0%D0%BC)" title="Категория:Википедия:Статьи без источников (не распределённые по типам)">Википедия:Статьи без источников (не распределённые по типам)</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9D%D0%B5%D1%82_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2_%D1%81_%D0%B8%D1%8E%D0%BB%D1%8F_2017" title="Категория:Википедия:Нет источников с июля 2017">Википедия:Нет источников с июля 2017</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D1%81_%D1%83%D1%82%D0%B2%D0%B5%D1%80%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F%D0%BC%D0%B8_%D0%B1%D0%B5%D0%B7_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2_%D0%B1%D0%BE%D0%BB%D0%B5%D0%B5_14_%D0%B4%D0%BD%D0%B5%D0%B9" title="Категория:Википедия:Статьи с утверждениями без источников более 14 дней">Википедия:Статьи с утверждениями без источников более 14 дней</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A1%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B,_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D1%83%D1%8E%D1%89%D0%B8%D0%B5_%D0%B2%D0%BE%D0%BB%D1%88%D0%B5%D0%B1%D0%BD%D1%8B%D0%B5_%D1%81%D1%81%D1%8B%D0%BB%D0%BA%D0%B8_ISBN" title="Категория:Страницы, использующие волшебные ссылки ISBN">Страницы, использующие волшебные ссылки ISBN</a></li></ul></div></div> </div> </div> <div id="mw-navigation"> <h2>Навигация</h2> <div id="mw-head"> <nav id="p-personal" class="mw-portlet mw-portlet-personal vector-user-menu-legacy vector-menu" aria-labelledby="p-personal-label" > <h3 id="p-personal-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Персональные инструменты</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anonuserpage" class="mw-list-item"><span title="Страница участника для моего IP">Вы не представились системе</span></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9C%D0%BE%D1%91_%D0%BE%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5" title="Страница обсуждений для моего IP [n]" accesskey="n"><span>Обсуждение</span></a></li><li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9C%D0%BE%D0%B9_%D0%B2%D0%BA%D0%BB%D0%B0%D0%B4" title="Список правок, сделанных с этого IP-адреса [y]" accesskey="y"><span>Вклад</span></a></li><li id="pt-createaccount" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%BE%D0%B7%D0%B4%D0%B0%D1%82%D1%8C_%D1%83%D1%87%D1%91%D1%82%D0%BD%D1%83%D1%8E_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C&returnto=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F+%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0" title="Мы предлагаем вам создать учётную запись и войти в систему, хотя это и не обязательно."><span>Создать учётную запись</span></a></li><li id="pt-login" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%92%D1%85%D0%BE%D0%B4&returnto=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F+%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0" title="Здесь можно зарегистрироваться в системе, но это необязательно. [o]" accesskey="o"><span>Войти</span></a></li> </ul> </div> </nav> <div id="left-navigation"> <nav id="p-namespaces" class="mw-portlet mw-portlet-namespaces vector-menu-tabs vector-menu-tabs-legacy vector-menu" aria-labelledby="p-namespaces-label" > <h3 id="p-namespaces-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Пространства имён</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected mw-list-item"><a href="/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0" title="Просмотреть контентную страницу [c]" accesskey="c"><span>Статья</span></a></li><li id="ca-talk" class="mw-list-item"><a href="/wiki/%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0" rel="discussion" title="Обсуждение основной страницы [t]" accesskey="t"><span>Обсуждение</span></a></li> </ul> </div> </nav> <nav id="p-variants" class="mw-portlet mw-portlet-variants emptyPortlet vector-menu-dropdown vector-menu" aria-labelledby="p-variants-label" > <input type="checkbox" id="p-variants-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-variants" class="vector-menu-checkbox" aria-labelledby="p-variants-label" > <label id="p-variants-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">русский</span> </label> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </nav> </div> <div id="right-navigation"> <nav id="p-views" class="mw-portlet mw-portlet-views vector-menu-tabs vector-menu-tabs-legacy vector-menu" aria-labelledby="p-views-label" > <h3 id="p-views-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Просмотры</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="mw-list-item"><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&stable=1"><span>Читать</span></a></li><li id="ca-current" class="collapsible selected mw-list-item"><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&stable=0&redirect=no" title="Показать текущую версию этой страницы [v]" accesskey="v"><span>Текущая версия</span></a></li><li id="ca-ve-edit" class="mw-list-item"><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&veaction=edit" title="Редактировать данную страницу [v]" accesskey="v"><span>Править</span></a></li><li id="ca-edit" class="collapsible mw-list-item"><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=edit" title="Править исходный текст этой страницы [e]" accesskey="e"><span>Править код</span></a></li><li id="ca-history" class="mw-list-item"><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=history" title="Журнал изменений страницы [h]" accesskey="h"><span>История</span></a></li> </ul> </div> </nav> <nav id="p-cactions" class="mw-portlet mw-portlet-cactions emptyPortlet vector-menu-dropdown vector-menu" aria-labelledby="p-cactions-label" title="Больше возможностей" > <input type="checkbox" id="p-cactions-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-cactions" class="vector-menu-checkbox" aria-labelledby="p-cactions-label" > <label id="p-cactions-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Ещё</span> </label> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </nav> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <h3 >Поиск</h3> <form action="/w/index.php" id="searchform" class="vector-search-box-form"> <div id="simpleSearch" class="vector-search-box-inner" data-search-loc="header-navigation"> <input class="vector-search-box-input" type="search" name="search" placeholder="Искать в Википедии" aria-label="Искать в Википедии" autocapitalize="sentences" title="Искать в Википедии [f]" accesskey="f" id="searchInput" > <input type="hidden" name="title" value="Служебная:Поиск"> <input id="mw-searchButton" class="searchButton mw-fallbackSearchButton" type="submit" name="fulltext" title="Найти страницы, содержащие указанный текст" value="Найти"> <input id="searchButton" class="searchButton" type="submit" name="go" title="Перейти к странице, имеющей в точности такое название" value="Перейти"> </div> </form> </div> </div> </div> <div id="mw-panel" class="vector-legacy-sidebar"> <div id="p-logo" role="banner"> <a class="mw-wiki-logo" href="/wiki/%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0" title="Перейти на заглавную страницу"></a> </div> <nav id="p-navigation" class="mw-portlet mw-portlet-navigation vector-menu-portal portal vector-menu" aria-labelledby="p-navigation-label" > <h3 id="p-navigation-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Навигация</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0" title="Перейти на заглавную страницу [z]" accesskey="z"><span>Заглавная страница</span></a></li><li id="n-content" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BE%D0%B4%D0%B5%D1%80%D0%B6%D0%B0%D0%BD%D0%B8%D0%B5"><span>Содержание</span></a></li><li id="n-featured" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%98%D0%B7%D0%B1%D1%80%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8" title="Статьи, считающиеся лучшими статьями проекта"><span>Избранные статьи</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0" title="Посмотреть случайно выбранную страницу [x]" accesskey="x"><span>Случайная статья</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/%D0%9F%D0%BE%D1%80%D1%82%D0%B0%D0%BB:%D0%A2%D0%B5%D0%BA%D1%83%D1%89%D0%B8%D0%B5_%D1%81%D0%BE%D0%B1%D1%8B%D1%82%D0%B8%D1%8F" title="Статьи о текущих событиях в мире"><span>Текущие события</span></a></li><li id="n-sitesupport" class="mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=ru.wikipedia.org&uselang=ru" title="Поддержите нас"><span>Пожертвовать</span></a></li> </ul> </div> </nav> <nav id="p-participation" class="mw-portlet mw-portlet-participation vector-menu-portal portal vector-menu" aria-labelledby="p-participation-label" > <h3 id="p-participation-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Участие</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-bug_in_article" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BE%D0%BE%D0%B1%D1%89%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%B1_%D0%BE%D1%88%D0%B8%D0%B1%D0%BA%D0%B0%D1%85" title="Сообщить об ошибке в этой статье"><span>Сообщить об ошибке</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B0:%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5"><span>Как править статьи</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BE%D0%BE%D0%B1%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%BE" title="О проекте, о том, чем здесь можно заниматься, а также — где что находится"><span>Сообщество</span></a></li><li id="n-forum" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A4%D0%BE%D1%80%D1%83%D0%BC" title="Форум участников Википедии"><span>Форум</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B0" title="Место расположения Справки"><span>Справка</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%B2%D0%B5%D0%B6%D0%B8%D0%B5_%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B8" title="Список последних изменений [r]" accesskey="r"><span>Свежие правки</span></a></li><li id="n-newpages" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9D%D0%BE%D0%B2%D1%8B%D0%B5_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B" title="Список недавно созданных страниц"><span>Новые страницы</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%BF%D0%B5%D1%86%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B"><span>Служебные страницы</span></a></li> </ul> </div> </nav> <nav id="p-tb" class="mw-portlet mw-portlet-tb vector-menu-portal portal vector-menu" aria-labelledby="p-tb-label" > <h3 id="p-tb-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Инструменты</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D1%81%D1%8B%D0%BB%D0%BA%D0%B8_%D1%81%D1%8E%D0%B4%D0%B0/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0" title="Список всех страниц, ссылающихся на данную [j]" accesskey="j"><span>Ссылки сюда</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%B2%D1%8F%D0%B7%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B8/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0" rel="nofollow" title="Последние изменения в страницах, на которые ссылается эта страница [k]" accesskey="k"><span>Связанные правки</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&oldid=139421010" title="Постоянная ссылка на эту версию страницы"><span>Постоянная ссылка</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=info" title="Подробнее об этой странице"><span>Сведения о странице</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A6%D0%B8%D1%82%D0%B0%D1%82%D0%B0&page=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&id=139421010&wpFormIdentifier=titleform" title="Информация о том, как цитировать эту страницу"><span>Цитировать страницу</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:UrlShortener&url=https%3A%2F%2Fru.wikipedia.org%2Fwiki%2FNP-%25D0%25BF%25D0%25BE%25D0%25BB%25D0%25BD%25D0%25B0%25D1%258F_%25D0%25B7%25D0%25B0%25D0%25B4%25D0%25B0%25D1%2587%25D0%25B0"><span>Получить короткий URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:QrCode&url=https%3A%2F%2Fru.wikipedia.org%2Fwiki%2FNP-%25D0%25BF%25D0%25BE%25D0%25BB%25D0%25BD%25D0%25B0%25D1%258F_%25D0%25B7%25D0%25B0%25D0%25B4%25D0%25B0%25D1%2587%25D0%25B0"><span>Скачать QR-код</span></a></li> </ul> </div> </nav> <nav id="p-coll-print_export" class="mw-portlet mw-portlet-coll-print_export vector-menu-portal portal vector-menu" aria-labelledby="p-coll-print_export-label" > <h3 id="p-coll-print_export-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Печать/экспорт</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:DownloadAsPdf&page=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&action=show-download-screen" title="Скачать эту страницу как файл PDF"><span>Скачать как PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&printable=yes" title="Версия этой страницы для печати [p]" accesskey="p"><span>Версия для печати</span></a></li> </ul> </div> </nav> <nav id="p-wikibase-otherprojects" class="mw-portlet mw-portlet-wikibase-otherprojects vector-menu-portal portal vector-menu" aria-labelledby="p-wikibase-otherprojects-label" > <h3 id="p-wikibase-otherprojects-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">В других проектах</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:NP-complete_problems" hreflang="en"><span>Викисклад</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q215206" title="Ссылка на связанный элемент репозитория данных [g]" accesskey="g"><span>Элемент Викиданных</span></a></li> </ul> </div> </nav> <nav id="p-lang" class="mw-portlet mw-portlet-lang vector-menu-portal portal vector-menu" aria-labelledby="p-lang-label" > <h3 id="p-lang-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">На других языках</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D9%83%D8%AB%D9%8A%D8%B1%D8%A9_%D8%AD%D8%AF%D9%88%D8%AF_%D8%BA%D9%8A%D8%B1_%D9%82%D8%B7%D8%B9%D9%8A%D8%A9_%D9%83%D8%A7%D9%85%D9%84%D8%A9" title="مسألة كثيرة حدود غير قطعية كاملة — арабский" lang="ar" hreflang="ar" data-title="مسألة كثيرة حدود غير قطعية كاملة" data-language-autonym="العربية" data-language-local-name="арабский" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/NP-tam_m%C9%99s%C9%99l%C9%99" title="NP-tam məsələ — азербайджанский" lang="az" hreflang="az" data-title="NP-tam məsələ" data-language-autonym="Azərbaycanca" data-language-local-name="азербайджанский" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/NP-complet" title="NP-complet — каталанский" lang="ca" hreflang="ca" data-title="NP-complet" data-language-autonym="Català" data-language-local-name="каталанский" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/NP-%C3%BAplnost" title="NP-úplnost — чешский" lang="cs" hreflang="cs" data-title="NP-úplnost" data-language-autonym="Čeština" data-language-local-name="чешский" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/NP-komplet" title="NP-komplet — датский" lang="da" hreflang="da" data-title="NP-komplet" data-language-autonym="Dansk" data-language-local-name="датский" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit — немецкий" lang="de" hreflang="de" data-title="NP-Vollständigkeit" data-language-autonym="Deutsch" data-language-local-name="немецкий" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/NP-completeness" title="NP-completeness — греческий" lang="el" hreflang="el" data-title="NP-completeness" data-language-autonym="Ελληνικά" data-language-local-name="греческий" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/NP-completeness" title="NP-completeness — английский" lang="en" hreflang="en" data-title="NP-completeness" data-language-autonym="English" data-language-local-name="английский" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/NP-completo" title="NP-completo — испанский" lang="es" hreflang="es" data-title="NP-completo" data-language-autonym="Español" data-language-local-name="испанский" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%A7%D9%86%E2%80%8C%D9%BE%DB%8C_%DA%A9%D8%A7%D9%85%D9%84" title="ان‌پی کامل — персидский" lang="fa" hreflang="fa" data-title="ان‌پی کامل" data-language-autonym="فارسی" data-language-local-name="персидский" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/NP-t%C3%A4ydellisyys" title="NP-täydellisyys — финский" lang="fi" hreflang="fi" data-title="NP-täydellisyys" data-language-autonym="Suomi" data-language-local-name="финский" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Probl%C3%A8me_NP-complet" title="Problème NP-complet — французский" lang="fr" hreflang="fr" data-title="Problème NP-complet" data-language-autonym="Français" data-language-local-name="французский" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/NP-completo" title="NP-completo — итальянский" lang="it" hreflang="it" data-title="NP-completo" data-language-autonym="Italiano" data-language-local-name="итальянский" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/NP%E5%AE%8C%E5%85%A8%E5%95%8F%E9%A1%8C" title="NP完全問題 — японский" lang="ja" hreflang="ja" data-title="NP完全問題" data-language-autonym="日本語" data-language-local-name="японский" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/NP-%EC%99%84%EC%A0%84" title="NP-완전 — корейский" lang="ko" hreflang="ko" data-title="NP-완전" data-language-autonym="한국어" data-language-local-name="корейский" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/NP-volledig" title="NP-volledig — нидерландский" lang="nl" hreflang="nl" data-title="NP-volledig" data-language-autonym="Nederlands" data-language-local-name="нидерландский" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-nn mw-list-item"><a href="https://nn.wikipedia.org/wiki/NP-komplett" title="NP-komplett — нюнорск" lang="nn" hreflang="nn" data-title="NP-komplett" data-language-autonym="Norsk nynorsk" data-language-local-name="нюнорск" class="interlanguage-link-target"><span>Norsk nynorsk</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/NP-komplett" title="NP-komplett — норвежский букмол" lang="nb" hreflang="nb" data-title="NP-komplett" data-language-autonym="Norsk bokmål" data-language-local-name="норвежский букмол" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Problem_NP-zupe%C5%82ny" title="Problem NP-zupełny — польский" lang="pl" hreflang="pl" data-title="Problem NP-zupełny" data-language-autonym="Polski" data-language-local-name="польский" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/NP-completo" title="NP-completo — португальский" lang="pt" hreflang="pt" data-title="NP-completo" data-language-autonym="Português" data-language-local-name="португальский" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/NP-completitudine" title="NP-completitudine — румынский" lang="ro" hreflang="ro" data-title="NP-completitudine" data-language-autonym="Română" data-language-local-name="румынский" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/NP-kompletni_problemi" title="NP-kompletni problemi — сербскохорватский" lang="sh" hreflang="sh" data-title="NP-kompletni problemi" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="сербскохорватский" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/NP-complete" title="NP-complete — Simple English" lang="en-simple" hreflang="en-simple" data-title="NP-complete" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/NP-%C3%BApln%C3%BD_probl%C3%A9m" title="NP-úplný problém — словацкий" lang="sk" hreflang="sk" data-title="NP-úplný problém" data-language-autonym="Slovenčina" data-language-local-name="словацкий" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%9D%D0%9F-%D0%BA%D0%BE%D0%BC%D0%BF%D0%BB%D0%B5%D1%82%D0%BD%D0%B8_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B8" title="НП-комплетни проблеми — сербский" lang="sr" hreflang="sr" data-title="НП-комплетни проблеми" data-language-autonym="Српски / srpski" data-language-local-name="сербский" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/NP-fullst%C3%A4ndig" title="NP-fullständig — шведский" lang="sv" hreflang="sv" data-title="NP-fullständig" data-language-autonym="Svenska" data-language-local-name="шведский" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B9%80%E0%B8%AD%E0%B9%87%E0%B8%99%E0%B8%9E%E0%B8%B5%E0%B8%9A%E0%B8%A3%E0%B8%B4%E0%B8%9A%E0%B8%B9%E0%B8%A3%E0%B8%93%E0%B9%8C" title="เอ็นพีบริบูรณ์ — тайский" lang="th" hreflang="th" data-title="เอ็นพีบริบูรณ์" data-language-autonym="ไทย" data-language-local-name="тайский" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/NP-tam" title="NP-tam — турецкий" lang="tr" hreflang="tr" data-title="NP-tam" data-language-autonym="Türkçe" data-language-local-name="турецкий" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%B2%D0%BD%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0" title="NP-повна задача — украинский" lang="uk" hreflang="uk" data-title="NP-повна задача" data-language-autonym="Українська" data-language-local-name="украинский" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/NP-%C4%91%E1%BA%A7y_%C4%91%E1%BB%A7" title="NP-đầy đủ — вьетнамский" lang="vi" hreflang="vi" data-title="NP-đầy đủ" data-language-autonym="Tiếng Việt" data-language-local-name="вьетнамский" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/NP%E5%AE%8C%E5%85%A8" title="NP完全 — китайский" lang="zh" hreflang="zh" data-title="NP完全" data-language-autonym="中文" data-language-local-name="китайский" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q215206#sitelinks-wikipedia" title="Править ссылки на другие языки" class="wbc-editpage">Править ссылки</a></span></div> </div> </nav> </div> </div> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> Эта страница в последний раз была отредактирована 4 августа 2024 в 23:43.</li> <li id="footer-info-copyright">Текст доступен по <a rel="nofollow" class="external text" href="//creativecommons.org/licenses/by-sa/4.0/deed.ru">лицензии Creative Commons «С указанием авторства — С сохранением условий» (CC BY-SA)</a>; в отдельных случаях могут действовать дополнительные условия. <span class="noprint">Подробнее см. <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/ru">Условия использования</a>.</span><br /> Wikipedia® — зарегистрированный товарный знак некоммерческой организации <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/ru/">«Фонд Викимедиа» (Wikimedia Foundation, Inc.)</a></li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/ru">Политика конфиденциальности</a></li> <li id="footer-places-about"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9E%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B5">Описание Википедии</a></li> <li id="footer-places-disclaimers"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9E%D1%82%D0%BA%D0%B0%D0%B7_%D0%BE%D1%82_%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%BE%D1%81%D1%82%D0%B8">Отказ от ответственности</a></li> <li id="footer-places-contact"><a href="//ru.wikipedia.org/wiki/Википедия:Контакты">Свяжитесь с нами</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Policy:Universal_Code_of_Conduct/ru">Кодекс поведения</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Разработчики</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/ru.wikipedia.org">Статистика</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Заявление о куки</a></li> <li id="footer-places-mobileview"><a href="//ru.m.wikipedia.org/w/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Мобильная версия</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" lang="en" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> <div class="mw-portlet mw-portlet-dock-bottom emptyPortlet vector-menu-portal portal" id="p-dock-bottom"> <ul> </ul> </div> <script>(RLQ=window.RLQ||[]).push(function(){mw.log.warn("This page is using the deprecated ResourceLoader module \"codex-search-styles\".\n[1.43] Use a CodexModule with codexComponents to set your specific components used: https://www.mediawiki.org/wiki/Codex#Using_a_limited_subset_of_components");mw.config.set({"wgHostname":"mw-web.codfw.main-76d4c66f66-7k4hn","wgBackendResponseTime":145,"wgPageParseReport":{"limitreport":{"cputime":"0.374","walltime":"0.642","ppvisitednodes":{"value":3355,"limit":1000000},"postexpandincludesize":{"value":81931,"limit":2097152},"templateargumentsize":{"value":3132,"limit":2097152},"expansiondepth":{"value":16,"limit":100},"expensivefunctioncount":{"value":33,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":14548,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 396.933 1 -total"," 40.42% 160.422 1 Шаблон:Примечания"," 20.74% 82.325 1 Шаблон:Cite_journal"," 16.73% 66.391 1 Шаблон:Статья"," 16.25% 64.504 1 Шаблон:Нет_АИ"," 16.18% 64.235 2 Шаблон:Навигационная_таблица"," 16.11% 63.927 1 Шаблон:Классы_сложности"," 11.98% 47.552 3 Шаблон:Бсокр"," 11.87% 47.115 26 Шаблон:Нп1"," 7.56% 29.994 2 Шаблон:Main"]},"scribunto":{"limitreport-timeusage":{"value":"0.156","limit":"10.000"},"limitreport-memusage":{"value":5649616,"limit":52428800}},"cachereport":{"origin":"mw-api-int.codfw.main-5f44755944-dcmrh","timestamp":"20250302131109","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"NP-\u043f\u043e\u043b\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430","url":"https:\/\/ru.wikipedia.org\/wiki\/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0","sameAs":"http:\/\/www.wikidata.org\/entity\/Q215206","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q215206","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"\u0424\u043e\u043d\u0434 \u0412\u0438\u043a\u0438\u043c\u0435\u0434\u0438\u0430","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2006-03-05T10:44:32Z","dateModified":"2024-08-04T23:43:54Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/a\/a0\/P_np_np-complete_np-hard.svg","headline":"\u0442\u0438\u043f \u0437\u0430\u0434\u0430\u0447 \u0432 \u0442\u0435\u043e\u0440\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432"}</script> </body> </html>