CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>NP-completeness - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);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":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"1631421e-4728-4d82-b7ff-2b2df44163e0","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"NP-completeness","wgTitle":"NP-completeness","wgCurRevisionId":1257002113,"wgRevisionId":1257002113,"wgArticleId":23385892,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Webarchive template wayback links","Articles with short description","Short description matches Wikidata","Wikipedia articles needing clarification from July 2012","All Wikipedia articles needing clarification","All articles with unsourced statements","Articles with unsourced statements from October 2022","Articles with unsourced statements from August 2024","All articles needing examples","Articles needing examples from April 2023","1971 in computing","NP-complete problems", "Complexity classes","Mathematical optimization"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"NP-completeness","wgRelevantArticleId":23385892,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgRedirectedFrom":"NP-complete","wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgInternalRedirectTargetUrl":"/wiki/NP-completeness","wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage", "wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q215206","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"}; RLPAGEMODULES=["mediawiki.action.view.redirect","ext.cite.ux-enhancements","mediawiki.page.media","ext.scribunto.logs","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","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.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</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=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <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/6/69/3SAT_17_svg.svg/1200px-3SAT_17_svg.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="481"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/6/69/3SAT_17_svg.svg/800px-3SAT_17_svg.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="321"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/6/69/3SAT_17_svg.svg/640px-3SAT_17_svg.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="257"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="NP-completeness - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/NP-completeness"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=NP-completeness&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="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/NP-completeness"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-NP-completeness rootpage-NP-completeness skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=NP-completeness" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=NP-completeness" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=NP-completeness" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=NP-completeness" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Overview" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Overview"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Overview</span> </div> </a> <ul id="toc-Overview-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Formal_definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Formal_definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Formal definition</span> </div> </a> <ul id="toc-Formal_definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Background" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Background"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Background</span> </div> </a> <ul id="toc-Background-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-NP-complete_problems" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#NP-complete_problems"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>NP-complete problems</span> </div> </a> <button aria-controls="toc-NP-complete_problems-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle NP-complete problems subsection</span> </button> <ul id="toc-NP-complete_problems-sublist" class="vector-toc-list"> <li id="toc-Intermediate_problems" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Intermediate_problems"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Intermediate problems</span> </div> </a> <ul id="toc-Intermediate_problems-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Solving_NP-complete_problems" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Solving_NP-complete_problems"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Solving NP-complete problems</span> </div> </a> <ul id="toc-Solving_NP-complete_problems-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Completeness_under_different_types_of_reduction" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Completeness_under_different_types_of_reduction"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Completeness under different types of reduction</span> </div> </a> <ul id="toc-Completeness_under_different_types_of_reduction-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Naming" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Naming"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Naming</span> </div> </a> <ul id="toc-Naming-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Common_misconceptions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Common_misconceptions"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Common misconceptions</span> </div> </a> <ul id="toc-Common_misconceptions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Properties" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>Properties</span> </div> </a> <ul id="toc-Properties-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>References</span> </div> </a> <button aria-controls="toc-References-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle References subsection</span> </button> <ul id="toc-References-sublist" class="vector-toc-list"> <li id="toc-Citations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Citations"> <div class="vector-toc-text"> <span class="vector-toc-numb">11.1</span> <span>Citations</span> </div> </a> <ul id="toc-Citations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Sources" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Sources"> <div class="vector-toc-text"> <span class="vector-toc-numb">11.2</span> <span>Sources</span> </div> </a> <ul id="toc-Sources-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Further_reading" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Further_reading"> <div class="vector-toc-text"> <span class="vector-toc-numb">12</span> <span>Further reading</span> </div> </a> <ul id="toc-Further_reading-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">NP-completeness</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 31 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-31" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">31 languages</span> </label> <div class="vector-dropdown-content"> <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="مسألة كثيرة حدود غير قطعية كاملة – Arabic" lang="ar" hreflang="ar" data-title="مسألة كثيرة حدود غير قطعية كاملة" data-language-autonym="العربية" data-language-local-name="Arabic" 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ə – Azerbaijani" lang="az" hreflang="az" data-title="NP-tam məsələ" data-language-autonym="Azərbaycanca" data-language-local-name="Azerbaijani" 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 – Catalan" lang="ca" hreflang="ca" data-title="NP-complet" data-language-autonym="Català" data-language-local-name="Catalan" 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 – Czech" lang="cs" hreflang="cs" data-title="NP-úplnost" data-language-autonym="Čeština" data-language-local-name="Czech" 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 – Danish" lang="da" hreflang="da" data-title="NP-komplet" data-language-autonym="Dansk" data-language-local-name="Danish" 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 – German" lang="de" hreflang="de" data-title="NP-Vollständigkeit" data-language-autonym="Deutsch" data-language-local-name="German" 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 – Greek" lang="el" hreflang="el" data-title="NP-completeness" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/NP-completo" title="NP-completo – Spanish" lang="es" hreflang="es" data-title="NP-completo" data-language-autonym="Español" data-language-local-name="Spanish" 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="ان‌پی کامل – Persian" lang="fa" hreflang="fa" data-title="ان‌پی کامل" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</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 – French" lang="fr" hreflang="fr" data-title="Problème NP-complet" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</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-완전 – Korean" lang="ko" hreflang="ko" data-title="NP-완전" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/NP-completo" title="NP-completo – Italian" lang="it" hreflang="it" data-title="NP-completo" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/NP-volledig" title="NP-volledig – Dutch" lang="nl" hreflang="nl" data-title="NP-volledig" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</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完全問題 – Japanese" lang="ja" hreflang="ja" data-title="NP完全問題" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/NP-komplett" title="NP-komplett – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="NP-komplett" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-nn mw-list-item"><a href="https://nn.wikipedia.org/wiki/NP-komplett" title="NP-komplett – Norwegian Nynorsk" lang="nn" hreflang="nn" data-title="NP-komplett" data-language-autonym="Norsk nynorsk" data-language-local-name="Norwegian Nynorsk" class="interlanguage-link-target"><span>Norsk nynorsk</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 – Polish" lang="pl" hreflang="pl" data-title="Problem NP-zupełny" data-language-autonym="Polski" data-language-local-name="Polish" 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 – Portuguese" lang="pt" hreflang="pt" data-title="NP-completo" data-language-autonym="Português" data-language-local-name="Portuguese" 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 – Romanian" lang="ro" hreflang="ro" data-title="NP-completitudine" data-language-autonym="Română" data-language-local-name="Romanian" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a 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" title="NP-полная задача – Russian" lang="ru" hreflang="ru" data-title="NP-полная задача" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</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 – Slovak" lang="sk" hreflang="sk" data-title="NP-úplný problém" data-language-autonym="Slovenčina" data-language-local-name="Slovak" 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="НП-комплетни проблеми – Serbian" lang="sr" hreflang="sr" data-title="НП-комплетни проблеми" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</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 – Serbo-Croatian" lang="sh" hreflang="sh" data-title="NP-kompletni problemi" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Serbo-Croatian" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</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 – Finnish" lang="fi" hreflang="fi" data-title="NP-täydellisyys" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</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 – Swedish" lang="sv" hreflang="sv" data-title="NP-fullständig" data-language-autonym="Svenska" data-language-local-name="Swedish" 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="เอ็นพีบริบูรณ์ – Thai" lang="th" hreflang="th" data-title="เอ็นพีบริบูรณ์" data-language-autonym="ไทย" data-language-local-name="Thai" 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 – Turkish" lang="tr" hreflang="tr" data-title="NP-tam" data-language-autonym="Türkçe" data-language-local-name="Turkish" 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-повна задача – Ukrainian" lang="uk" hreflang="uk" data-title="NP-повна задача" data-language-autonym="Українська" data-language-local-name="Ukrainian" 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 đủ – Vietnamese" lang="vi" hreflang="vi" data-title="NP-đầy đủ" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" 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完全 – Chinese" lang="zh" hreflang="zh" data-title="NP完全" data-language-autonym="中文" data-language-local-name="Chinese" 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="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/NP-completeness" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:NP-completeness" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/NP-completeness"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=NP-completeness&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=NP-completeness&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/NP-completeness"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=NP-completeness&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=NP-completeness&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/NP-completeness" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/NP-completeness" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=NP-completeness&oldid=1257002113" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=NP-completeness&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=NP-completeness&id=1257002113&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FNP-completeness"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FNP-completeness"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <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=Special:DownloadAsPdf&page=NP-completeness&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=NP-completeness&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <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>Wikimedia Commons</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="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"><span class="mw-redirectedfrom">(Redirected from <a href="/w/index.php?title=NP-complete&redirect=no" class="mw-redirect" title="NP-complete">NP-complete</a>)</span></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Complexity class</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-Confusing plainlinks metadata ambox ambox-style ambox-confusing" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>may be <a href="/wiki/Wikipedia:Vagueness" title="Wikipedia:Vagueness">confusing or unclear</a> to readers</b>.<span class="hide-when-compact"> Please help <a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify">clarify the article</a>. There might be a discussion about this on <a href="/wiki/Talk:NP-completeness" title="Talk:NP-completeness">the talk page</a>.</span> <span class="date-container"><i>(<span class="date">July 2012</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <figure typeof="mw:File/Thumb"><a href="/wiki/File:3SAT_17_svg.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/69/3SAT_17_svg.svg/400px-3SAT_17_svg.svg.png" decoding="async" width="400" height="160" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/69/3SAT_17_svg.svg/600px-3SAT_17_svg.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/69/3SAT_17_svg.svg/800px-3SAT_17_svg.svg.png 2x" data-file-width="354" data-file-height="142" /></a><figcaption>The <a href="/wiki/Boolean_satisfiability_problem" title="Boolean satisfiability problem">Boolean satisfiability problem</a> (SAT) asks to determine if a <a href="/wiki/Propositional_formula" title="Propositional formula">propositional formula</a> (example depicted) can be made <i>true</i> by an appropriate assignment ("solution") of truth values to its variables. While it is easy to verify whether a given assignment renders the formula <i>true</i>,<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> no essentially faster method to find a satisfying assignment is known than to try all assignments in succession. <a href="/wiki/Stephen_Cook" title="Stephen Cook">Cook</a> and <a href="/wiki/Leonid_Levin" title="Leonid Levin">Levin</a> proved that each easy-to-verify problem can be solved as fast as SAT, which is hence NP-complete.</figcaption></figure> <p>In <a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, a problem is <b>NP-complete</b> when: </p> <ol><li>It is a <a href="/wiki/Decision_problem" title="Decision problem">decision problem</a>, meaning that for any input to the problem, the output is either "yes" or "no".</li> <li>When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) <i>solution</i>.</li> <li>The correctness of each solution can be verified quickly (namely, in <a href="/wiki/Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>) and a <a href="/wiki/Brute-force_search" title="Brute-force search">brute-force search</a> algorithm can find a solution by trying all possible solutions.</li> <li>The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.</li></ol> <p>The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to <a href="/wiki/Nondeterministic_Turing_machine" title="Nondeterministic Turing machine">nondeterministic Turing machines</a>, a way of mathematically formalizing the idea of a brute-force search algorithm. <a href="/wiki/Polynomial_time" class="mw-redirect" title="Polynomial time">Polynomial time</a> refers to an amount of time that is considered "quick" for a <a href="/wiki/Deterministic_algorithm" title="Deterministic algorithm">deterministic algorithm</a> to check a single solution, or for a nondeterministic Turing machine to perform the whole search. "<a href="/wiki/Complete_(complexity)" title="Complete (complexity)">Complete</a>" refers to the property of being able to simulate everything in the same <a href="/wiki/Complexity_class" title="Complexity class">complexity class</a>. </p><p>More precisely, each input to the problem should be associated with a set of solutions of polynomial length, the validity of each of which can be tested quickly (in <a href="/wiki/Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</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> such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called <a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a>, an abbreviation for "nondeterministic polynomial time". A problem is said to be <a href="/wiki/NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> if everything in NP can be transformed in polynomial time into it even though it may not be in NP. A problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If some NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by <b>NP-C</b> or <b>NPC</b>. </p><p>Although a solution to an NP-complete problem can be <i>verified</i> "quickly", there is no known way to <i>find</i> a solution quickly. That is, the time required to solve the problem using any currently known <a href="/wiki/Algorithm" title="Algorithm">algorithm</a> increases rapidly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the <a href="/wiki/P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a>, is one of the fundamental <a href="/wiki/List_of_open_problems_in_computer_science" class="mw-redirect" title="List of open problems in computer science">unsolved problems in computer science</a> today. </p><p>While a method for computing the solutions to NP-complete problems quickly remains undiscovered, <a href="/wiki/Computer_scientist" title="Computer scientist">computer scientists</a> and <a href="/wiki/Computer_programmer" class="mw-redirect" title="Computer programmer">programmers</a> still frequently encounter NP-complete problems. NP-complete problems are often addressed by using <a href="/wiki/Heuristic_(computer_science)" title="Heuristic (computer science)">heuristic</a> methods and <a href="/wiki/Approximation_algorithm" title="Approximation algorithm">approximation algorithms</a>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=1" title="Edit section: Overview"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>NP-complete problems are in <a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a>, the set of all <a href="/wiki/Decision_problem" title="Decision problem">decision problems</a> whose solutions can be verified in polynomial time; <i>NP</i> may be equivalently defined as the set of decision problems that can be solved in polynomial time on a <a href="/wiki/Non-deterministic_Turing_machine" class="mw-redirect" title="Non-deterministic Turing machine">non-deterministic Turing machine</a>. A problem <i>p</i> in NP is NP-complete if every other problem in NP can be transformed (or reduced) into <i>p</i> in polynomial time.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (October 2022)">citation needed</span></a></i>]</sup> </p><p>It is not known whether every problem in NP can be quickly solved—this is called the <a href="/wiki/P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a>. But if <i>any NP-complete problem</i> can be solved quickly, then <i>every problem in NP</i> can, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every NP-complete problem (that is, it can be reduced in polynomial time). Because of this, it is often said that NP-complete problems are <i>harder</i> or <i>more difficult</i> than NP problems in general.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (October 2022)">citation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=2" title="Edit section: Formal definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/P_%3D_NP_problem#NP-completeness" class="mw-redirect" title="P = NP problem">formal definition for NP-completeness (article <i>P = NP</i>)</a></div> <p>A decision problem <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 \scriptstyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb065b175e96fd6b2519350ac89fc99fa786c882" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.249ex; height:1.676ex;" alt="{\displaystyle \scriptstyle C}"></span> is NP-complete if:<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (October 2022)">citation needed</span></a></i>]</sup> </p> <ol><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 \scriptstyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb065b175e96fd6b2519350ac89fc99fa786c882" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.249ex; height:1.676ex;" alt="{\displaystyle \scriptstyle C}"></span> is in NP, and</li> <li>Every problem in NP is <a href="/wiki/Many-one_reduction" title="Many-one reduction">reducible</a> to <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 \scriptstyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb065b175e96fd6b2519350ac89fc99fa786c882" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.249ex; height:1.676ex;" alt="{\displaystyle \scriptstyle C}"></span> in polynomial time.<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></ol> <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 \scriptstyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb065b175e96fd6b2519350ac89fc99fa786c882" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.249ex; height:1.676ex;" alt="{\displaystyle \scriptstyle C}"></span> can be shown to be in NP by demonstrating that a candidate solution to <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 \scriptstyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb065b175e96fd6b2519350ac89fc99fa786c882" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.249ex; height:1.676ex;" alt="{\displaystyle \scriptstyle C}"></span> can be verified in polynomial time. </p><p>Note that a problem satisfying condition 2 is said to be <a href="/wiki/NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>, whether or not it satisfies condition 1.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p><p>A consequence of this definition is that if we had a polynomial time algorithm (on a <a href="/wiki/Universal_Turing_machine" title="Universal Turing machine">UTM</a>, or any other <a href="/wiki/Turing_completeness" title="Turing completeness">Turing-equivalent</a> <a href="/wiki/Abstract_machine" title="Abstract machine">abstract machine</a>) for <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 \scriptstyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb065b175e96fd6b2519350ac89fc99fa786c882" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.249ex; height:1.676ex;" alt="{\displaystyle \scriptstyle C}"></span>, we could solve all problems in NP in polynomial time. </p> <div class="mw-heading mw-heading2"><h2 id="Background">Background</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=3" title="Edit section: Background"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File: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/300px-P_np_np-complete_np-hard.svg.png" decoding="async" width="300" height="188" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/450px-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/600px-P_np_np-complete_np-hard.svg.png 2x" data-file-width="800" data-file-height="500" /></a><figcaption><a href="/wiki/Euler_diagram" title="Euler diagram">Euler diagram</a> for <a href="/wiki/P_(complexity)" title="P (complexity)">P</a>, <a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a>, NP-complete, and <a href="/wiki/NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> sets of problems. The left side is valid under the assumption that <a href="/wiki/P_versus_NP_problem" title="P versus NP problem">P≠NP</a>, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete, and in general, not every problem in P or NP is NP-complete).</figcaption></figure> <p>The concept of NP-completeness was introduced in 1971 (see <a href="/wiki/Cook%E2%80%93Levin_theorem" title="Cook–Levin theorem">Cook–Levin theorem</a>), though the term <i>NP-complete</i> was introduced later. At the 1971 <a href="/wiki/Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">STOC</a> conference, there was a fierce debate between the computer scientists about whether NP-complete problems could be solved in polynomial time on a <a href="/wiki/Deterministic" class="mw-redirect" title="Deterministic">deterministic</a> <a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a>. <a href="/wiki/John_Hopcroft" title="John Hopcroft">John Hopcroft</a> brought everyone at the conference to a consensus that the question of whether NP-complete problems are solvable in polynomial time should be put off to be solved at some later date, since nobody had any formal proofs for their claims one way or the other.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (August 2024)">citation needed</span></a></i>]</sup> This is known as "the question of whether P=NP". </p><p>Nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great <a href="/wiki/Unsolved_problems_of_mathematics" class="mw-redirect" title="Unsolved problems of mathematics">unsolved problems of mathematics</a>. The <a href="/wiki/Clay_Mathematics_Institute" title="Clay Mathematics Institute">Clay Mathematics Institute</a> is offering a US$1 million reward (<a href="/wiki/Millennium_Prize_Problems" title="Millennium Prize Problems">Millennium Prize</a>) to anyone who has a formal proof that P=NP or that P≠NP.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p><p>The existence of NP-complete problems is not obvious. The <a href="/wiki/Cook%E2%80%93Levin_theorem" title="Cook–Levin theorem">Cook–Levin theorem</a> states that the <a href="/wiki/Boolean_satisfiability_problem" title="Boolean satisfiability problem">Boolean satisfiability problem</a> is NP-complete, thus establishing that such problems do exist. In 1972, <a href="/wiki/Richard_Karp" class="mw-redirect" title="Richard Karp">Richard Karp</a> proved that several other problems were also NP-complete (see <a href="/wiki/Karp%27s_21_NP-complete_problems" title="Karp's 21 NP-complete problems">Karp's 21 NP-complete problems</a>); thus, there is a class of NP-complete problems (besides the Boolean satisfiability problem). Since the original results, thousands of other problems have been shown to be NP-complete by reductions from other problems previously shown to be NP-complete; many of these problems are collected in <a href="#CITEREFGareyJohnson1979">Garey & Johnson (1979)</a>. </p> <div class="mw-heading mw-heading2"><h2 id="NP-complete_problems">NP-complete problems</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=4" title="Edit section: NP-complete problems"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Relative_NPC_chart.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/8/89/Relative_NPC_chart.svg/300px-Relative_NPC_chart.svg.png" decoding="async" width="300" height="330" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/89/Relative_NPC_chart.svg/450px-Relative_NPC_chart.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/89/Relative_NPC_chart.svg/600px-Relative_NPC_chart.svg.png 2x" data-file-width="500" data-file-height="550" /></a><figcaption>Some NP-complete problems, indicating the <a href="/wiki/Reduction_(complexity)" title="Reduction (complexity)">reductions</a> typically used to prove their NP-completeness</figcaption></figure> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/List_of_NP-complete_problems" title="List of NP-complete problems">List of NP-complete problems</a></div> <p>The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it. Therefore, it is useful to know a variety of NP-complete problems. The list below contains some well-known problems that are NP-complete when expressed as decision problems. </p> <style data-mw-deduplicate="TemplateStyles:r1184024115">.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}</style><div class="div-col" style="column-width: 25em;"> <ul><li><a href="/wiki/Boolean_satisfiability_problem" title="Boolean satisfiability problem">Boolean satisfiability problem (SAT)</a></li> <li><a href="/wiki/Knapsack_problem" title="Knapsack problem">Knapsack problem</a></li> <li><a href="/wiki/Hamiltonian_path_problem" title="Hamiltonian path problem">Hamiltonian path problem</a></li> <li><a href="/wiki/Travelling_salesman_problem" title="Travelling salesman problem">Travelling salesman problem</a> (decision version)</li> <li><a href="/wiki/Subgraph_isomorphism_problem" title="Subgraph isomorphism problem">Subgraph isomorphism problem</a></li> <li><a href="/wiki/Subset_sum_problem" title="Subset sum problem">Subset sum problem</a></li> <li><a href="/wiki/Clique_problem" title="Clique problem">Clique problem</a></li> <li><a href="/wiki/Vertex_cover_problem" class="mw-redirect" title="Vertex cover problem">Vertex cover problem</a></li> <li><a href="/wiki/Independent_set_problem" class="mw-redirect" title="Independent set problem">Independent set problem</a></li> <li><a href="/wiki/Dominating_set_problem" class="mw-redirect" title="Dominating set problem">Dominating set problem</a></li> <li><a href="/wiki/Graph_coloring_problem" class="mw-redirect" title="Graph coloring problem">Graph coloring problem</a></li> <li><a href="/wiki/Sudoku" title="Sudoku">Sudoku</a></li></ul> </div> <p>To the right is a diagram of some of the problems and the <a href="/wiki/Reduction_(complexity)" title="Reduction (complexity)">reductions</a> typically used to prove their NP-completeness. In this diagram, problems are reduced from bottom to top. Note that this diagram is misleading as a description of the mathematical relationship between these problems, as there exists a <a href="/wiki/Polynomial-time_reduction" title="Polynomial-time reduction">polynomial-time reduction</a> between any two NP-complete problems; but it indicates where demonstrating this polynomial-time reduction has been easiest. </p><p>There is often only a small difference between a problem in P and an NP-complete problem. For example, the <a href="/wiki/3-satisfiability" class="mw-redirect" title="3-satisfiability">3-satisfiability</a> problem, a restriction of the Boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted <a href="/wiki/2-satisfiability" title="2-satisfiability">2-satisfiability</a> problem is in P (specifically, it is <a href="/wiki/NL-complete" title="NL-complete">NL-complete</a>), but the slightly more general max. 2-sat. problem is again NP-complete. Determining whether a graph can be colored with 2 colors is in P, but with 3 colors is NP-complete, even when restricted to <a href="/wiki/Planar_graph" title="Planar graph">planar graphs</a>. Determining if a graph is a <a href="/wiki/Cycle_graph" title="Cycle graph">cycle</a> or is <a href="/wiki/Bipartite_graph" title="Bipartite graph">bipartite</a> is very easy (in <a href="/wiki/L_(complexity)" title="L (complexity)">L</a>), but finding a maximum bipartite or a maximum cycle subgraph is NP-complete. A solution of the <a href="/wiki/Knapsack_problem" title="Knapsack problem">knapsack problem</a> within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NP-complete. </p> <div class="mw-heading mw-heading3"><h3 id="Intermediate_problems">Intermediate problems</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=5" title="Edit section: Intermediate problems"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>An interesting example is the <a href="/wiki/Graph_isomorphism_problem" title="Graph isomorphism problem">graph isomorphism problem</a>, the <a href="/wiki/Graph_theory" title="Graph theory">graph theory</a> problem of determining whether a <a href="/wiki/Graph_isomorphism" title="Graph isomorphism">graph isomorphism</a> exists between two graphs. Two graphs are <a href="/wiki/Isomorphic" class="mw-redirect" title="Isomorphic">isomorphic</a> if one can be <a href="/wiki/Isomorphism" title="Isomorphism">transformed</a> into the other simply by renaming <a href="/wiki/Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a>. Consider these two problems: </p> <ul><li>Graph Isomorphism: Is graph G<sub>1</sub> isomorphic to graph G<sub>2</sub>?</li> <li>Subgraph Isomorphism: Is graph G<sub>1</sub> isomorphic to a subgraph of graph G<sub>2</sub>?</li></ul> <p>The Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete, though it is in NP. This is an example of a problem that is thought to be <i>hard</i>, but is not thought to be NP-complete. This class is called <i>NP-Intermediate problems</i> and exists if and only if P≠NP. </p> <div class="mw-heading mw-heading2"><h2 id="Solving_NP-complete_problems">Solving NP-complete problems</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=6" title="Edit section: Solving NP-complete problems"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>At present, all known algorithms for NP-complete problems require time that is <a href="/wiki/Superpolynomial" class="mw-redirect" title="Superpolynomial">superpolynomial</a> in the input size. The <a href="/wiki/Vertex_cover" title="Vertex cover">vertex cover</a> problem has <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 O(1.2738^{k}+nk)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mn>1.2738</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo>+</mo> <mi>n</mi> <mi>k</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(1.2738^{k}+nk)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2d3e2bc9d14ef1fcfc3fe1da0724c7c4d975834c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.577ex; height:3.176ex;" alt="{\displaystyle O(1.2738^{k}+nk)}"></span><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> for some <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 k>0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>></mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k>0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/27b3af208b148139eefc03f0f80fa94c38c5af45" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k>0}"></span> and it is unknown whether there are any faster algorithms. </p><p>The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms: </p> <ul><li><a href="/wiki/Approximation_algorithm" title="Approximation algorithm">Approximation</a>: Instead of searching for an optimal solution, search for a solution that is at most a factor from an optimal one.</li> <li><a href="/wiki/Randomized_algorithm" title="Randomized algorithm">Randomization</a>: Use randomness to get a faster average <a href="/wiki/Running_time" class="mw-redirect" title="Running time">running time</a>, and allow the algorithm to fail with some small probability. Note: The <a href="/wiki/Monte_Carlo_method" title="Monte Carlo method">Monte Carlo method</a> is not an example of an efficient algorithm in this specific sense, although evolutionary approaches like <a href="/wiki/Genetic_algorithm" title="Genetic algorithm">Genetic algorithms</a> may be.</li> <li>Restriction: By restricting the structure of the input (e.g., to planar graphs), faster algorithms are usually possible.</li> <li><a href="/wiki/Parameterized_complexity" title="Parameterized complexity">Parameterization</a>: Often there are fast algorithms if certain parameters of the input are fixed.</li> <li><a href="/wiki/Heuristic_(computer_science)" title="Heuristic (computer science)">Heuristic</a>: An algorithm that works "reasonably well" in many cases, but for which there is no proof that it is both always fast and always produces a good result. <a href="/wiki/Metaheuristic" title="Metaheuristic">Metaheuristic</a> approaches are often used.</li></ul> <p>One example of a heuristic algorithm is a suboptimal <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 O(n\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}"></span> <a href="/wiki/Greedy_coloring" title="Greedy coloring">greedy coloring algorithm</a> used for <a href="/wiki/Graph_coloring_problem" class="mw-redirect" title="Graph coloring problem">graph coloring</a> during the <a href="/wiki/Register_allocation" title="Register allocation">register allocation</a> phase of some compilers, a technique called <a href="/wiki/Register_allocation#Graph-coloring_allocation" title="Register allocation">graph-coloring global register allocation</a>. Each vertex is a variable, edges are drawn between variables which are being used at the same time, and colors indicate the register assigned to each variable. Because most <a href="/wiki/RISC" class="mw-redirect" title="RISC">RISC</a> machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application. </p> <div class="mw-heading mw-heading2"><h2 id="Completeness_under_different_types_of_reduction">Completeness under different types of reduction</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=7" title="Edit section: Completeness under different types of reduction"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the definition of NP-complete given above, the term <i>reduction</i> was used in the technical meaning of a polynomial-time <a href="/wiki/Many-one_reduction" title="Many-one reduction">many-one reduction</a>. </p><p>Another type of reduction is polynomial-time <a href="/wiki/Turing_reduction" title="Turing reduction">Turing reduction</a>. A problem <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 \scriptstyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mi>X</mi> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b88bfd56b234fcec7137b28c3982a284f776009" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.4ex; height:1.676ex;" alt="{\displaystyle \scriptstyle X}"></span> is polynomial-time Turing-reducible to a problem <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 \scriptstyle Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mi>Y</mi> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a07b9920463d11820e4d2f5c12194efec8bbbabb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.254ex; height:1.509ex;" alt="{\displaystyle \scriptstyle Y}"></span> if, given a subroutine that solves <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 \scriptstyle Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mi>Y</mi> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a07b9920463d11820e4d2f5c12194efec8bbbabb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.254ex; height:1.509ex;" alt="{\displaystyle \scriptstyle Y}"></span> in polynomial time, one could write a program that calls this subroutine and solves <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 \scriptstyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mi>X</mi> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b88bfd56b234fcec7137b28c3982a284f776009" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.4ex; height:1.676ex;" alt="{\displaystyle \scriptstyle X}"></span> in polynomial time. This contrasts with many-one reducibility, which has the restriction that the program can only call the subroutine once, and the return value of the subroutine must be the return value of the program. </p><p>If one defines the analogue to NP-complete with Turing reductions instead of many-one reductions, the resulting set of problems won't be smaller than NP-complete; it is an open question whether it will be any larger. </p><p>Another type of reduction that is also often used to define NP-completeness is the <a href="/wiki/Logarithmic-space_many-one_reduction" class="mw-redirect" title="Logarithmic-space many-one reduction">logarithmic-space many-one reduction</a> which is a many-one reduction that can be computed with only a logarithmic amount of space. Since every computation that can be done in <a href="/wiki/Logarithmic_space" class="mw-redirect" title="Logarithmic space">logarithmic space</a> can also be done in polynomial time it follows that if there is a logarithmic-space many-one reduction then there is also a polynomial-time many-one reduction. This type of reduction is more refined than the more usual polynomial-time many-one reductions and it allows us to distinguish more classes such as <a href="/wiki/P-complete" title="P-complete">P-complete</a>. Whether under these types of reductions the definition of NP-complete changes is still an open problem. All currently known NP-complete problems are NP-complete under log space reductions. All currently known NP-complete problems remain NP-complete even under much weaker reductions such as <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 AC_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle AC_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/91af718047c0894c98c149c4d2accfab1ce620f6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.459ex; height:2.509ex;" alt="{\displaystyle AC_{0}}"></span> reductions and <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 NC_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle NC_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7acee2b474c478dc76db5f6add22623a3f3e7937" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.78ex; height:2.509ex;" alt="{\displaystyle NC_{0}}"></span> reductions. Some NP-Complete problems such as SAT are known to be complete even under polylogarithmic time projections.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> It is known, however, that <a href="/wiki/AC0" title="AC0">AC<sup>0</sup></a> reductions define a strictly smaller class than polynomial-time reductions.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Naming">Naming</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=8" title="Edit section: Naming"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>According to <a href="/wiki/Donald_Knuth" title="Donald Knuth">Donald Knuth</a>, the name "NP-complete" was popularized by <a href="/wiki/Alfred_Aho" title="Alfred Aho">Alfred Aho</a>, <a href="/wiki/John_Hopcroft" title="John Hopcroft">John Hopcroft</a> and <a href="/wiki/Jeffrey_Ullman" title="Jeffrey Ullman">Jeffrey Ullman</a> in their celebrated textbook "The Design and Analysis of Computer Algorithms". He reports that they introduced the change in the <a href="/wiki/Galley_proofs" class="mw-redirect" title="Galley proofs">galley proofs</a> for the book (from "polynomially-complete"), in accordance with the results of a poll he had conducted of the <a href="/wiki/Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a> community.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> Other suggestions made in the poll<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> included "<a href="/wiki/Labours_of_Hercules" title="Labours of Hercules">Herculean</a>", "formidable", <a href="/wiki/Kenneth_Steiglitz" title="Kenneth Steiglitz">Steiglitz</a>'s "hard-boiled" in honor of Cook, and Shen Lin's acronym "PET", which stood for "probably exponential time", but depending on which way the <a href="/wiki/P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a> went, could stand for "provably exponential time" or "previously exponential time".<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Common_misconceptions">Common misconceptions</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=9" title="Edit section: Common misconceptions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The following misconceptions are frequent.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> </p> <ul><li><i>"NP-complete problems are the most difficult known problems."</i> Since NP-complete problems are in NP, their running time is at most exponential. However, some problems have been proven to require more time, for example <a href="/wiki/Presburger_arithmetic" title="Presburger arithmetic">Presburger arithmetic</a>. Of some problems, it has even been proven that they can never be solved at all, for example the <a href="/wiki/Halting_problem" title="Halting problem">halting problem</a>.</li> <li><i>"NP-complete problems are difficult because there are so many different solutions."</i> On the one hand, there are many problems that have a solution space just as large, but can be solved in polynomial time (for example <a href="/wiki/Minimum_spanning_tree" title="Minimum spanning tree">minimum spanning tree</a>). On the other hand, there are NP-problems with at most one solution that are NP-hard under randomized polynomial-time reduction (see <a href="/wiki/Valiant%E2%80%93Vazirani_theorem" title="Valiant–Vazirani theorem">Valiant–Vazirani theorem</a>).</li> <li><i>"Solving NP-complete problems requires exponential time."</i> First, this would imply P ≠ NP, which is still an unsolved question. Further, some NP-complete problems actually have algorithms running in superpolynomial, but subexponential time such as O(2<sup><span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span></sup><i>n</i>). For example, the <a href="/wiki/Independent_set_problem" class="mw-redirect" title="Independent set problem">independent set</a> and <a href="/wiki/Dominating_set_problem" class="mw-redirect" title="Dominating set problem">dominating set</a> problems for <a href="/wiki/Planar_graph" title="Planar graph">planar graphs</a> are NP-complete, but can be solved in subexponential time using the <a href="/wiki/Planar_separator_theorem" title="Planar separator theorem">planar separator theorem</a>.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup></li> <li><i>"Each instance of an NP-complete problem is difficult."</i> Often some instances, or even most instances, may be easy to solve within polynomial time. However, unless P=NP, any polynomial-time algorithm must asymptotically be wrong on more than polynomially many of the exponentially many inputs of a certain size.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup></li> <li><i>"If P=NP, all cryptographic ciphers can be broken."</i> A polynomial-time problem can be very difficult to solve in practice if the polynomial's degree or constants are large enough. In addition, <a href="/wiki/Information-theoretic_security" title="Information-theoretic security">information-theoretic security</a> provides cryptographic methods that cannot be broken even with unlimited computing power.</li> <li><i>"A large-scale quantum computer would be able to efficiently solve NP-complete problems."</i> The class of decision problems that can be efficiently solved (in principle) by a fault-tolerant quantum computer is known as BQP. However, BQP is not believed to contain all of NP, and if it does not, then it cannot contain any NP-complete problem.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup></li></ul> <div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=10" title="Edit section: Properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Viewing a <a href="/wiki/Decision_problem#Definition" title="Decision problem">decision problem</a> as a formal language in some fixed encoding, the set NPC of all NP-complete problems is <b>not closed</b> under: </p> <ul><li><a href="/wiki/Union_(set_theory)" title="Union (set theory)">union</a></li> <li><a href="/wiki/Intersection" title="Intersection">intersection</a></li> <li><a href="/wiki/Concatenation" title="Concatenation">concatenation</a></li> <li><a href="/wiki/Kleene_star" title="Kleene star">Kleene star</a><sup class="noprint Inline-Template" style="margin-left:0.1em; white-space:nowrap;">[<i><a href="/wiki/Wikipedia:AUDIENCE" class="mw-redirect" title="Wikipedia:AUDIENCE"><span title="An editor has requested that an example be provided. (April 2023)">example needed</span></a></i>]</sup></li></ul> <p>It is not known whether NPC is closed under <a href="/wiki/Complement_(complexity)" title="Complement (complexity)">complementation</a>, since NPC=<a href="/wiki/Co-NP-complete" title="Co-NP-complete">co-NPC</a> if and only if NP=<a href="/wiki/Co-NP" title="Co-NP">co-NP</a>, and since NP=co-NP is an <a href="/wiki/Open_problem" title="Open problem">open question</a>.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=11" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Almost_complete" class="mw-redirect" title="Almost complete">Almost complete</a></li> <li><a href="/wiki/Gadget_(computer_science)" title="Gadget (computer science)">Gadget (computer science)</a></li> <li><a href="/wiki/Ladner%27s_theorem" class="mw-redirect" title="Ladner's theorem">Ladner's theorem</a></li> <li><a href="/wiki/List_of_NP-complete_problems" title="List of NP-complete problems">List of NP-complete problems</a></li> <li><a href="/wiki/NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a></li> <li><a href="/wiki/P_%3D_NP_problem" class="mw-redirect" title="P = NP problem">P = NP problem</a></li> <li><a href="/wiki/Strongly_NP-complete" class="mw-redirect" title="Strongly NP-complete">Strongly NP-complete</a></li> <li><a href="/wiki/Travelling_Salesman_(2012_film)" title="Travelling Salesman (2012 film)">Travelling Salesman (2012 film)</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=12" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Citations">Citations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=13" title="Edit section: Citations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;"> <ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">For example, simply assigning <i>true</i> to each variable renders the 18th conjunct <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 {\overline {m}}\lor {\overline {r}}\lor {\overline {s}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>m</mi> <mo accent="false">¯</mo> </mover> </mrow> <mo>∨</mo> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>r</mi> <mo accent="false">¯</mo> </mover> </mrow> <mo>∨</mo> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>s</mi> <mo accent="false">¯</mo> </mover> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\overline {m}}\lor {\overline {r}}\lor {\overline {s}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d349c49c3f8236dc617824f7e15ccabde69d5e51" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.69ex; height:2.343ex;" alt="{\displaystyle {\overline {m}}\lor {\overline {r}}\lor {\overline {s}}}"></span> (and hence the complete formula) <i>false</i>.</span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.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.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.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}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFCobham1965" class="citation book cs1"><a href="/wiki/Alan_Cobham" title="Alan Cobham">Cobham, Alan</a> (1965). "The intrinsic computational difficulty of functions". <i>Proc. Logic, Methodology, and Philosophy of Science II</i>. North Holland.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=The+intrinsic+computational+difficulty+of+functions&rft.btitle=Proc.+Logic%2C+Methodology%2C+and+Philosophy+of+Science+II&rft.pub=North+Holland&rft.date=1965&rft.aulast=Cobham&rft.aufirst=Alan&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJ._van_Leeuwen1998" class="citation book cs1">J. van Leeuwen (1998). <i>Handbook of Theoretical Computer Science</i>. Elsevier. p. 84. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-262-72014-4" title="Special:BookSources/978-0-262-72014-4"><bdi>978-0-262-72014-4</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Handbook+of+Theoretical+Computer+Science&rft.pages=84&rft.pub=Elsevier&rft.date=1998&rft.isbn=978-0-262-72014-4&rft.au=J.+van+Leeuwen&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJ._van_Leeuwen1998" class="citation book cs1">J. van Leeuwen (1998). <i>Handbook of Theoretical Computer Science</i>. Elsevier. p. 80. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-262-72014-4" title="Special:BookSources/978-0-262-72014-4"><bdi>978-0-262-72014-4</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Handbook+of+Theoretical+Computer+Science&rft.pages=80&rft.pub=Elsevier&rft.date=1998&rft.isbn=978-0-262-72014-4&rft.au=J.+van+Leeuwen&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKiersz" class="citation web cs1">Kiersz, Andy. <a rel="nofollow" class="external text" href="https://www.businessinsider.com/millennium-prize-problems-million-dollar-prize-2017-12">"An eminent mathematician claims to have solved one of math's greatest mysteries — and it's one of 6 problems with a $1 million prize"</a>. <i>Business Insider</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2023-04-24</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Business+Insider&rft.atitle=An+eminent+mathematician+claims+to+have+solved+one+of+math%27s+greatest+mysteries+%E2%80%94+and+it%27s+one+of+6+problems+with+a+%241+million+prize&rft.aulast=Kiersz&rft.aufirst=Andy&rft_id=https%3A%2F%2Fwww.businessinsider.com%2Fmillennium-prize-problems-million-dollar-prize-2017-12&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChenKanjXia2010" class="citation journal cs1">Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2010-09-06). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2010.06.026">"Improved upper bounds for vertex cover"</a>. <i>Theoretical Computer Science</i>. <b>411</b> (40): 3736–3756. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2010.06.026">10.1016/j.tcs.2010.06.026</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0304-3975">0304-3975</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theoretical+Computer+Science&rft.atitle=Improved+upper+bounds+for+vertex+cover&rft.volume=411&rft.issue=40&rft.pages=3736-3756&rft.date=2010-09-06&rft_id=info%3Adoi%2F10.1016%2Fj.tcs.2010.06.026&rft.issn=0304-3975&rft.aulast=Chen&rft.aufirst=Jianer&rft.au=Kanj%2C+Iyad+A.&rft.au=Xia%2C+Ge&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252Fj.tcs.2010.06.026&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAgrawalAllenderRudich1998" class="citation journal cs1"><a href="/wiki/Manindra_Agrawal" title="Manindra Agrawal">Agrawal, M.</a>; Allender, E.; <a href="/wiki/Steven_Rudich" title="Steven Rudich">Rudich, Steven</a> (1998). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.1998.1583">"Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem"</a>. <i>Journal of Computer and System Sciences</i>. <b>57</b> (2): 127–143. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.1998.1583">10.1006/jcss.1998.1583</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1090-2724">1090-2724</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=Reductions+in+Circuit+Complexity%3A+An+Isomorphism+Theorem+and+a+Gap+Theorem&rft.volume=57&rft.issue=2&rft.pages=127-143&rft.date=1998&rft_id=info%3Adoi%2F10.1006%2Fjcss.1998.1583&rft.issn=1090-2724&rft.aulast=Agrawal&rft.aufirst=M.&rft.au=Allender%2C+E.&rft.au=Rudich%2C+Steven&rft_id=https%3A%2F%2Fdoi.org%2F10.1006%252Fjcss.1998.1583&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAgrawalAllenderImpagliazzoPitassi2001" class="citation journal cs1"><a href="/wiki/Manindra_Agrawal" title="Manindra Agrawal">Agrawal, M.</a>; Allender, E.; Impagliazzo, R.; <a href="/wiki/Toniann_Pitassi" title="Toniann Pitassi">Pitassi, T.</a>; <a href="/wiki/Steven_Rudich" title="Steven Rudich">Rudich, Steven</a> (2001). "Reducing the complexity of reductions". <i>Computational Complexity</i>. <b>10</b> (2): 117–138. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00037-001-8191-1">10.1007/s00037-001-8191-1</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1016-3328">1016-3328</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:29017219">29017219</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Computational+Complexity&rft.atitle=Reducing+the+complexity+of+reductions&rft.volume=10&rft.issue=2&rft.pages=117-138&rft.date=2001&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A29017219%23id-name%3DS2CID&rft.issn=1016-3328&rft_id=info%3Adoi%2F10.1007%2Fs00037-001-8191-1&rft.aulast=Agrawal&rft.aufirst=M.&rft.au=Allender%2C+E.&rft.au=Impagliazzo%2C+R.&rft.au=Pitassi%2C+T.&rft.au=Rudich%2C+Steven&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><a href="/wiki/Don_Knuth" class="mw-redirect" title="Don Knuth">Don Knuth</a>, Tracy Larrabee, and Paul M. Roberts, <i><a rel="nofollow" class="external text" href="http://tex.loria.fr/typographie/mathwriting.pdf">Mathematical Writing</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100827044400/http://tex.loria.fr/typographie/mathwriting.pdf">Archived</a> 2010-08-27 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></i> § 25, <i>MAA Notes No. 14</i>, MAA, 1989 (also <a href="/wiki/Stanford_University" title="Stanford University">Stanford</a> Technical Report, 1987).</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKnuth1974" class="citation journal cs1">Knuth, D. F. (1974). "A terminological proposal". <i>SIGACT News</i>. <b>6</b> (1): 12–18. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1811129.1811130">10.1145/1811129.1811130</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:45313676">45313676</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIGACT+News&rft.atitle=A+terminological+proposal&rft.volume=6&rft.issue=1&rft.pages=12-18&rft.date=1974&rft_id=info%3Adoi%2F10.1145%2F1811129.1811130&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A45313676%23id-name%3DS2CID&rft.aulast=Knuth&rft.aufirst=D.+F.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">See the poll, or <a rel="nofollow" class="external autonumber" href="http://www.cs.princeton.edu/~wayne/kleinberg-tardos/08np-complete-2x2.pdf">[1]</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110607082034/http://www.cs.princeton.edu/~wayne/kleinberg-tardos/08np-complete-2x2.pdf">Archived</a> 2011-06-07 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>.</span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBall2000" class="citation news cs1">Ball, Philip (2000). <a rel="nofollow" class="external text" href="http://www.nature.com/news/2000/000113/full/news000113-10.html">"DNA computer helps travelling salesman"</a>. <i>Nature</i>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fnews000113-10">10.1038/news000113-10</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Nature&rft.atitle=DNA+computer+helps+travelling+salesman&rft.date=2000&rft_id=info%3Adoi%2F10.1038%2Fnews000113-10&rft.aulast=Ball&rft.aufirst=Philip&rft_id=http%3A%2F%2Fwww.nature.com%2Fnews%2F2000%2F000113%2Ffull%2Fnews000113-10.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><a href="#CITEREFBern1990">Bern (1990)</a>; <a href="#CITEREFDeĭnekoKlinzWoeginger2006">Deĭneko, Klinz & Woeginger (2006)</a>; <a href="#CITEREFDornPenninkxBodlaenderFomin2005">Dorn et al. (2005)</a>; <a href="#CITEREFLiptonTarjan1980">Lipton & Tarjan (1980)</a>.</span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHemaspaandraWilliams2012" class="citation journal cs1">Hemaspaandra, L. A.; Williams, R. (2012). "SIGACT News Complexity Theory Column 76". <i>ACM SIGACT News</i>. <b>43</b> (4): 70. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2421119.2421135">10.1145/2421119.2421135</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13367514">13367514</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+SIGACT+News&rft.atitle=SIGACT+News+Complexity+Theory+Column+76&rft.volume=43&rft.issue=4&rft.pages=70&rft.date=2012&rft_id=info%3Adoi%2F10.1145%2F2421119.2421135&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A13367514%23id-name%3DS2CID&rft.aulast=Hemaspaandra&rft.aufirst=L.+A.&rft.au=Williams%2C+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAaronson2010" class="citation conference cs1">Aaronson, Scott (2010). "BQP and the polynomial hierarchy". In Schulman, Leonard J. (ed.). <i>Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010</i>. Association for Computing Machinery. pp. 141–150. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0910.4698">0910.4698</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1806689.1806711">10.1145/1806689.1806711</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-0050-6" title="Special:BookSources/978-1-4503-0050-6"><bdi>978-1-4503-0050-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=BQP+and+the+polynomial+hierarchy&rft.btitle=Proceedings+of+the+42nd+ACM+Symposium+on+Theory+of+Computing%2C+STOC+2010%2C+Cambridge%2C+Massachusetts%2C+USA%2C+5%E2%80%938+June+2010&rft.pages=141-150&rft.pub=Association+for+Computing+Machinery&rft.date=2010&rft_id=info%3Aarxiv%2F0910.4698&rft_id=info%3Adoi%2F10.1145%2F1806689.1806711&rft.isbn=978-1-4503-0050-6&rft.aulast=Aaronson&rft.aufirst=Scott&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTalbotWelsh2006" class="citation cs2">Talbot, John; <a href="/wiki/Dominic_Welsh" title="Dominic Welsh">Welsh, D. J. A.</a> (2006), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=y_ZwupY8pzUC&pg=PA57"><i>Complexity and Cryptography: An Introduction</i></a>, Cambridge University Press, p. 57, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780521617710" title="Special:BookSources/9780521617710"><bdi>9780521617710</bdi></a>, <q>The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Complexity+and+Cryptography%3A+An+Introduction&rft.pages=57&rft.pub=Cambridge+University+Press&rft.date=2006&rft.isbn=9780521617710&rft.aulast=Talbot&rft.aufirst=John&rft.au=Welsh%2C+D.+J.+A.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3Dy_ZwupY8pzUC%26pg%3DPA57&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></span> </li> </ol></div> <div class="mw-heading mw-heading3"><h3 id="Sources">Sources</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=14" title="Edit section: Sources"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239549316">.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}</style><div class="refbegin refbegin-columns references-column-width" style="column-width: 30em"> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGareyJohnson1979" class="citation book cs1"><a href="/wiki/Michael_Garey" title="Michael Garey">Garey, Michael R.</a>; <a href="/wiki/David_S._Johnson" title="David S. Johnson">Johnson, David S.</a> (1979). <i><a href="/wiki/Computers_and_Intractability" title="Computers and Intractability">Computers and Intractability: A Guide to the Theory of NP-Completeness</a></i>. Series of Books in the Mathematical Sciences (1st ed.). New York: <a href="/wiki/W._H._Freeman_and_Company" title="W. H. Freeman and Company">W. H. Freeman and Company</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780716710455" title="Special:BookSources/9780716710455"><bdi>9780716710455</bdi></a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066">0519066</a>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/247570676">247570676</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computers+and+Intractability%3A+A+Guide+to+the+Theory+of+NP-Completeness&rft.place=New+York&rft.series=Series+of+Books+in+the+Mathematical+Sciences&rft.edition=1st&rft.pub=W.+H.+Freeman+and+Company&rft.date=1979&rft_id=info%3Aoclcnum%2F247570676&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D519066%23id-name%3DMR&rft.isbn=9780716710455&rft.aulast=Garey&rft.aufirst=Michael+R.&rft.au=Johnson%2C+David+S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span> This book is a classic, developing the theory, then cataloguing <i>many</i> NP-Complete problems.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCook1971" class="citation conference cs1"><a href="/wiki/Stephen_A._Cook" class="mw-redirect" title="Stephen A. Cook">Cook, S.A.</a> (1971). "The complexity of theorem proving procedures". <i>Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York</i>. pp. 151–158. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800157.805047">10.1145/800157.805047</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=The+complexity+of+theorem+proving+procedures&rft.btitle=Proceedings%2C+Third+Annual+ACM+Symposium+on+the+Theory+of+Computing%2C+ACM%2C+New+York&rft.pages=151-158&rft.date=1971&rft_id=info%3Adoi%2F10.1145%2F800157.805047&rft.aulast=Cook&rft.aufirst=S.A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDunne" class="citation web cs1">Dunne, P.E. <a rel="nofollow" class="external text" href="http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html">"An annotated list of selected NP-complete problems"</a>. COMP202, Dept. of Computer Science, <a href="/wiki/University_of_Liverpool" title="University of Liverpool">University of Liverpool</a><span class="reference-accessdate">. Retrieved <span class="nowrap">2008-06-21</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=An+annotated+list+of+selected+NP-complete+problems&rft.pub=COMP202%2C+Dept.+of+Computer+Science%2C+University+of+Liverpool&rft.aulast=Dunne&rft.aufirst=P.E&rft_id=http%3A%2F%2Fwww.csc.liv.ac.uk%2F~ped%2Fteachadmin%2FCOMP202%2Fannotated_np.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCrescenziKann,_V.Halldórsson,_M.Karpinski,_M." class="citation web cs1">Crescenzi, P.; Kann, V.; Halldórsson, M.; <a href="/wiki/Marek_Karpinski" title="Marek Karpinski">Karpinski, M.</a>; <a href="/wiki/Gerhard_J._Woeginger" title="Gerhard J. Woeginger">Woeginger, G</a>. <a rel="nofollow" class="external text" href="http://www.csc.kth.se/~viggo/problemlist/">"A compendium of NP optimization problems"</a>. KTH, Stockholm<span class="reference-accessdate">. Retrieved <span class="nowrap">2020-10-24</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=A+compendium+of+NP+optimization+problems&rft.pub=KTH%2C+Stockholm&rft.aulast=Crescenzi&rft.aufirst=P.&rft.au=Kann%2C+V.&rft.au=Halld%C3%B3rsson%2C+M.&rft.au=Karpinski%2C+M.&rft.au=Woeginger%2C+G&rft_id=http%3A%2F%2Fwww.csc.kth.se%2F~viggo%2Fproblemlist%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDahlke" class="citation web cs1">Dahlke, K. <a rel="nofollow" class="external text" href="http://www.mathreference.com/lan-cx-np,intro.html">"NP-complete problems"</a>. <i>Math Reference Project</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2008-06-21</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Math+Reference+Project&rft.atitle=NP-complete+problems&rft.aulast=Dahlke&rft.aufirst=K&rft_id=http%3A%2F%2Fwww.mathreference.com%2Flan-cx-np%2Cintro.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKarlsson" class="citation web cs1">Karlsson, R. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090419082030/http://www.cs.lth.se/home/Rolf_Karlsson/bk/lect8.pdf">"Lecture 8: NP-complete problems"</a> <span class="cs1-format">(PDF)</span>. Dept. of Computer Science, Lund University, Sweden. Archived from <a rel="nofollow" class="external text" href="http://www.cs.lth.se/home/Rolf_Karlsson/bk/lect8.pdf">the original</a> <span class="cs1-format">(PDF)</span> on April 19, 2009<span class="reference-accessdate">. Retrieved <span class="nowrap">2008-06-21</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Lecture+8%3A+NP-complete+problems&rft.pub=Dept.+of+Computer+Science%2C+Lund+University%2C+Sweden&rft.aulast=Karlsson&rft.aufirst=R&rft_id=http%3A%2F%2Fwww.cs.lth.se%2Fhome%2FRolf_Karlsson%2Fbk%2Flect8.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSun" class="citation web cs1">Sun, H.M. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090902082705/http://is.cs.nthu.edu.tw/course/2008Spring/cs431102/hmsunCh08.ppt">"The theory of NP-completeness"</a>. Information Security Laboratory, Dept. of Computer Science, <a href="/wiki/National_Tsing_Hua_University" title="National Tsing Hua University">National Tsing Hua University</a>, Hsinchu City, Taiwan. Archived from <a rel="nofollow" class="external text" href="http://is.cs.nthu.edu.tw/course/2008Spring/cs431102/hmsunCh08.ppt">the original</a> <span class="cs1-format">(PPT)</span> on 2009-09-02<span class="reference-accessdate">. Retrieved <span class="nowrap">2008-06-21</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=The+theory+of+NP-completeness&rft.pub=Information+Security+Laboratory%2C+Dept.+of+Computer+Science%2C+National+Tsing+Hua+University%2C+Hsinchu+City%2C+Taiwan&rft.aulast=Sun&rft.aufirst=H.M&rft_id=http%3A%2F%2Fis.cs.nthu.edu.tw%2Fcourse%2F2008Spring%2Fcs431102%2FhmsunCh08.ppt&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJiang" class="citation web cs1">Jiang, J.R. <a rel="nofollow" class="external text" href="http://www.csie.ncu.edu.tw/%7Ejrjiang/alg2006/NPC-3.ppt">"The theory of NP-completeness"</a> <span class="cs1-format">(PPT)</span>. Dept. of Computer Science and Information Engineering, <a href="/wiki/National_Central_University" title="National Central University">National Central University</a>, Jhongli City, Taiwan<span class="reference-accessdate">. Retrieved <span class="nowrap">2008-06-21</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=The+theory+of+NP-completeness&rft.pub=Dept.+of+Computer+Science+and+Information+Engineering%2C+National+Central+University%2C+Jhongli+City%2C+Taiwan&rft.aulast=Jiang&rft.aufirst=J.R&rft_id=http%3A%2F%2Fwww.csie.ncu.edu.tw%2F%257Ejrjiang%2Falg2006%2FNPC-3.ppt&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCormenLeiserson,_C.E.Rivest,_R.L.Stein,_C.2001" class="citation book cs1"><a href="/wiki/Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, T.H.</a>; <a href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, C.E.</a>; <a href="/wiki/Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Rivest, R.L.</a>; <a href="/wiki/Clifford_Stein" title="Clifford Stein">Stein, C.</a> (2001). "Chapter 34: NP–Completeness". <a href="/wiki/Introduction_to_Algorithms" title="Introduction to Algorithms"><i>Introduction to Algorithms</i></a> (2nd ed.). MIT Press and McGraw-Hill. pp. 966–1021. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-262-03293-3" title="Special:BookSources/978-0-262-03293-3"><bdi>978-0-262-03293-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Chapter+34%3A+NP%E2%80%93Completeness&rft.btitle=Introduction+to+Algorithms&rft.pages=966-1021&rft.edition=2nd&rft.pub=MIT+Press+and+McGraw-Hill&rft.date=2001&rft.isbn=978-0-262-03293-3&rft.aulast=Cormen&rft.aufirst=T.H.&rft.au=Leiserson%2C+C.E.&rft.au=Rivest%2C+R.L.&rft.au=Stein%2C+C.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSipser1997" class="citation book cs1"><a href="/wiki/Michael_Sipser" title="Michael Sipser">Sipser, M.</a> (1997). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoth00sips/page/248">"Sections 7.4–7.5 (NP-completeness, Additional NP-complete Problems)"</a></span>. <i>Introduction to the Theory of Computation</i>. PWS Publishing. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoth00sips/page/248">248–271</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-534-94728-6" title="Special:BookSources/978-0-534-94728-6"><bdi>978-0-534-94728-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Sections+7.4%E2%80%937.5+%28NP-completeness%2C+Additional+NP-complete+Problems%29&rft.btitle=Introduction+to+the+Theory+of+Computation&rft.pages=248-271&rft.pub=PWS+Publishing&rft.date=1997&rft.isbn=978-0-534-94728-6&rft.aulast=Sipser&rft.aufirst=M.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fintroductiontoth00sips%2Fpage%2F248&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPapadimitriou1994" class="citation book cs1"><a href="/wiki/Christos_Papadimitriou" title="Christos Papadimitriou">Papadimitriou, C.</a> (1994). "Chapter 9 (NP-complete problems)". <i>Computational Complexity</i> (1st ed.). Addison Wesley. pp. 181–218. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-201-53082-7" title="Special:BookSources/978-0-201-53082-7"><bdi>978-0-201-53082-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Chapter+9+%28NP-complete+problems%29&rft.btitle=Computational+Complexity&rft.pages=181-218&rft.edition=1st&rft.pub=Addison+Wesley&rft.date=1994&rft.isbn=978-0-201-53082-7&rft.aulast=Papadimitriou&rft.aufirst=C.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span></li> <li><a rel="nofollow" class="external text" href="http://www.ics.uci.edu/~eppstein/cgt/hard.html">Computational Complexity of Games and Puzzles</a></li> <li><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs.CC/0210020">Tetris is Hard, Even to Approximate</a></li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20061216121200/http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm">Minesweeper is NP-complete!</a></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBern1990" class="citation journal cs1">Bern, Marshall (1990). "Faster exact algorithms for Steiner trees in planar networks". <i>Networks</i>. <b>20</b> (1): 109–120. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fnet.3230200110">10.1002/net.3230200110</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Networks&rft.atitle=Faster+exact+algorithms+for+Steiner+trees+in+planar+networks&rft.volume=20&rft.issue=1&rft.pages=109-120&rft.date=1990&rft_id=info%3Adoi%2F10.1002%2Fnet.3230200110&rft.aulast=Bern&rft.aufirst=Marshall&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDeĭnekoKlinzWoeginger2006" class="citation journal cs1">Deĭneko, Vladimir G.; Klinz, Bettina; <a href="/wiki/Gerhard_J._Woeginger" title="Gerhard J. Woeginger">Woeginger, Gerhard J.</a> (2006). "Exact algorithms for the Hamiltonian cycle problem in planar graphs". <i>Operations Research Letters</i>. <b>34</b> (3): 269–274. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.orl.2005.04.013">10.1016/j.orl.2005.04.013</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Operations+Research+Letters&rft.atitle=Exact+algorithms+for+the+Hamiltonian+cycle+problem+in+planar+graphs&rft.volume=34&rft.issue=3&rft.pages=269-274&rft.date=2006&rft_id=info%3Adoi%2F10.1016%2Fj.orl.2005.04.013&rft.aulast=De%C4%ADneko&rft.aufirst=Vladimir+G.&rft.au=Klinz%2C+Bettina&rft.au=Woeginger%2C+Gerhard+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDornPenninkxBodlaenderFomin2005" class="citation book cs1">Dorn, Frederic; Penninkx, Eelko; <a href="/wiki/Hans_L._Bodlaender" title="Hans L. Bodlaender">Bodlaender, Hans L.</a>; Fomin, Fedor V. (2005). "Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions". <i>Proc. 13th European Symposium on Algorithms (ESA '05)</i>. Lecture Notes in Computer Science. Vol. 3669. Springer-Verlag. pp. 95–106. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11561071_11">10.1007/11561071_11</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-29118-3" title="Special:BookSources/978-3-540-29118-3"><bdi>978-3-540-29118-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Efficient+Exact+Algorithms+on+Planar+Graphs%3A+Exploiting+Sphere+Cut+Branch+Decompositions&rft.btitle=Proc.+13th+European+Symposium+on+Algorithms+%28ESA+%2705%29&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=95-106&rft.pub=Springer-Verlag&rft.date=2005&rft_id=info%3Adoi%2F10.1007%2F11561071_11&rft.isbn=978-3-540-29118-3&rft.aulast=Dorn&rft.aufirst=Frederic&rft.au=Penninkx%2C+Eelko&rft.au=Bodlaender%2C+Hans+L.&rft.au=Fomin%2C+Fedor+V.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLiptonTarjan1980" class="citation journal cs1"><a href="/wiki/Richard_J._Lipton" class="mw-redirect" title="Richard J. Lipton">Lipton, Richard J.</a>; <a href="/wiki/Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (1980). "Applications of a planar separator theorem". <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>. <b>9</b> (3): 615–627. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0209046">10.1137/0209046</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:12961628">12961628</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Applications+of+a+planar+separator+theorem&rft.volume=9&rft.issue=3&rft.pages=615-627&rft.date=1980&rft_id=info%3Adoi%2F10.1137%2F0209046&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A12961628%23id-name%3DS2CID&rft.aulast=Lipton&rft.aufirst=Richard+J.&rft.au=Tarjan%2C+Robert+E.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ANP-completeness" class="Z3988"></span>.</li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=NP-completeness&action=edit&section=15" title="Edit section: Further reading"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239549316"><div class="refbegin" style=""> <ul><li><a href="/wiki/Scott_Aaronson" title="Scott Aaronson">Scott Aaronson</a>, <i><a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0502072">NP-complete Problems and Physical Reality</a></i>, ACM <a href="/wiki/SIGACT" class="mw-redirect" title="SIGACT">SIGACT</a> News, Vol. 36, No. 1. (March 2005), pp. 30–52.</li> <li><a href="/wiki/Lance_Fortnow" title="Lance Fortnow">Lance Fortnow</a>, <i><a rel="nofollow" class="external text" href="http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf">The status of the P versus NP problem</a></i>, <a href="/wiki/Commun._ACM" class="mw-redirect" title="Commun. ACM">Commun. ACM</a>, Vol. 52, No. 9. (2009), pp. 78–86.</li></ul> </div> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Complexity_classes" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Complexity_classes" title="Template:Complexity classes"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Complexity_classes" title="Template talk:Complexity classes"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Complexity_classes" title="Special:EditPage/Template:Complexity classes"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Complexity_classes" style="font-size:114%;margin:0 4em"><a href="/wiki/Complexity_class" title="Complexity class">Complexity classes</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Considered feasible</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/DLOGTIME" title="DLOGTIME">DLOGTIME</a></li> <li><a href="/wiki/AC0" title="AC0">AC<sup>0</sup></a></li> <li><a href="/wiki/ACC0" title="ACC0">ACC<sup>0</sup></a></li> <li><a href="/wiki/TC0" title="TC0">TC<sup>0</sup></a></li> <li><a href="/wiki/L_(complexity)" title="L (complexity)">L</a></li> <li><a href="/wiki/SL_(complexity)" title="SL (complexity)">SL</a></li> <li><a href="/wiki/RL_(complexity)" title="RL (complexity)">RL</a></li> <li><a href="/wiki/FL_(complexity)" title="FL (complexity)">FL</a></li> <li><a href="/wiki/NL_(complexity)" title="NL (complexity)">NL</a> <ul><li><a href="/wiki/NL-complete" title="NL-complete">NL-complete</a></li></ul></li> <li><a href="/wiki/NC_(complexity)" title="NC (complexity)">NC</a></li> <li><a href="/wiki/SC_(complexity)" title="SC (complexity)">SC</a></li> <li><a href="/wiki/CC_(complexity)" title="CC (complexity)">CC</a></li> <li><a href="/wiki/P_(complexity)" title="P (complexity)">P</a> <ul><li><a href="/wiki/P-complete" title="P-complete">P-complete</a></li></ul></li> <li><a href="/wiki/ZPP_(complexity)" title="ZPP (complexity)">ZPP</a></li> <li><a href="/wiki/RP_(complexity)" title="RP (complexity)">RP</a></li> <li><a href="/wiki/BPP_(complexity)" title="BPP (complexity)">BPP</a></li> <li><a href="/wiki/BQP" title="BQP">BQP</a></li> <li><a href="/wiki/APX" title="APX">APX</a></li> <li><a href="/wiki/FP_(complexity)" title="FP (complexity)">FP</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Suspected infeasible</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/UP_(complexity)" title="UP (complexity)">UP</a></li> <li><a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a> <ul><li><a class="mw-selflink selflink">NP-complete</a></li> <li><a href="/wiki/NP-hardness" title="NP-hardness">NP-hard</a></li> <li><a href="/wiki/Co-NP" title="Co-NP">co-NP</a></li> <li><a href="/wiki/Co-NP-complete" title="Co-NP-complete">co-NP-complete</a></li></ul></li> <li><a href="/wiki/TFNP" title="TFNP">TFNP</a></li> <li><a href="/wiki/FNP_(complexity)" title="FNP (complexity)">FNP</a></li> <li><a href="/wiki/Arthur%E2%80%93Merlin_protocol" title="Arthur–Merlin protocol">AM</a></li> <li><a href="/wiki/QMA" title="QMA">QMA</a></li> <li><a href="/wiki/PH_(complexity)" title="PH (complexity)">PH</a></li> <li><a href="/wiki/Parity_P" title="Parity P">⊕P</a></li> <li><a href="/wiki/PP_(complexity)" title="PP (complexity)">PP</a></li> <li><a href="/wiki/%E2%99%AFP" title="♯P">#P</a> <ul><li><a href="/wiki/%E2%99%AFP-complete" title="♯P-complete">#P-complete</a></li></ul></li> <li><a href="/wiki/IP_(complexity)" title="IP (complexity)">IP</a></li> <li><a href="/wiki/PSPACE" title="PSPACE">PSPACE</a> <ul><li><a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Considered infeasible</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/EXPTIME" title="EXPTIME">EXPTIME</a></li> <li><a href="/wiki/NEXPTIME" title="NEXPTIME">NEXPTIME</a></li> <li><a href="/wiki/EXPSPACE" title="EXPSPACE">EXPSPACE</a></li> <li><a href="/wiki/2-EXPTIME" title="2-EXPTIME">2-EXPTIME</a></li> <li><a href="/wiki/ELEMENTARY" title="ELEMENTARY">ELEMENTARY</a></li> <li><a href="/wiki/PR_(complexity)" title="PR (complexity)">PR</a></li> <li><a href="/wiki/R_(complexity)" title="R (complexity)">R</a></li> <li><a href="/wiki/RE_(complexity)" title="RE (complexity)">RE</a></li> <li><a href="/wiki/ALL_(complexity)" title="ALL (complexity)">ALL</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Class hierarchies</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Polynomial_hierarchy" title="Polynomial hierarchy">Polynomial hierarchy</a></li> <li><a href="/wiki/Exponential_hierarchy" title="Exponential hierarchy">Exponential hierarchy</a></li> <li><a href="/wiki/Grzegorczyk_hierarchy" title="Grzegorczyk hierarchy">Grzegorczyk hierarchy</a></li> <li><a href="/wiki/Arithmetical_hierarchy" title="Arithmetical hierarchy">Arithmetical hierarchy</a></li> <li><a href="/wiki/Boolean_hierarchy" title="Boolean hierarchy">Boolean hierarchy</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Families of classes</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/DTIME" title="DTIME">DTIME</a></li> <li><a href="/wiki/NTIME" title="NTIME">NTIME</a></li> <li><a href="/wiki/DSPACE" title="DSPACE">DSPACE</a></li> <li><a href="/wiki/NSPACE" title="NSPACE">NSPACE</a></li> <li><a href="/wiki/Probabilistically_checkable_proof" title="Probabilistically checkable proof">Probabilistically checkable proof</a></li> <li><a href="/wiki/Interactive_proof_system" title="Interactive proof system">Interactive proof system</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><a href="/wiki/List_of_complexity_classes" title="List of complexity classes">List of complexity classes</a></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=NP-completeness&oldid=1257002113">https://en.wikipedia.org/w/index.php?title=NP-completeness&oldid=1257002113</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:1971_in_computing" title="Category:1971 in computing">1971 in computing</a></li><li><a href="/wiki/Category:NP-complete_problems" title="Category:NP-complete problems">NP-complete problems</a></li><li><a href="/wiki/Category:Complexity_classes" title="Category:Complexity classes">Complexity classes</a></li><li><a href="/wiki/Category:Mathematical_optimization" title="Category:Mathematical optimization">Mathematical optimization</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_clarification_from_July_2012" title="Category:Wikipedia articles needing clarification from July 2012">Wikipedia articles needing clarification from July 2012</a></li><li><a href="/wiki/Category:All_Wikipedia_articles_needing_clarification" title="Category:All Wikipedia articles needing clarification">All Wikipedia articles needing clarification</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_October_2022" title="Category:Articles with unsourced statements from October 2022">Articles with unsourced statements from October 2022</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_August_2024" title="Category:Articles with unsourced statements from August 2024">Articles with unsourced statements from August 2024</a></li><li><a href="/wiki/Category:All_articles_needing_examples" title="Category:All articles needing examples">All articles needing examples</a></li><li><a href="/wiki/Category:Articles_needing_examples_from_April_2023" title="Category:Articles needing examples from April 2023">Articles needing examples from April 2023</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 12 November 2024, at 17:49<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=NP-completeness&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</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"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></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"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-5857dfdcd6-bh7wn","wgBackendResponseTime":165,"wgPageParseReport":{"limitreport":{"cputime":"0.555","walltime":"0.820","ppvisitednodes":{"value":3045,"limit":1000000},"postexpandincludesize":{"value":81697,"limit":2097152},"templateargumentsize":{"value":3347,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":6,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":92482,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 572.023 1 -total"," 28.79% 164.701 1 Template:Reflist"," 18.30% 104.673 8 Template:Cite_book"," 13.89% 79.459 1 Template:ComplexityClasses"," 13.12% 75.042 1 Template:Navbox"," 10.55% 60.328 1 Template:Short_description"," 9.19% 52.597 1 Template:Confusing"," 8.43% 48.204 1 Template:Ambox"," 7.27% 41.599 5 Template:Harvtxt"," 7.19% 41.116 4 Template:Cn"]},"scribunto":{"limitreport-timeusage":{"value":"0.352","limit":"10.000"},"limitreport-memusage":{"value":8185141,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFAaronson2010\"] = 1,\n [\"CITEREFAgrawalAllenderImpagliazzoPitassi2001\"] = 1,\n [\"CITEREFAgrawalAllenderRudich1998\"] = 1,\n [\"CITEREFBall2000\"] = 1,\n [\"CITEREFBern1990\"] = 1,\n [\"CITEREFChenKanjXia2010\"] = 1,\n [\"CITEREFCobham1965\"] = 1,\n [\"CITEREFCook1971\"] = 1,\n [\"CITEREFCormenLeiserson,_C.E.Rivest,_R.L.Stein,_C.2001\"] = 1,\n [\"CITEREFCrescenziKann,_V.Halldórsson,_M.Karpinski,_M.\"] = 1,\n [\"CITEREFDahlke\"] = 1,\n [\"CITEREFDeĭnekoKlinzWoeginger2006\"] = 1,\n [\"CITEREFDornPenninkxBodlaenderFomin2005\"] = 1,\n [\"CITEREFDunne\"] = 1,\n [\"CITEREFHemaspaandraWilliams2012\"] = 1,\n [\"CITEREFJ._van_Leeuwen1998\"] = 2,\n [\"CITEREFJiang\"] = 1,\n [\"CITEREFKarlsson\"] = 1,\n [\"CITEREFKiersz\"] = 1,\n [\"CITEREFKnuth1974\"] = 1,\n [\"CITEREFLiptonTarjan1980\"] = 1,\n [\"CITEREFPapadimitriou1994\"] = 1,\n [\"CITEREFSipser1997\"] = 1,\n [\"CITEREFSun\"] = 1,\n [\"CITEREFTalbotWelsh2006\"] = 1,\n}\ntemplate_list = table#1 {\n [\"Citation\"] = 1,\n [\"Cite book\"] = 7,\n [\"Cite conference\"] = 2,\n [\"Cite journal\"] = 8,\n [\"Cite news\"] = 1,\n [\"Cite web\"] = 7,\n [\"Cn\"] = 4,\n [\"ComplexityClasses\"] = 1,\n [\"Confusing\"] = 1,\n [\"DEFAULTSORT:Np-Complete\"] = 1,\n [\"Div col\"] = 1,\n [\"Div col end\"] = 1,\n [\"Example needed\"] = 1,\n [\"Garey-Johnson\"] = 1,\n [\"Harvtxt\"] = 5,\n [\"Main\"] = 1,\n [\"Refbegin\"] = 2,\n [\"Refend\"] = 2,\n [\"Reflist\"] = 1,\n [\"See also\"] = 1,\n [\"Short description\"] = 1,\n [\"Sic\"] = 1,\n [\"Sqrt\"] = 1,\n [\"Webarchive\"] = 2,\n}\narticle_whitelist = table#1 {\n}\nciteref_patterns = table#1 {\n}\n"},"cachereport":{"origin":"mw-web.codfw.main-5857dfdcd6-fdgjj","timestamp":"20241203052838","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"NP-completeness","url":"https:\/\/en.wikipedia.org\/wiki\/NP-completeness","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":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-08-25T15:24:56Z","dateModified":"2024-11-12T17:49:12Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/6\/69\/3SAT_17_svg.svg","headline":"complexity class"}</script> </body> </html>