Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" lang="en" dir="ltr"> <head> <title>NP-complete - Wikipedia, the free encyclopedia<

185 views

Skip to first unread message

sci.math

unread,

Jul 6, 2010, 5:36:11 PM7/6/10

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://
www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" dir="ltr">
<head>
<title>NP-complete - Wikipedia, the free encyclopedia</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<meta name="generator" content="MediaWiki 1.16wmf4" />
<link rel="alternate" type="application/x-wiki" title="Edit this page"
href="/w/index.php?title=NP-complete&action=edit" />
<link rel="edit" title="Edit this page" href="/w/index.php?title=NP-
complete&action=edit" />
<link rel="apple-touch-icon" href="http://en.wikipedia.org/apple-touch-
icon.png" />
<link rel="shortcut icon" href="/favicon.ico" />
<link rel="search" type="application/opensearchdescription+xml" href="/
w/opensearch_desc.php" title="Wikipedia (en)" />
<link rel="copyright" href="http://creativecommons.org/licenses/by-sa/
3.0/" />
<link rel="alternate" type="application/atom+xml" title="Wikipedia
Atom feed" href="/w/index.php?
title=Special:RecentChanges&feed=atom" />
<link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/
vector/main-ltr.css?283l" type="text/css" media="screen" />
<link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/
common/shared.css?283l" type="text/css" media="screen" />

<script src="/w/index.php?title=-
&action=raw&gen=js&useskin=vector&283l" type="text/
javascript"></script>

</head>
<body class="mediawiki ltr ns-0 ns-subject page-NP-complete skin-
vector">

<div id="mw-page-base" class="noprint"></div>
<div id="mw-head-base" class="noprint"></div>

<div id="content">
<a id="top"></a>
<div id="mw-js-message" style="display:none;"></div>

<div id="siteNotice"><script type='text/javascript'>if (wgNotice !=
'') document.writeln(wgNotice);</script></div>

<h1 id="firstHeading" class="firstHeading">NP-complete</h1>


<div id="bodyContent">

<h3 id="siteSub">From Wikipedia, the free encyclopedia</h3>

<div id="contentSub"></div>


<div id="jump-to-nav">
Jump to: <a href="#mw-head">navigation</a>,
<a href="#p-search">search</a>

</div>


<p>In <a href="/wiki/Computational_complexity_theory"
title="Computational complexity theory">computational complexity
theory</a>, the <a href="/wiki/Complexity_class" title="Complexity
class">complexity class</a> <b>NP-complete</b> (abbreviated <b>NP-C</
b> or <b>NPC</b>), is a class of problems having two properties:</p>

<ul>
<li>It is in the set of <a href="/wiki/NP_(complexity)" title="NP
(complexity)">NP</a> (nondeterministic polynomial time) problems: Any
given solution to the problem can be <i>verified</i> quickly (in <a
href="/wiki/Polynomial_time" title="Polynomial time" class="mw-
redirect">polynomial time</a>).</li>
<li>It is also in the set of <a href="/wiki/NP-hard" title="NP-
hard">NP-hard</a> problems: Any NP problem can be converted into this
one by a transformation of the inputs in polynomial time.</li>
</ul>

<p>Although any given solution to such a problem can be verified
quickly, there is no known efficient way to locate a solution in the
first place; indeed, the most notable characteristic of NP-complete
problems is that no fast solution to them is known. That is, the time
required to solve the problem using any currently known <a href="/wiki/
Algorithm" title="Algorithm">algorithm</a> increases very quickly as
the size of the problem grows. As a result, the time required to solve
even moderately large versions of many of these problems easily
reaches into the billions or trillions of years, using any amount of
computing power available today. As a consequence, determining whether
or not it is possible to solve these problems quickly is one of the
principal <a href="/wiki/List_of_open_problems_in_computer_science"
title="List of open problems in computer science" class="mw-
redirect">unsolved problems in computer science</a> today.</p>
<p>While a method for computing the solutions to NP-complete problems
using a reasonable amount of time remains undiscovered, <a href="/wiki/
Computer_scientist" title="Computer scientist">computer scientists</a>
and <a href="/wiki/Computer_programmer" title="Computer programmer"
class="mw-redirect">programmers</a> still frequently encounter NP-
complete problems. An expert programmer should be able to recognize an
NP-complete problem so that he or she does not unknowingly spend time
trying to solve a problem which so far has eluded generations of
computer scientists. Instead, NP-complete problems are often addressed
by using <a href="/wiki/Approximation_algorithm" title="Approximation
algorithm">approximation algorithms</a>.</p>

<table id="toc" class="toc">
<tr>
<td>
<div id="toctitle">
<h2>Contents</h2>
</div>
<ul>
<li class="toclevel-1 tocsection-1"><a href="#Formal_overview"><span
class="tocnumber">1</span> <span class="toctext">Formal overview</
span></a></li>
<li class="toclevel-1 tocsection-2"><a href="#Formal_definition_of_NP-
completeness"><span class="tocnumber">2</span> <span
class="toctext">Formal definition of NP-completeness</span></a></li>
<li class="toclevel-1 tocsection-3"><a href="#Background"><span
class="tocnumber">3</span> <span class="toctext">Background</span></
a></li>

<li class="toclevel-1 tocsection-4"><a href="#NP-
complete_problems"><span class="tocnumber">4</span> <span
class="toctext">NP-complete problems</span></a></li>
<li class="toclevel-1 tocsection-5"><a href="#Solving_NP-
complete_problems"><span class="tocnumber">5</span> <span
class="toctext">Solving NP-complete problems</span></a></li>
<li class="toclevel-1 tocsection-6"><a
href="#Completeness_under_different_types_of_reduction"><span
class="tocnumber">6</span> <span class="toctext">Completeness under
different types of reduction</span></a></li>
<li class="toclevel-1 tocsection-7"><a href="#Naming"><span
class="tocnumber">7</span> <span class="toctext">Naming</span></a></
li>
<li class="toclevel-1 tocsection-8"><a href="#See_also"><span
class="tocnumber">8</span> <span class="toctext">See also</span></a></
li>

<li class="toclevel-1 tocsection-9"><a href="#References"><span
class="tocnumber">9</span> <span class="toctext">References</span></
a></li>
<li class="toclevel-1 tocsection-10"><a href="#Further_reading"><span
class="tocnumber">10</span> <span class="toctext">Further reading</
span></a></li>
</ul>
</td>
</tr>
</table>
<script type="text/javascript">
//<![CDATA[
if (window.showTocToggle) { var tocShowText = "show"; var tocHideText
= "hide"; showTocToggle(); }
//]]>
</script>
<h2><span class="editsection">[<a href="/w/index.php?title=NP-
complete&action=edit&section=1" title="Edit section: Formal
overview">edit</a>]</span> <span class="mw-headline"
id="Formal_overview">Formal overview</span></h2>

<p>NP-complete is a <a href="/wiki/Subset" title="Subset">subset</a>
of <a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a>, the
set of all <a href="/wiki/Decision_problems" title="Decision problems"
class="mw-redirect">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/Nondeterministic_Turing_machine"
title="Nondeterministic Turing machine" class="mw-
redirect">nondeterministic Turing machine</a>. A problem <i>p</i> in
NP is also in NPC <a href="/wiki/If_and_only_if" title="If and only
if">if and only if</a> every other problem in NP can be transformed
into <i>p</i> in polynomial time. NP-complete can also be used as an
adjective: problems in the class NP-complete are known as NP-complete
problems.</p>

<p>What follows is reduced source code:</p>
<p><code>// Copyright © 2010 www.meami.org // // The information on
this page may not be reproduced or republished on another web page or
web site unless done so by M. M. Musatov (with the exception of
Wikipedia). // M. M. Musatov, Meami.org, release this code for private
non-profit non-commercial use only - All Other Rights Reserved. // //
#include // #include // #include // #include // // using namespace
std; // // typedef struct node // { // int nElem; // struct node
*pNextNode; // }Node; // // // int pushElem(Node **argpRoot, int
argnElem) // { // Node *pNewNode; // pNewNode = (Node
*)malloc(sizeof(Node)); // if(!pNewNode) // { // fprintf(stderr,"\n\t
ERR: Memory allocation failure for Node \n"); // return -1; // } // //
pNewNode->nElem = argnElem; // pNewNode->pNextNode = NULL; //
if(*argpRoot==NULL) // { // *argpRoot = pNewNode; // } // else // { //
pNewNode->pNextNode = *argpRoot; // *argpRoot = pNewNode; // } //
return 1; // } // // // int popElem(Node **argpRoot) // { //
assert(*argpRoot!=NULL); // int nRetElem; // Node *pDeleteNode; //
pDeleteNode = *argpRoot; // *argpRoot = (*argpRoot)->pNextNode; //
nRetElem = pDeleteNode->nElem; // free(pDeleteNode); // return
nRetElem; // } // // void deleteList(Node **argpRoot) // { //
while(*argpRoot) // { // popElem(argpRoot); // } // } // // void
printElems(Node *argpRoot) // { // //assert(argpRoot != NULL); //
if(argpRoot!=NULL) // { // Node *pTempNode = argpRoot; //
while(pTempNode->pNextNode) // { // fprintf(stdout,"%d-
>",pTempNode->nElem); // pTempNode = pTempNode-
>pNextNode; // } // fprintf(stdout,"%d",pTempNode-
>nElem); // } // } // // int findElemFromListEnd(Node *argpRoot,int
nTargetPos,int *argpnElem) // { // /* // assert(argpRoot!=NULL); //
assert(nTargetPos <= INT_MAX && nTargetPos > 0); //
assert(argpnElem!=NULL); // */ // // if(argpRoot == NULL) // { //
fprintf(stderr, "\n\t ERR: list is empty\n"); // return -1; // } // //
if((nTargetPos > INT_MAX) || (nTargetPos <= 0)) // { //
fprintf(stderr, "\n\t ERR: target position should be <=INT_MAX and
non-zero positive value\n"); // return -1; // } // // if(argpnElem ==
NULL) // { // fprintf(stderr, "\n\t ERR: no memory allocated to store
the element at target position in the input list\n"); // return
-1; // } // // Node *pFwdNode,*pLagNode; // int nCurrentPos = 1; // //
pFwdNode = argpRoot; // pLagNode = NULL; // // while(pFwdNode) // { //
if(nCurrentPos == nTargetPos) // { // pLagNode = argpRoot; //
break; // } // pFwdNode = pFwdNode->pNextNode; // nCurrentPos+
+; // } // // if(!pLagNode) // { // fprintf(stderr, "\n\t ERR: target
position specified is non-existent for the current list\n"); //
*argpnElem = -1; // return -1; // } // // while(pFwdNode-
>pNextNode) // { // pLagNode = pLagNode->pNextNode; // pFwdNode
= pFwdNode->pNextNode; // } // *argpnElem = pLagNode->nElem; //
return 1; // } // int main() // { // Node *pRoot = NULL; // int
nNumElems = 0; // int nCurElem; // unsigned int unTestCaseId; // int
nTargetPos; // int i; // // while(!feof(stdin)) // { //
fscanf(stdin,"---\n"); // fprintf(stdout,"---\n"); //
fscanf(stdin,"NumOfElems :%d\n",&nNumElems); //
fprintf(stdout,"NumOfElems :%d\n",nNumElems); //
fflush(stdout); // for(i=0;i // { //
fscanf(stdin,"%d,",&nCurElem); //
pushElem(&pRoot,nCurElem); // } // printElems(pRoot); //
fflush(stdout); // fscanf(stdin,"\nTarget Position :%d
\n",&nTargetPos); // fprintf(stdout,"\nTarget Position :%d
\n",nTargetPos); // fflush(stdout); //
if(findElemFromListEnd(pRoot,nTargetPos,&nCurElem)<0) // { //
fprintf(stdout,"ERROR\n"); // // } // else // { //
fprintf(stdout,"Element:%d\n",nCurElem); // } // fscanf(stdin,"---
\n"); // fprintf(stdout,"---\n"); // fflush(stdout); // //
deleteList(&pRoot); // } // return 0; // }<a href="http://
meami.org/gibraltar.htm" class="external autonumber"
rel="nofollow">[1]</a></code></p>

<p>NP-complete problems are studied because the ability to quickly
verify solutions to a problem (NP) seems to correlate with the ability
to quickly solve that problem (<a href="/wiki/P_(complexity)" title="P
(complexity)">P</a>). It is not known whether every problem in NP can
be quickly solved—this is called the <a href="/wiki/P_%3D_NP_problem"
title="P = NP problem" class="mw-redirect">P = NP problem</a>. But if
<i>any single problem</i> in NP-complete can be solved quickly, then
<i>every problem in NP</i> can also be quickly solved, because the
definition of an NP-complete problem states that every problem in NP
must be quickly reducible to every problem in NP-complete (that is, it
can be reduced in polynomial time). Because of this, it is often said
that the NP-complete problems are <i>harder</i> or <i>more difficult</
i> than NP problems in general.</p>

<h2><span class="editsection">[<a href="/w/index.php?title=NP-
complete&action=edit&section=2" title="Edit section: Formal
definition of NP-completeness">edit</a>]</span> <span class="mw-
headline" id="Formal_definition_of_NP-completeness">Formal definition
of NP-completeness</span></h2>
<div class="rellink relarticle mainarticle">Main article: <a href="/
wiki/P_%3D_NP_problem#Formal_definition_for_NP-completeness" title="P
= NP problem" class="mw-redirect">formal definition for NP-
completeness (article <i>P = NP</i>)</a></div>
<p>A decision problem <img class="tex" alt="\scriptstyle C"
src="http://upload.wikimedia.org/math/f/c/7/
fc783207375c0abb99cfb79841b1708d.png" /> is NP-complete if:</p>
<ol>
<li><img class="tex" alt="\scriptstyle C" src="http://
upload.wikimedia.org/math/f/c/7/fc783207375c0abb99cfb79841b1708d.png" /
> is in NP, and</li>

<li>Every problem in NP is <a href="/wiki/Reduction_(complexity)"
title="Reduction (complexity)">reducible</a> to <img class="tex"
alt="\scriptstyle C" src="http://upload.wikimedia.org/math/f/c/7/
fc783207375c0abb99cfb79841b1708d.png" /> in polynomial time.</li>
</ol>
<p><img class="tex" alt="\scriptstyle C" src="http://
upload.wikimedia.org/math/f/c/7/fc783207375c0abb99cfb79841b1708d.png" /
> can be shown to be in NP by demonstrating that a candidate solution
to <img class="tex" alt="\scriptstyle C" src="http://
upload.wikimedia.org/math/f/c/7/fc783207375c0abb99cfb79841b1708d.png" /
> can be verified in polynomial time.</p>
<p>A problem <img class="tex" alt="\scriptstyle K" src="http://
upload.wikimedia.org/math/5/8/a/58a0d43f50180ea2c46c506e745f0e8d.png" /
> is reducible to <img class="tex" alt="\scriptstyle C" src="http://
upload.wikimedia.org/math/f/c/7/fc783207375c0abb99cfb79841b1708d.png" /
> if there is a polynomial-time many-one reduction, a <a href="/wiki/
Deterministic_algorithm" title="Deterministic algorithm">deterministic
algorithm</a> which transforms any instance <img class="tex"
alt="\scriptstyle k \in K" src="http://upload.wikimedia.org/math/f/f/3/
ff350c15776a952c12dde81ac71c5d15.png" /> into an instance <img
class="tex" alt="\scriptstyle c \in C" src="http://
upload.wikimedia.org/math/c/c/d/ccd054fd2c7efcd5d40f843387eaf1c2.png" /
>, such that the answer to <img class="tex" alt="\scriptstyle c"
src="http://upload.wikimedia.org/math/
7/4/8/748313066baf5e80e875d513a18604cd.png" /> is <i>yes</i> if and
only if the answer to <img class="tex" alt="\scriptstyle k"
src="http://upload.wikimedia.org/math/6/d/
2/6d2638f3b017bed72452bddbc28cbd6a.png" /> is <i>yes</i>. To prove
that an NP problem <img class="tex" alt="\scriptstyle C" src="http://
upload.wikimedia.org/math/f/c/7/fc783207375c0abb99cfb79841b1708d.png" /
> is in fact an NP-complete problem it is sufficient to show that an
already known NP-complete problem reduces to <img class="tex"
alt="\scriptstyle C" src="http://upload.wikimedia.org/math/f/c/7/
fc783207375c0abb99cfb79841b1708d.png" />.</p>

<p>Note that a problem satisfying condition 2 is said to be <a href="/
wiki/NP-hard" title="NP-hard">NP-hard</a>, whether or not it satisfies
condition 1.</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 <img class="tex" alt="\scriptstyle C" src="http://
upload.wikimedia.org/math/f/c/7/fc783207375c0abb99cfb79841b1708d.png" /
>, we could solve all problems in NP in polynomial time.</p>
<h2><span class="editsection">[<a href="/w/index.php?title=NP-
complete&action=edit&section=3" title="Edit section:
Background">edit</a>]</span> <span class="mw-headline"
id="Background">Background</span></h2>

<p>The concept of <i>NP-complete</i> was introduced in 1971 by <a
href="/wiki/Stephen_Cook" title="Stephen Cook">Stephen Cook</a> in a
paper entitled <i>The <a href="/wiki/Complexity"
title="Complexity">complexity</a> of theorem-proving procedures</i> on
pages 151-158 of the <i>Proceedings of the 3rd Annual ACM Symposium on
Theory of Computing</i>, though the term <i>NP-complete</i> did not
appear anywhere in his paper. At that <a href="/wiki/Computer_science"
title="Computer science">computer science</a> conference, there was a
fierce debate among the computer scientists about whether NP-complete
problems could be solved in polynomial time on a <a href="/wiki/
Deterministic" title="Deterministic" class="mw-
redirect">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 <a href="/wiki/Run_time_(computing)"
title="Run time (computing)">solvable</a> 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. 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"
title="Unsolved problems of mathematics" class="mw-redirect">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 to anyone
who has a formal proof that P=NP or that P≠NP.</p>
<p>In the celebrated <a href="/wiki/Cook%27s_theorem" title="Cook's
theorem" class="mw-redirect">Cook-Levin theorem</a> (independently
proved by <a href="/wiki/Leonid_Levin" title="Leonid Levin">Leonid
Levin</a>), Cook proved that the <a href="/wiki/
Boolean_satisfiability_problem" title="Boolean satisfiability
problem">Boolean satisfiability problem</a> is NP-complete (a simpler,
but still highly technical <a href="/wiki/
Proof_that_Boolean_satisfiability_problem_is_NP-complete" title="Proof
that Boolean satisfiability problem is NP-complete" class="mw-
redirect">proof of this</a> is available). In 1972, <a href="/wiki/
Richard_Karp" 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 Cook's 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="/wiki/Michael_Garey" title="Michael Garey">Garey</a> and <a
href="/wiki/David_S._Johnson" title="David S. Johnson">Johnson's</a>
1979 book <i>Computers and Intractability: A Guide to NP-Completeness</
i>.</p>

<h2><span class="editsection">[<a href="/w/index.php?title=NP-
complete&action=edit&section=4" title="Edit section: NP-
complete problems">edit</a>]</span> <span class="mw-headline" id="NP-
complete_problems">NP-complete problems</span></h2>
<div class="rellink relarticle mainarticle">Main article: <a href="/
wiki/List_of_NP-complete_problems" title="List of NP-complete
problems">List of NP-complete problems</a></div>
<div class="thumb tright">
<div class="thumbinner" style="width:222px;"><a href="/wiki/
File:Relative_NPC_chart.PNG" class="image"><img alt="" src="http://
upload.wikimedia.org/wikipedia/en/thumb/2/23/Relative_NPC_chart.PNG/
220px-Relative_NPC_chart.PNG" width="220" height="371"
class="thumbimage" /></a>
<div class="thumbcaption">
<div class="magnify"><a href="/wiki/File:Relative_NPC_chart.PNG"
class="internal" title="Enlarge"><img src="http://bits.wikimedia.org/
skins-1.5/common/images/magnify-clip.png" width="15" height="11"
alt="" /></a></div>
Some NP-complete problems, indicating the <a href="/wiki/
Reduction_(complexity)" title="Reduction (complexity)">reductions</a>
typically used to prove their NP-completeness</div>

</div>
</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" title="Isomorphic" class="mw-redirect">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 <b>hard</b>, but isn't thought to be NP-complete.</p>

<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>
<div style="-moz-column-count:2; column-count:2;">
<ul>
<li><a href="/wiki/Boolean_satisfiability_problem" title="Boolean
satisfiability problem">Boolean satisfiability problem (Sat.)</a></li>
<li><a href="/wiki/N-puzzle" title="N-puzzle" class="mw-redirect">N-
puzzle</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></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" title="Vertex cover problem"
class="mw-redirect">Vertex cover problem</a></li>
<li><a href="/wiki/Independent_set_problem" title="Independent set
problem" class="mw-redirect">Independent set problem</a></li>
<li><a href="/wiki/Dominating_set_problem" title="Dominating set
problem" class="mw-redirect">Dominating set problem</a></li>
<li><a href="/wiki/Graph_coloring_problem" title="Graph coloring
problem" class="mw-redirect">Graph coloring problem</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, an arrow from one problem to another
indicates the direction of the reduction. Note that this diagram is
misleading as a description of the mathematical relationship between
these problems, as there exists a polynomial-time reduction 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" title="3-satisfiability" class="mw-redirect">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, <a href="/wiki/NL-
complete" title="NL-complete">NL-complete</a>), and 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.<a href="http://
meami.org/gibraltar.htm" class="external autonumber"
rel="nofollow">[2]</a></p>

<h2><span class="editsection">[<a href="/w/index.php?title=NP-
complete&action=edit&section=5" title="Edit section: Solving
NP-complete problems">edit</a>]</span> <span class="mw-headline"
id="Solving_NP-complete_problems">Solving NP-complete problems</span></
h2>
<p>At present, all known algorithms for NP-complete problems require
time that is <a href="/wiki/Superpolynomial" title="Superpolynomial"
class="mw-redirect">superpolynomial</a> in the input size, 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 an "almost" 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" title="Running time" class="mw-
redirect">running time</a>, and allow the algorithm to fail with some
small probability. See <a href="/wiki/Monte_Carlo_method" title="Monte
Carlo method">Monte Carlo method</a>.</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)" class="mw-redirect">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 <img
class="tex" alt="\scriptstyle O(n\log n)" src="http://
upload.wikimedia.org/math/8/5/4/85475fa30b59d8b8f76fb930224a694d.png" /
> <a href="/wiki/Greedy_coloring" title="Greedy coloring">greedy
coloring algorithm</a> used for <a href="/wiki/Graph_coloring_problem"
title="Graph coloring problem" class="mw-redirect">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="/w/index.php?title=Graph-
coloring_global_register_allocation&action=edit&redlink=1"
class="new" title="Graph-coloring global register allocation (page
does not exist)">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" title="RISC"
class="mw-redirect">RISC</a> machines have a fairly large number of
general-purpose registers, even a heuristic approach is effective for
this application.</p>

<h2><span class="editsection">[<a href="/w/index.php?title=NP-
complete&action=edit&section=6" title="Edit section:
Completeness under different types of reduction">edit</a>]</span>
<span class="mw-headline"
id="Completeness_under_different_types_of_reduction">Completeness
under different types of reduction</span></h2>
<p>In the definition of NP-complete given above, the term
<i>reduction</i> was used in the technical meaning of a polynomial-
time many-one reduction.</p>
<p>Another type of reduction is polynomial-time Turing reduction. A
problem <img class="tex" alt="\scriptstyle X" src="http://
upload.wikimedia.org/math/5/1/c/51cea10940d0755e9c5b34dff3c328fd.png" /
> is polynomial-time Turing-reducible to a problem <img class="tex"
alt="\scriptstyle Y" src="http://upload.wikimedia.org/math/f/6/2/
f622e012a22e65b1660aaff8a2fcbf21.png" /> if, given a subroutine that
solves <img class="tex" alt="\scriptstyle Y" src="http://
upload.wikimedia.org/math/f/6/2/f622e012a22e65b1660aaff8a2fcbf21.png" /
> in polynomial time, one could write a program that calls this
subroutine and solves <img class="tex" alt="\scriptstyle X"
src="http://upload.wikimedia.org/math/5/1/c/
51cea10940d0755e9c5b34dff3c328fd.png" /> 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. If the two concepts were the same, then it would follow
that NP = <a href="/wiki/Co-NP" title="Co-NP">co-NP</a>. This holds
because by their definition the classes of NP-complete and co-NP-
complete problems under Turing reductions are the same and because
these classes are both supersets of the same classes defined with many-
one reductions. So if both definitions of NP-completeness are equal
then there is a co-NP-complete problem (under both definitions) such
as for example the complement of the boolean satisfiability problem
that is also NP-complete (under both definitions). This implies that
NP = co-NP as is shown in the proof in the co-NP article. Although
whether NP = co-NP is an open question it is considered unlikely and
therefore it is also unlikely that the two definitions of NP-
completeness are equivalent.</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" title="Logarithmic-space many-one reduction" class="mw-
redirect">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" title="Logarithmic space" class="mw-
redirect">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.</p>
<h2><span class="editsection">[<a href="/w/index.php?title=NP-
complete&action=edit&section=7" title="Edit section:
Naming">edit</a>]</span> <span class="mw-headline" id="Naming">Naming</
span></h2>

<p>According to <a href="/wiki/Don_Knuth" title="Don Knuth" class="mw-
redirect">Don 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" title="Galley proofs" class="mw-
redirect">galley proofs</a> for the book (from "polynomially-
complete"), in accordance with the results of a poll by the <a href="/
wiki/Theoretical_Computer_Science" title="Theoretical Computer
Science">Theoretical Computer Science</a> community (other options
included "<a href="/wiki/Labours_of_Hercules" title="Labours of
Hercules">Herculean</a>", "<a href="/wiki/Augeas"
title="Augeas">Augean</a>" and "NP-hard" problems).<sup
id="cite_ref-0" class="reference"><a href="#cite_note-0"><span>[</
span>1<span>]</span></a></sup> For other options considered at
different times (including <a href="/wiki/Kenneth_Steiglitz"
title="Kenneth Steiglitz">Steiglitz</a>'s "hard-boiled" in honor of
Cook) see <a href="http://www.cs.princeton.edu/~wayne/kleinberg-tardos/
08np-complete-2x2.pdf" class="external autonumber" rel="nofollow">[3]</
a>.</p>

<h2><span class="editsection">[<a href="/w/index.php?title=NP-
complete&action=edit&section=8" title="Edit section: See
also">edit</a>]</span> <span class="mw-headline" id="See_also">See
also</span></h2>
<ul>
<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/Almost_complete" title="Almost complete" class="mw-
redirect">Almost complete</a></li>
<li><a href="/wiki/Ladner%27s_theorem" title="Ladner's theorem"
class="mw-redirect">Ladner's theorem</a></li>
<li><a href="/wiki/Strongly_NP-complete" title="Strongly NP-
complete">Strongly NP-complete</a></li>
<li><a href="/wiki/P_%3D_NP_problem" title="P = NP problem" class="mw-
redirect">P = NP problem</a></li>

<li><a href="/wiki/NP-hard" title="NP-hard">NP-hard</a></li>
</ul>
<h2><span class="editsection">[<a href="/w/index.php?title=NP-
complete&action=edit&section=9" title="Edit section:
References">edit</a>]</span> <span class="mw-headline"
id="References">References</span></h2>
<div class="references-small">
<ol class="references">
<li id="cite_note-0"><b><a href="#cite_ref-0">^</a></b> <a href="/wiki/
Don_Knuth" title="Don Knuth" class="mw-redirect">Don Knuth</a>, Tracy
Larrabee, and Paul M. Roberts, <i><a href="http://tex.loria.fr/
typographie/mathwriting.pdf" class="external text"
rel="nofollow">Mathematical Writing</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).</li>

</ol>
</div>
<ul>
<li><span class="citation book"><a href="/wiki/Michael_Garey"
title="Michael Garey">Garey, M.R.</a>; <a href="/wiki/
David_S._Johnson" title="David S. Johnson">Johnson, D.S.</a> (1979).
<i><a href="/wiki/
Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-
Completeness" title="Computers and Intractability: A Guide to the
Theory of NP-Completeness">Computers and Intractability: A Guide to
the Theory of NP-Completeness</a></i>. New York: W.H. Freeman. <a
href="/wiki/International_Standard_Book_Number" title="International
Standard Book Number">ISBN</a> <a href="/wiki/Special:BookSources/
0-7167-1045-5" title="Special:BookSources/
0-7167-1045-5">0-7167-1045-5</a>.</span><span class="Z3988"
title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=book&rft.btitle=%5B%5BComputers+and
+Intractability%3A+A+Guide+to+the+Theory+of+NP-Completeness%5D
%5D&rft.aulast=Garey&rft.aufirst=M.R.&rft.au=Garey%2C
%26%2332%3BM.R.&rft.date=1979&rft.place=New
+York&rft.pub=W.H.
+Freeman&rft.isbn=0-7167-1045-5&rfr_id=info:sid/
en.wikipedia.org:NP-complete"><span style="display: none;"> </
span></span> This book is a classic, developing the theory, then
cataloguing <i>many</i> NP-Complete problems.</li>

<li><span class="citation book"><a href="/wiki/Stephen_A._Cook"
title="Stephen A. Cook" class="mw-redirect">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/Digital_object_identifier"
title="Digital object identifier">doi</a>:<a href="http://dx.doi.org/
10.1145%2F800157.805047" class="external text"
rel="nofollow">10.1145/800157.805047</a>.</span><span class="Z3988"
title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=bookitem&rft.btitle=The+complexity+of+theorem
+proving+procedures&rft.atitle=Proceedings%2C+Third+Annual+ACM
+Symposium+on+the+Theory+of+Computing%2C+ACM%2C+New
+York&rft.aulast=Cook&rft.aufirst=S.A.&rft.au=Cook%2C
%26%2332%3BS.A.&rft.date=1971&rft.pages=pp.%26nbsp
%3B151%E2%80%93158&rft_id=info:doi/
10.1145%2F800157.805047&rfr_id=info:sid/en.wikipedia.org:NP-
complete"><span style="display: none;"> </span></span></li>
<li><span class="citation web">Dunne, P.E. <a href="http://
www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html"
class="external text" rel="nofollow">"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="printonly">. <a
href="http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/
annotated_np.html" class="external free" rel="nofollow">http://
www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html</a></span><span
class="reference-accessdate">. Retrieved 2008-06-21</span>.</
span><span class="Z3988"
title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=bookitem&rft.btitle=An+annotated+list+of
+selected+NP-complete
+problems&rft.atitle=&rft.aulast=Dunne&rft.aufirst=P.E&rft.au=Dunne
%2C%26%2332%3BP.E&rft.pub=COMP202%2C+Dept.+of+Computer+Science%2C+
%5B%5BUniversity+of+Liverpool%5D%5D&rft_id=http%3A%2F
%2Fwww.csc.liv.ac.uk%2F%7Eped%2Fteachadmin
%2FCOMP202%2Fannotated_np.html&rfr_id=info:sid/en.wikipedia.org:NP-
complete"><span style="display: none;"> </span></span></li>

<li><span class="citation web">Crescenzi, P.; Kann, V.; Halldórsson,
M.; <a href="/wiki/Marek_Karpinski" title="Marek Karpinski">Karpinski,
M.</a>; Woeginger, G. <a href="http://www.nada.kth.se/~viggo/
problemlist/compendium.html" class="external text" rel="nofollow">"A
compendium of NP optimization problems"</a>. KTH NADA, Stockholm<span
class="printonly">. <a href="http://www.nada.kth.se/~viggo/problemlist/
compendium.html" class="external free" rel="nofollow">http://
www.nada.kth.se/~viggo/problemlist/compendium.html</a></span><span
class="reference-accessdate">. Retrieved 2008-06-21</span>.</
span><span class="Z3988"
title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=bookitem&rft.btitle=A+compendium+of+NP
+optimization
+problems&rft.atitle=&rft.aulast=Crescenzi&rft.aufirst=P.&rft.au=Crescenzi
%2C%26%2332%3BP.&rft.pub=KTH+NADA%2C+Stockholm&rft_id=http%3A
%2F%2Fwww.nada.kth.se%2F%7Eviggo%2Fproblemlist
%2Fcompendium.html&rfr_id=info:sid/en.wikipedia.org:NP-
complete"><span style="display: none;"> </span></span></li>
<li><span class="citation web">Dahlke, K. <a href="http://
www.mathreference.com/lan-cx-np,intro.html" class="external text"
rel="nofollow">"NP-complete problems"</a>. <i>Math Reference Project</
i><span class="printonly">. <a href="http://www.mathreference.com/lan-
cx-np,intro.html" class="external free" rel="nofollow">http://
www.mathreference.com/lan-cx-np,intro.html</a></span><span
class="reference-accessdate">. Retrieved 2008-06-21</span>.</
span><span class="Z3988"
title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=bookitem&rft.btitle=NP-complete
+problems&rft.atitle=Math+Reference
+Project&rft.aulast=Dahlke&rft.aufirst=K&rft.au=Dahlke%2C
%26%2332%3BK&rft_id=http%3A%2F%2Fwww.mathreference.com%2Flan-cx-np
%2Cintro.html&rfr_id=info:sid/en.wikipedia.org:NP-complete"><span
style="display: none;"> </span></span></li>

<li><span class="citation web">Karlsson, R. <a href="http://
www.cs.lth.se/home/Rolf_Karlsson/bk/lect8.pdf" class="external text"
rel="nofollow">"Lecture 8: NP-complete problems"</a> (PDF). Dept. of
Computer Science, Lund University, Sweden<span class="printonly">. <a
href="http://www.cs.lth.se/home/Rolf_Karlsson/bk/lect8.pdf"
class="external free" rel="nofollow">http://www.cs.lth.se/home/
Rolf_Karlsson/bk/lect8.pdf</a></span><span class="reference-
accessdate">. Retrieved 2008-06-21</span>.</span><span class="Z3988"
title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=bookitem&rft.btitle=Lecture+8%3A+NP-complete
+problems&rft.atitle=&rft.aulast=Karlsson&rft.aufirst=R&rft.au=Karlsson
%2C%26%2332%3BR&rft.pub=Dept.+of+Computer+Science%2C+Lund
+University%2C+Sweden&rft_id=http%3A%2F%2Fwww.cs.lth.se%2Fhome
%2FRolf_Karlsson%2Fbk%2Flect8.pdf&rfr_id=info:sid/
en.wikipedia.org:NP-complete"><span style="display: none;"> </
span></span></li>
<li><span class="citation web">Sun, H.M. <a href="http://
is.cs.nthu.edu.tw/course/2008Spring/cs431102/hmsunCh08.ppt"
class="external text" rel="nofollow">"The theory of NP-completeness"</
a> (PPT). 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<span class="printonly">. <a href="http://is.cs.nthu.edu.tw/
course/2008Spring/cs431102/hmsunCh08.ppt" class="external free"
rel="nofollow">http://is.cs.nthu.edu.tw/course/2008Spring/cs431102/
hmsunCh08.ppt</a></span><span class="reference-accessdate">. Retrieved
2008-06-21</span>.</span><span class="Z3988"
title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=bookitem&rft.btitle=The+theory+of+NP-
completeness&rft.atitle=&rft.aulast=Sun&rft.aufirst=H.M&rft.au=Sun
%2C%26%2332%3BH.M&rft.pub=Information+Security+Laboratory%2C+Dept.
+of+Computer+Science%2C+%5B%5BNational+Tsing+Hua+University%5D%5D%2C
+Hsinchu+City%2C+Taiwan&rft_id=http%3A%2F%2Fis.cs.nthu.edu.tw
%2Fcourse%2F2008Spring%2Fcs431102%2FhmsunCh08.ppt&rfr_id=info:sid/
en.wikipedia.org:NP-complete"><span style="display: none;"> </
span></span></li>

<li><span class="citation web">Jiang, J.R. <a href="http://
www.csie.ncu.edu.tw/%7Ejrjiang/alg2006/NPC-3.ppt" class="external
text" rel="nofollow">"The theory of NP-completeness"</a> (PPT). 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="printonly">. <a href="http://www.csie.ncu.edu.tw/%7Ejrjiang/
alg2006/NPC-3.ppt" class="external free" rel="nofollow">http://
www.csie.ncu.edu.tw/%7Ejrjiang/alg2006/NPC-3.ppt</a></span><span
class="reference-accessdate">. Retrieved 2008-06-21</span>.</
span><span class="Z3988"
title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=bookitem&rft.btitle=The+theory+of+NP-
completeness&rft.atitle=&rft.aulast=Jiang&rft.aufirst=J.R&rft.au=Jiang
%2C%26%2332%3BJ.R&rft.pub=Dept.+of+Computer+Science+and+Information
+Engineering%2C+%5B%5BNational+Central+University%5D%5D%2C+Jhongli+City
%2C+Taiwan&rft_id=http%3A%2F%2Fwww.csie.ncu.edu.tw%2F%257Ejrjiang
%2Falg2006%2FNPC-3.ppt&rfr_id=info:sid/en.wikipedia.org:NP-
complete"><span style="display: none;"> </span></span></li>
<li><span class="citation book"><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" title="Ronald L. Rivest"
class="mw-redirect">Rivest, R.L.</a>; <a href="/wiki/Clifford_Stein"
title="Clifford Stein">Stein, C.</a> (2001). <i><a href="/wiki/
Introduction_to_Algorithms" title="Introduction to
Algorithms">Introduction to Algorithms</a></i> (2nd ed.). MIT Press
and McGraw-Hill. Chapter 34: NP–Completeness, pp. 966–1021. <a href="/
wiki/International_Standard_Book_Number" title="International Standard
Book Number">ISBN</a> <a href="/wiki/Special:BookSources/
0-262-03293-7" title="Special:BookSources/
0-262-03293-7">0-262-03293-7</a>.</span><span class="Z3988"
title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=book&rft.btitle=%5B%5BIntroduction+to
+Algorithms%5D
%5D&rft.aulast=Cormen&rft.aufirst=T.H.&rft.au=Cormen%2C
%26%2332%3BT.H.&rft.date=2001&rft.pages=Chapter+34%3A+NP
%E2%80%93Completeness%2C+pp.
+966%E2%80%931021&rft.edition=2nd&rft.pub=MIT+Press+and+McGraw-
Hill&rft.isbn=0-262-03293-7&rfr_id=info:sid/
en.wikipedia.org:NP-complete"><span style="display: none;"> </
span></span></li>

<li><span class="citation book"><a href="/wiki/Michael_Sipser"
title="Michael Sipser">Sipser, M.</a> (1997). <i>Introduction to the
Theory of Computation</i>. PWS Publishing. Sections 7.4–7.5 (NP-
completeness, Additional NP-complete Problems), pp. 248–271.</
span><span class="Z3988"
title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=book&rft.btitle=Introduction+to+the+Theory+of
+Computation&rft.aulast=Sipser&rft.aufirst=M.&rft.au=Sipser
%2C%26%2332%3BM.&rft.date=1997&rft.pages=Sections
+7.4%E2%80%937.5+%28NP-completeness%2C+Additional+NP-complete+Problems
%29%2C+pp.+248%E2%80%93271&rft.pub=PWS
+Publishing&rfr_id=info:sid/en.wikipedia.org:NP-complete"><span
style="display: none;"> </span></span></li>
<li><span class="citation book"><a href="/wiki/Christos_Papadimitriou"
title="Christos Papadimitriou">Papadimitriou, C.</a> (1994).
<i>Computational Complexity</i> (1st ed.). Addison Wesley. Chapter 9
(NP-complete problems), pp. 181–218. <a href="/wiki/
International_Standard_Book_Number" title="International Standard Book
Number">ISBN</a> <a href="/wiki/Special:BookSources/0201530821"
title="Special:BookSources/0201530821">0201530821</a>.</span><span
class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi
%2Ffmt%3Akev%3Amtx
%3Abook&rft.genre=book&rft.btitle=Computational
+Complexity&rft.aulast=Papadimitriou&rft.aufirst=C.&rft.au=Papadimitriou
%2C%26%2332%3BC.&rft.date=1994&rft.pages=Chapter+9+%28NP-
complete+problems%29%2C+pp.
+181%E2%80%93218&rft.edition=1st&rft.pub=Addison
+Wesley&rft.isbn=0201530821&rfr_id=info:sid/
en.wikipedia.org:NP-complete"><span style="display: none;"> </
span></span></li>
<li><a href="http://www.ics.uci.edu/~eppstein/cgt/hard.html"
class="external text" rel="nofollow">Computational Complexity of Games
and Puzzles</a></li>

<li><a href="http://arxiv.org/abs/cs.CC/0210020" class="external text"
rel="nofollow">Tetris is Hard, Even to Approximate</a></li>
<li><a href="http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm"
class="external text" rel="nofollow">Minesweeper is NP-complete!</a></
li>
</ul>
<h2><span class="editsection">[<a href="/w/index.php?title=NP-
complete&action=edit&section=10" title="Edit section: Further
reading">edit</a>]</span> <span class="mw-headline"
id="Further_reading">Further reading</span></h2>
<ul>
<li><a href="/wiki/Scott_Aaronson" title="Scott Aaronson">Scott
Aaronson</a>, <i><a href="http://arxiv.org/abs/quant-ph/0502072"
class="external text" rel="nofollow">NP-complete Problems and Physical
Reality</a></i>, ACM <a href="/wiki/SIGACT" title="SIGACT" class="mw-
redirect">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 href="http://people.cs.uchicago.edu/~fortnow/papers/pnp-
cacm.pdf" class="external text" rel="nofollow">The status of the P
versus NP problem</a></i>, <a href="/wiki/Commun._ACM" title="Commun.
ACM" class="mw-redirect">Commun. ACM</a>, Vol. 52, No. 9. (2009),
pp. 78-86.</li>
</ul>
<table class="navbox" cellspacing="0" style=";">
<tr>
<td style="padding:2px;">
<table cellspacing="0" class="nowraplinks collapsible autocollapse"
style="width:100%;background:transparent;color:inherit;;">
<tr>
<th style=";" colspan="2" class="navbox-title">
<div style="float:left; width:6em;text-align:left;">
<div class="noprint plainlinks navbar" style="background:none; padding:
0; font-weight:normal;;;border:none;; font-size:xx-small;"><a href="/
wiki/Template:ComplexityClasses"
title="Template:ComplexityClasses"><span title="View this template"
style=";;border:none;">v</span></a> <span style="font-size:
80%;">•</span> <a href="/wiki/Template_talk:ComplexityClasses"
title="Template talk:ComplexityClasses"><span title="Discuss this
template" style=";;border:none;">d</span></a> <span style="font-
size:80%;">•</span> <a href="http://en.wikipedia.org/w/index.php?
title=Template:ComplexityClasses&action=edit" class="external
text" rel="nofollow"><span title="Edit this template"
style=";;border:none;;">e</span></a></div>

</div>
<span class="" style="font-size:110%;">Important <a href="/wiki/
Complexity_class" title="Complexity class">complexity classes</a> (<a
href="/wiki/List_of_complexity_classes" title="List of complexity
classes">more</a>)</span></th>
</tr>
<tr style="height:2px;">
<td></td>
</tr>
<tr>
<td class="navbox-group" style=";;">Classes considered feasible</td>
<td style="text-align:left;border-left-width:2px;border-left-
style:solid;width:100%;padding:0px;;;" class="navbox-list navbox-odd">
<div style="padding:0em 0.25em"><a href="/wiki/DLOGTIME"
title="DLOGTIME">DLOGTIME</a> • <a href="/wiki/AC0"
title="AC0">AC<sup>0</sup></a> • <a href="/wiki/L_(complexity)"
title="L (complexity)">L</a> • <a href="/wiki/SL_(complexity)"
title="SL (complexity)">SL</a> • <a href="/wiki/RL_(complexity)"
title="RL (complexity)">RL</a> • <a href="/wiki/NL_(complexity)"
title="NL (complexity)">NL</a> • <a href="/wiki/NC_(complexity)"
title="NC (complexity)">NC</a> • <a href="/wiki/SC_(complexity)"
title="SC (complexity)">SC</a> • <a href="/wiki/P_(complexity)"
title="P (complexity)">P</a> (<a href="/wiki/P-complete" title="P-
complete">P-complete</a>) • <a href="/wiki/ZPP_(complexity)"
title="ZPP (complexity)">ZPP</a> • <a href="/wiki/
RP_(complexity)" title="RP (complexity)">RP</a> • <a href="/wiki/
BPP" title="BPP">BPP</a> • <a href="/wiki/BQP" title="BQP">BQP</
a> </div>

</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<td class="navbox-group" style=";;">Classes suspected to be
infeasible</td>
<td style="text-align:left;border-left-width:2px;border-left-
style:solid;width:100%;padding:0px;;;" class="navbox-list navbox-
even">
<div style="padding:0em 0.25em"><a href="/wiki/UP_(complexity)"
title="UP (complexity)">UP</a> • <a href="/wiki/NP_(complexity)"
title="NP (complexity)">NP</a> (<strong class="selflink">NP-complete</
strong> · <a href="/wiki/NP-hard" title="NP-hard">NP-hard</a> ·
<a href="/wiki/Co-NP" title="Co-NP">co-NP</a> · <a href="/wiki/Co-
NP-complete" title="Co-NP-complete">co-NP-complete</a>) • <a href="/
wiki/Arthur%E2%80%93Merlin_protocol" title="Arthur–Merlin
protocol">AM</a> • <a href="/wiki/PH_(complexity)" title="PH
(complexity)">PH</a> • <a href="/wiki/PP_(complexity)" title="PP
(complexity)">PP</a> • <a href="/wiki/Sharp-P" title="Sharp-P">#P</a>
(<a href="/wiki/Sharp-P-complete" title="Sharp-P-complete">#P-
complete</a>) • <a href="/wiki/IP_(complexity)" title="IP
(complexity)">IP</a> • <a href="/wiki/PSPACE"
title="PSPACE">PSPACE</a> (<a href="/wiki/PSPACE-complete"
title="PSPACE-complete">PSPACE-complete</a>)</div>

</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<td class="navbox-group" style=";;">Classes considered infeasible</td>
<td style="text-align:left;border-left-width:2px;border-left-
style:solid;width:100%;padding:0px;;;" class="navbox-list navbox-odd">
<div style="padding:0em 0.25em"><a href="/wiki/EXPTIME"
title="EXPTIME">EXPTIME</a> • <a href="/wiki/NEXPTIME"
title="NEXPTIME">NEXPTIME</a> • <a href="/wiki/EXPSPACE"
title="EXPSPACE">EXPSPACE</a> • <a href="/wiki/2-EXPTIME"
title="2-EXPTIME">2-EXPTIME</a> • <a href="/wiki/ELEMENTARY"
title="ELEMENTARY">ELEMENTARY</a> • <a href="/wiki/
PR_(complexity)" title="PR (complexity)">PR</a> • <a href="/wiki/
R_(complexity)" title="R (complexity)">R</a> • <a href="/wiki/
RE_(complexity)" title="RE (complexity)">RE</a> • <a href="/wiki/
ALL_(complexity)" title="ALL (complexity)">ALL</a></div>

</td>
</tr>
<tr style="height:2px">
<td></td>
</tr>
<tr>
<td class="navbox-group" style=";;">Families of complexity classes</
td>
<td style="text-align:left;border-left-width:2px;border-left-
style:solid;width:100%;padding:0px;;;" class="navbox-list navbox-
even">
<div style="padding:0em 0.25em"><a href="/wiki/DTIME"
title="DTIME">DTIME</a> • <a href="/wiki/NTIME"
title="NTIME">NTIME</a> • <a href="/wiki/DSPACE"
title="DSPACE">DSPACE</a> • <a href="/wiki/NSPACE"
title="NSPACE">NSPACE</a> • <a href="/wiki/
Probabilistically_checkable_proof" title="Probabilistically checkable
proof">Probabilistically checkable proof</a> • <a href="/wiki/
Interactive_proof_system" title="Interactive proof system">Interactive
proof system</a> </div>

</td>
</tr>
</table>
</td>
</tr>
</table>

<div class="printfooter">
Retrieved from "<a href="http://en.wikipedia.org/wiki/NP-
complete">http://en.wikipedia.org/wiki/NP-complete</a>"</div>

<div id='catlinks' class='catlinks'><div id="mw-normal-
catlinks"><a href="/wiki/Special:Categories"
title="Special:Categories">Categories</a>: <span dir='ltr'><a href="/
wiki/Category:NP-complete_problems" title="Category:NP-complete
problems">NP-complete problems</a></span> | <span dir='ltr'><a href="/
wiki/Category:Complexity_classes" title="Category:Complexity
classes">Complexity classes</a></span> | <span dir='ltr'><a href="/
wiki/Category:Mathematical_optimization" title="Category:Mathematical
optimization">Mathematical optimization</a></span></div></div>

<div class="visualClear"></div>
</div>

</div>


<div id="mw-head" class="noprint">

<div id="p-personal" class="">
<h5>Personal tools</h5>
<ul>

<li id="pt-prefswitch-link-anon"><a href="http://
en.wikipedia.org/w/index.php?
title=Special:UsabilityInitiativePrefSwitch&from=NP-complete"
title="Learn about new features" class="no-text-transform">New
features</a></li>
<li id="pt-login"><a href="/w/index.php?
title=Special:UserLogin&returnto=NP-complete" title="You are
encouraged to log in; however, it is not mandatory. [o]"
accesskey="o">Log in / create account</a></li>
</ul>
</div>

<div id="left-navigation">

<div id="p-namespaces" class="vectorTabs">
<h5>Namespaces</h5>

<ul>
<li id="ca-nstab-main" class="selected"><a href="/wiki/NP-
complete" title="View the content page [c]"
accesskey="c"><span>Article</span></a></li>
<li id="ca-talk"><a href="/wiki/Talk:NP-complete"
title="Discussion about the content page [t]"
accesskey="t"><span>Discussion</span></a></li>
</ul>
</div>

<div id="p-variants" class="vectorMenu emptyPortlet">
<h5><span>Variants</span><a href="#"></a></h5>

</div>
<div id="right-navigation">

<div id="p-views" class="vectorTabs">
<h5>Views</h5>
<ul>
<li id="ca-view" class="selected"><a href="/wiki/NP-complete"
><span>Read</span></a></li>
<li id="ca-edit"><a href="/w/index.php?title=NP-
complete&action=edit" title="You can edit this page. 
Please
use the preview button before saving. [e]" accesskey="e"><span>Edit</
span></a></li>
<li id="ca-history" class="collapsible "><a href="/w/index.php?
title=NP-complete&action=history" title="Past versions of this
page [h]" accesskey="h"><span>View history</span></a></li>
</ul>

</div>

<div id="p-cactions" class="vectorMenu emptyPortlet">
<h5><span>Actions</span><a href="#"></a></h5>
<div class="menu">
<ul>
</ul>
</div>

</div>

<div id="p-search">
<h5><label for="searchInput">Search</label></h5>
<form action="/w/index.php" id="searchform">
<input type='hidden' name="title" value="Special:Search"/>
<div id="simpleSearch">
<input id="searchInput" name="search" type="text" title="Search
Wikipedia [f]" accesskey="f" value="" />

</div>
</div>

<div class="portal" id='p-navigation'>
<h5>Navigation</h5>
<div class="body">
<ul>

<li id="n-mainpage-description"><a href="/wiki/Main_Page"
title="Visit the main page [z]" accesskey="z">Main page</a></li>
<li id="n-contents"><a href="/wiki/Portal:Contents" title="Guides
to browsing Wikipedia">Contents</a></li>
<li id="n-featuredcontent"><a href="/wiki/
Portal:Featured_content" title="Featured content — the best of
Wikipedia">Featured content</a></li>
<li id="n-currentevents"><a href="/wiki/Portal:Current_events"
title="Find background information on current events">Current events</
a></li>
<li id="n-randompage"><a href="/wiki/Special:Random" title="Load
a random article [x]" accesskey="x">Random article</a></li>
</ul>

</div>
</div>

<div class="portal" id='p-interaction'>
<h5>Interaction</h5>
<div class="body">

<ul>
<li id="n-aboutsite"><a href="/wiki/Wikipedia:About" title="Find
out about Wikipedia">About Wikipedia</a></li>
<li id="n-portal"><a href="/wiki/Wikipedia:Community_portal"
title="About the project, what you can do, where to find
things">Community portal</a></li>
<li id="n-recentchanges"><a href="/wiki/Special:RecentChanges"
title="The list of recent changes in the wiki [r]"
accesskey="r">Recent changes</a></li>
<li id="n-contact"><a href="/wiki/Wikipedia:Contact_us"
title="How to contact Wikipedia">Contact Wikipedia</a></li>
<li id="n-sitesupport"><a href="http://wikimediafoundation.org/
wiki/Support_Wikipedia/en" title="Support us">Donate to Wikipedia</a></
li>

<div class="portal" id="p-tb">
<h5>Toolbox</h5>
<div class="body">

<ul>
<li id="t-whatlinkshere"><a href="/wiki/Special:WhatLinksHere/NP-
complete" title="List of all English Wikipedia pages containing links
to this page [j]" accesskey="j">What links here</a></li>
<li id="t-recentchangeslinked"><a href="/wiki/
Special:RecentChangesLinked/NP-complete" title="Recent changes in
pages linked from this page [k]" accesskey="k">Related changes</a></
li>
<li id="t-upload"><a href="/wiki/
Wikipedia:Upload" title="Upload files [u]" accesskey="u">Upload file</
a></li>
<li id="t-specialpages"><a href="/wiki/
Special:SpecialPages" title="List of all special pages [q]"
accesskey="q">Special pages</a></li>
<li id="t-permalink"><a href="/w/index.php?title=NP-
complete&oldid=372100350" title="Permanent link to this revision
of the page">Permanent link</a></li>

<div class="portal" id='p-coll-print_export'>
<h5>Print/export</h5>
<div class="body">

<ul id="collectionPortletList"><li id="coll-create_a_book"><a
href="/w/index.php?
title=Special:Book&bookcmd=book_creator&referer=NP-complete"
title="Create a book or page collection" rel="nofollow">Create a book</
a></li><li id="coll-download-as-rl"><a href="/w/index.php?
title=Special:Book&bookcmd=render_article&arttitle=NP-
complete&oldid=372100350&writer=rl" title="Download a PDF
version of this wiki page" rel="nofollow">Download as PDF</a></li><li
id="t-print"><a href="/w/index.php?title=NP-
complete&printable=yes" title="Printable version of this page [p]"
accesskey="p">Printable version</a></li></ul> </div>
</div>

<div class="portal" id="p-lang">
<h5>Languages</h5>
<div class="body">

<ul>
<li class="interwiki-ar"><a href="http://ar.wikipedia.org/wiki/
%D9%85%D8%B3%D8%A3%D9%84%D8%A9_NP_%D9%83%D8%A7%D9%85%D9%84%D8%A9"
title="مسألة NP كاملة">العربية</a></li>
<li class="interwiki-ca"><a href="http://ca.wikipedia.org/wiki/NP-
complet" title="NP-complet">Català</a></li>
<li class="interwiki-cs"><a href="http://cs.wikipedia.org/wiki/NP-
%C3%BAplnost" title="NP-úplnost">Česky</a></li>
<li class="interwiki-da"><a href="http://da.wikipedia.org/wiki/NP-
komplet" title="NP-komplet">Dansk</a></li>
<li class="interwiki-de"><a href="http://de.wikipedia.org/wiki/NP-
Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">Deutsch</a></li>

<li class="interwiki-es"><a href="http://es.wikipedia.org/wiki/NP-
completo" title="NP-completo">Español</a></li>
<li class="interwiki-fa"><a href="http://fa.wikipedia.org/wiki/
%D8%A7%D9%86%E2%80%8C%D9%BE%DB%8C_%DA%A9%D8%A7%D9%85%D9%84"
title="ان‌پی کامل">فارسی</a></li>
<li class="interwiki-fr"><a href="http://fr.wikipedia.org/wiki/
Probl%C3%A8me_NP-complet" title="Problème NP-complet">Français</a></
li>
<li class="interwiki-ko"><a href="http://ko.wikipedia.org/wiki/NP-
%EC%99%84%EC%A0%84" title="NP-완전">한국어</a></li>
<li class="interwiki-it"><a href="http://it.wikipedia.org/wiki/NP-
Completo" title="NP-Completo">Italiano</a></li>
<li class="interwiki-nl"><a href="http://nl.wikipedia.org/wiki/NP-
volledig" title="NP-volledig">Nederlands</a></li>

<li class="interwiki-ja"><a href="http://ja.wikipedia.org/wiki/NP
%E5%AE%8C%E5%85%A8%E5%95%8F%E9%A1%8C" title="NP完全問題">日本語</a></li>
<li class="interwiki-no"><a href="http://no.wikipedia.org/wiki/NP-
komplett" title="NP-komplett">‪Norsk (bokmål)‬</a></li>
<li class="interwiki-nn"><a href="http://nn.wikipedia.org/wiki/NP-
komplett" title="NP-komplett">‪Norsk (nynorsk)‬</a></li>
<li class="interwiki-pl"><a href="http://pl.wikipedia.org/wiki/
Problem_NP-zupe%C5%82ny" title="Problem NP-zupełny">Polski</a></li>
<li class="interwiki-pt"><a href="http://pt.wikipedia.org/wiki/NP-
completo" title="NP-completo">Português</a></li>
<li class="interwiki-ru"><a href="http://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-полная
задача">Русский</a></li>

<li class="interwiki-simple"><a href="http://simple.wikipedia.org/
wiki/NP-complete" title="NP-complete">Simple English</a></li>
<li class="interwiki-sk"><a href="http://sk.wikipedia.org/wiki/NP-
%C3%BApln%C3%BD_probl%C3%A9m" title="NP-úplný problém">Slovenčina</a></
li>
<li class="interwiki-sr"><a href="http://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="НП-комплетни
проблеми">Српски / Srpski</a></li>
<li class="interwiki-fi"><a href="http://fi.wikipedia.org/wiki/NP-
t%C3%A4ydellisyys" title="NP-täydellisyys">Suomi</a></li>
<li class="interwiki-sv"><a href="http://sv.wikipedia.org/wiki/NP-
fullst%C3%A4ndig" title="NP-fullständig">Svenska</a></li>
<li class="interwiki-th"><a href="http://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="เอ็นพีบริบูรณ์">ไทย</a></li>

<li class="interwiki-uk"><a href="http://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-повна задача">Українська</a></li>
<li class="interwiki-zh"><a href="http://zh.wikipedia.org/wiki/NP
%E5%AE%8C%E5%85%A8" title="NP完全">中文</a></li>
</ul>
</div>
</div>

</div>

<div id="footer">
<ul id="footer-info">
<li id="footer-info-lastmod"> This page was last
modified on 6 July 2010 at 21:14.<br /></li>
<li id="footer-info-copyright">Text is
available under the <a rel="license" href="http://en.wikipedia.org/
wiki/Wikipedia:Text_of_Creative_Commons_Attribution-
ShareAlike_3.0_Unported_License">Creative Commons Attribution-
ShareAlike License</a><a rel="license" href="http://
creativecommons.org/licenses/by-sa/3.0/" style="display:none;"></a>;
additional terms may apply.
See <a href="http://wikimediafoundation.org/wiki/Terms_of_Use">Terms
of Use</a> for details.<br/>

Wikipedia® is a registered trademark of the <a href="http://
www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-
profit organization.<br /></li><li class="noprint"><a class='internal'
href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact us</
a></li>
</ul>
<ul id="footer-places">
<li id="footer-places-privacy"><a href="http://
wikimediafoundation.org/wiki/Privacy_policy" title="wikimedia:Privacy
policy">Privacy policy</a></li>
<li id="footer-places-about"><a href="/wiki/
Wikipedia:About" title="Wikipedia:About">About Wikipedia</a></li>

<li id="footer-places-disclaimer"><a href="/
wiki/Wikipedia:General_disclaimer" title="Wikipedia:General
disclaimer">Disclaimers</a></li>
</ul>
<ul id="footer-icons" class="noprint">
<li id="footer-icon-poweredby"><a href="http://
www.mediawiki.org/"><img src="http://bits.wikimedia.org/skins-1.5/
common/images/poweredby_mediawiki_88x31.png" height="31" width="88"
alt="Powered by MediaWiki" /></a></li>
<li id="footer-icon-copyright"><a href="http://
wikimediafoundation.org/"><img src="/images/wikimedia-button.png"
width="88" height="31" alt="Wikimedia Foundation"/></a></li>
</ul>
<div style="clear:both"></div>
</div>

<script type="text/javascript"> if ( window.isMSIE55 ) fixalpha(); </
script>

bush6...@gmail.com

unread,

Mar 18, 2017, 1:22:19 PM3/18/17

0 new messages