My original paper appeared under this title in the Spring 2000 issue of the Mathematical Intelligencer(volume 22 number 2, pages 9--15).
Minesweeper is NP-complete!
It was discussed by Ian Stewart in the Mathematical Recreationscolumn in the Scientific American, in October 2000, and has been discussed in newspapers in the USA (including the Boston Globe on November 1st, 2000) and on national radio in Britain.It has also featured on CNET (www.cnet.com) and CNN (www.cnn.com)and in the Guardian on 9th November,and there was an extensive discussion at slashdot (www.slashdot.com).
My work on Minesweeper was the subject of Ian Stewart's lecture at the ClayInstitute on November 1st 2000.
I have just set up a FAQ list concerning minesweeper and NP-completeness which is available here. (But please readthe current page first!)
Np Complete Np Hard DifferenceSo what's it all about?
What I managed to prove is that the minesweeper game isessentially equivalent in complexity to any of a wide range of known natural and important problems in the literaturecalled NP-complete problems.
These problems all take the form of general problems requiringa yes/no answer. A rather nice example of such a problem is the 'BIN-PACKING' problem (I prefer to call it 'floppy-disk packing problem'!) which asks,
given n floppy disks each of size xand m computer files of sizes y1, y2, y3, .. ym, is it possible to copy all of the files to the floppy disks given?Obviously sometimes the answer will be 'yes', and sometimes 'no'. It dependson the numbers n,m,x and y1,..,ym. What is neededis an efficient computer program or algorithm that will givethe answer in all cases. (Here and thoughout, I mean 'efficient' in the technical sense of 'running in polynomial time'.)
Problems like this are of great practical importance,and an efficient algorithm would be very useful. Unfortunatelyno-one has yet found such an algorithm, and many people suspect that thereisn't such an algorithm. In principle, it may even be possibleto prove that there is no such algorithm, but again no-onehas managed to do this either. Just about all that we do know isthat if any one of the list of known NP-complete problems has an efficient algorithm, then they all doâand conversely if one of themcan be proved not to have any efficient algorithm then they allhave the same status.
The famous 'P=NP?' question is just this: to determine whether there is an NP-complete problem which has an efficient algorithm (in which case they all would have), or alternatively to prove some NP-complete problem does not have an efficient algorithm (in which case none of them would have). This is one of the biggest and most important open problem in mathematics at the moment, and is the subject of a $1,000,000 prize offeredby the Clay MathematicsInstitute in the USA. See their site for some more details, inparticular their pages on the P vs NP problem.
There are some very important reasons why one would want to know the answer to this questionâwhatever the answer would be. A 'positive' answer giving new efficient algorithms would clearly be an important breakthrough, but even a 'negative'answer that P is not equal to NP would have importantpractical consequences.
To understand why this is, you need to know that many codes used on computers and the internet are designed on the basis that a potential code-breaker would have to find an efficient algorithm for (at best)an NP-complete problem to break the code in reasonable time. These codes have proved to be remarkably effective. (In fact, because they are so good, they areâcontroversiallyâthe subject of various laws against their use, put in place by national governments who seem to have accepted that they cannot break them. But that is another story.) However, the possibility that P and NP may turn out to be equal after allleaves a nagging doubt in the minds of the people who use these codes.This is because any person who can prove P=NP would be able to break them all. If he really wanted to make money, he might do a lot better thanclaiming the Clay Institute's million dollars!
My result in the Mathematical Intelligencer states thata decision problem which I like to call 'the MinesweeperConsistency Problem' and which is exactly equivalent to the problem of playing the minesweeper game, is yet another oneof these NP-complete problems.
It's not entirely obvious how to convert the sorts of problemsyou get when playing the game to a simple decision problemwith yes/no answers. However, a good Minesweeper player will never make a guess if there is a square that is certainly freeand a guess is not required. Similarly he or she will mark upevery mine that can be identified with certainty. It is preciselythese questions, whether a mine is certainly in a particular square,or whether a square is certainly free, that can be solvedby an algorithm for the Minesweeper Consistency Problem. Seemy Intelligencer paper for more details.
For the current discussion, it suffices that the problem of simplydetecting which squares are or are not mines is equivalent tothe Minesweeper Consistency Problem, and the fact that it is NP-completemeans, for Minesweeper fans, that their favourite gamecan be seen as being right at the cutting edge of mathematical research.There are two possible viewpoints one might take on this.
The more 'sober' viewpoint is that the NP-completeness of Minesweepershows that Minesweeper really is a rather good game. The fact that it is NP-complete means that it is very difficult to spot when it is possible to clear a square safely in full knowledge that that square is clear, and when some guessing is required. In fact, even if you are told in advance that guessing is not required, it may still be difficult to decide what squares to clear. In some sense, when you play the game you cannot be expected to do much better than the hundreds of very good mathematicians who have worked on the P=NP? question for many many years.
But once again, there remains that nagging doubt.. The more exciting view one might take is that one day, perhaps, it may turn out thatan expert Minesweeper player could spot some pattern in the game that would eventually lead to an polynomial-time algorithm for solving itâand hence polynomial-time algorithms for all the NP-complete problems. Such an outcome would result in methods to crack all of the codes used in the internet and computers across the world.
Minesweeper configurations
I have written and maintain a companion world-wide-web paper, `Minesweeper configurations',which aims to contain some minesweeper configurations puzzles and problemsthat have come to light since the original paper. This is available here in PDF format.
In particular, I have already had one email pointing out that there is a small error in the diagram for a 'bent wire' in the published paperand a have had email discussions with various peopleabout simplifying the diagrams for the logic gates. The paper above contains details of some of these corrections and simplifications,and will be expanded in the future as more ideas and interesting positionscome to light. Please email me with your ideas!
Related pages
As mentioned above, there are algorithms that solve Minesweeperperfectly, but the only ones known take an inordinate amountof time. (Basically, this is because the game is played on a finitegrid, so there are only finitely many possibilities to go through.) For a different slant on Minesweeper, you can also consider Minesweeper-like games on an infinite grid. This is whatI did in a recent paper: I showed that in fact any computer program at all can be simulated by a position in such a game. See here for more details.
A minesweeper talk, first given at the ASEmeeting in Birmingham, Jan 3-5 2003, is available (PDF file, 300k). This talk contains some nice graphics, and some new minesweeperconfigurations.
Note: 'Minesweeper' here refers to the game of that name which isprovided with Microsoft's 'Windows' operating system.(I do not have any connection with Microsoft and nothing hereshould be regarded as comment on any of Microsoft's products.)
The diagrams in these pages are Minesweeper configurations thatwere used in the proof that the Minesweeper Consistency Problem isNP-complete. See the Intelligencer paper for more details.I am grateful to Harry Hutchinson for converting them to a more familiarformat than the numbers and stars that I originally used.
Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that Pâ NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)
NP-hardness (non-deterministic polynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, 'at least as hard as the hardest problems in NP'. A simple example of an NP-hard problem is the subset sum problem.
A more precise specification is: a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H; that is, assuming a solution for H takes 1 unit time, we can use Hâ's solution to solve L in polynomial time.[1][2] As a consequence, finding a polynomial algorithm to solve any NP-hard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered difficult.[3]
A common misconception is that the NP in 'NP-hard' stands for 'non-polynomial' when in fact it stands for 'non-deterministic polynomial acceptable problems'.[4] Although it is suspected that there are no polynomial-time algorithms for NP-hard problems, this has not been proven.[5] Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class.[6]
Definition[edit]
A decision problemH is NP-hard when for every problem L in NP, there is a polynomial-time reduction from L to H.[1]:80An equivalent definition is to require that every problem L in NP can be solved in polynomial time by an oracle machine with an oracle for H.[7] Informally, we can think of an algorithm that can call such an oracle machine as a subroutine for solving H, and solves L in polynomial time, if the subroutine call takes only one step to compute.
Another definition is to require that there is a polynomial-time reduction from an NP-complete problem G to H.[1]:91 As any problem L in NP reduces in polynomial time to G, L reduces in turn to H in polynomial time so this new definition implies the previous one. Awkwardly, it does not restrict the class NP-hard to decision problems, for instance it also includes search problems, or optimization problems.
Consequences[edit]
If P â NP, then NP-hard problems cannot be solved in polynomial time.
Note that some NP-hard optimization problems can be polynomial-time approximated up to some constant approximation ratio (in particular, those in APX) or even up to any approximation ratio (those in PTAS or FPTAS).
Examples[edit]
An example of an NP-hard problem is the decision subset sum problem, which is this: given a set of integers, does any non-empty subset of them add up to zero? That is a decision problem, and happens to be NP-complete. Dr driving 4 pc game. Another example of an NP-hard problem is the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph. This is commonly known as the traveling salesman problem.[8]
There are decision problems that are NP-hard but not NP-complete, for example the halting problem. This is the problem which asks 'given a program and its input, will it run forever?' That is a yes/no question, so this is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete. For example, the Boolean satisfiability problem can be reduced to the halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in NP since all problems in NP are decidable in a finite number of operations, while the halting problem, in general, is undecidable. There are also NP-hard problems that are neither NP-complete nor Undecidable. For instance, the language of True quantified Boolean formulas is decidable in polynomial space, but not in non-deterministic polynomial time (unless NP = PSPACE).[9]
NP-naming convention[edit]
NP-hard problems do not have to be elements of the complexity class NP.As NP plays a central role in computational complexity, it is used as the basis of several classes:
Tomb raider dual pistols. 'Finals'.
Application areas[edit]
NP-hard problems are often tackled with rules-based languages in areas including:
References[edit]
Retrieved from 'https://en.wikipedia.org/w/index.php?title=NP-hardness&oldid=893239952'
All NP complete problems are NP hard problems when solved in adifferent way.
But, all NP hard problems are not NP complete.
Ex:
1. Traveling salesman problem. It is both NP hard and NPcomplete. We can find that whether the solution is correct or notin the given period of time. In this way, it is NP complete.
But, to find the shortest path, i.e. optimization of TravelingSalesman problem is NP hard. If there will be changing costs, thenevery time when the salesperson returns to the source node, then hewill be having different shortest path. In this way, it is hard tosolve. It cannot be solved in the polynomial time. In this way, itis NP hard problem.
2. Halting problem.
3. Sum of subset problem.
Difference between np and np complete?
A problem is 'in NP' if there exists a polynomial time complexity algorithm which runs on a Non-Deterministic Turing Machine that solves it. A problem is 'NP Hard' if all problems in NP can be reduced to it in polynomial time, or equivalently if there is a polynomial-time reduction of any other NP Hard problem to it. A problem is NP Complete if it is both in NP and NP hard.
What is the difference between NP and NP Complete problems?
a problem in NP means that it can be solved in polynomial time with a non-deterministic turing machine - a problem that is NP-hard means that all problems in NP are 'easier' than this problem - a problem that is NP-complete means that it is in NP and it is NP-hard example - Hamiltonian path in a graph: The problem is: given a graph as input, an algorithm must say whether there is a⦠Read More
Is Node-disjoint paths np-complete?What is set difference between recursive and recursively enumerable but not recursive?
All recursive Languages are recursively enumerable. But not all the recursively enumerable languages are recursive. It is just like NP complete.
What is the difference between P and NP complexity classes?
P is the class of problems for which there is a deterministic polynomial time algorithm which computes a solution to the problem. NP is the class of problems where there is a nondeterministic algorithm which computes a solution to the problem, but no known deterministic polynomial time solution
What are some transformice tribe house codes?
House codes: /np @931629 /np @709003 Bootcamp like codes: /np @172976 /np @608368 /np @191205 /np @842019 /np @159932 /np @593204 /np @145219 /np @1450120 /np @449496 /np @618999 /np @801683 /np @1014313 /np @1444036 /np @633644 /np @808800 /np @1444041 That's all I know, but I hope it'll be to help ^^
What are some transformice house tribe codes?
House codes: /np @931629 /np @709003 Bootcamp like codes: /np @172976 /np @608368 /np @191205 /np @842019 /np @159932 /np @593204 /np @145219 /np @1450120 /np @449496 /np @618999 /np @801683 /np @1014313 /np @1444036 /np @633644 /np @808800 /np @1444041 Thats all I got sorry if some don't work I didn't check them all If you want to find me on TFM my user is Butterbe
Difference between noun phrase and verb phrase?
The price of petrol will have skyrocketted by 2015. The Subject at the beginning- 'The price of petrol' is the Noun Phrase. NP has other functions and uses too. The Verb Phrase is 'will have skyrocketted' (2 Auxiliary+main verb) A Verb phrase may be a one word or more than one word verbs. If it is more than one word it will have Auxiliary(s)+Principal Verb eg. I had lunch. (NP-I + VP-had+ NP-lunch) The guests⦠Read More
What are national parks in the interior plains?
If you mean the interior plains of the USA, these would include Badlands NP and Theodore Roosevelt NP. If you include the interior plains of Canada, then add Elk Island NP, Grasslands NP, Riding Mountain NP; and perhaps Prince Albert NP and Wood Buffalo NP.
What is np?Is there a national forest campground between Grand Teton NP and Yellowstone NP?
The road between the northern border of Grand Teton NP and the southern border of Yellowstone NP is completely contained by another area administered by the National Parks Service. Specifically, the John D. Rockefeller Jr Memorial Parkway. Within this area is Flagg Ranch, with a lodge, cabins, and camping area. Primitive camp sites exist along the dirt road just off the main highway between the two national parks. So, although there is not a campground⦠Read More
How do you convert shillings and pence into decimal?
With great difficulty. The easy bit was shillings: there were 20 shillings in a pound and 100 decimal pennies. At the time of their introduction, the latter were called New Pence (NP) and I will stick to that notation.So 1 shilling = 0.05 pounds = 5 NP. The problem came with converting 12 [old] pennies in a shilling to 5 NP. A saving grace was that there was still a 1/2 New Penny coin Formally⦠Read More
What type of chemical bond is there in C7H8?How do you explain what P NP and NP complete complexity classes are in a simple way?
P is the class of problems that can be solved in polynomial time. That is, the size of the input affects the length of the computation multiplicatively. NP is the class of problems in which the effect of input size on the length of the computation is exponential or factorial. In addition, for a problem to be in this class, a proposed or candidate solution must be checkable in polynomial time. The usual example here⦠Read More
What national park did Wilson establish?
Woodrow Wilson became U.S. President in March of 1913, and remained President until March of 1920. In addition to signing the legislation establishing the National Parks Service, he also signed legislation establishing Rocky Mountain NP, Lafayette NP (renamed Acadia NP in 1929), Hawaii NP (eventually became Hawaii Volcanoes NP), Mount McKinley NP (renamed Denali NP), Lassen Volcano NP (had previously been a national MONUMENT), Zion NP (same change), and Grand Canyon NP.
Where do you get Paintbrushes for free on neopets?
You have to click the button between explore and boards, it is REALLY hard to find, but it is there! --- That would be a random event. There are no free expensive things. Unless you have a really, really good friend who is either really generous and/or runs a NP generating program.
What does the NP on the barrel of a on a Browning rifle BBR stand for.?
date of manufacture, np=98 date of manufacture, np=98
What does NP on the back of a plate mean?What does NP mean after a person's name?What does np mean in texting?How is neptunium similar to plutonium?
Similarities: - Np and Pu are radioactive, unstable chemical elements - Np and Pu are man made - Np and Pu are dangerous - Np and Pu are fissionable with thermal neutrons
What does the term NP stand for on a computer?What is a the base of neptunium?
Please explain 'base of a neptunium'. If you think to chemistry: Known hydroxides are Np(OH)3, Np(OH)6, and in special conditions Np(OH)4, Np(OH)5.
State cook's theorem?
In computational complexity theory, Cook's theorem, also known as the CookâLevin theorem, states that the Boolean satisfiability problem is NP-complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable.
What are the difference between superstitions and scientifically base belief?
Scientifically base beliefs are proven facts, while superstitions are stories that for example if you wear a red socks you will score more runs in cricket or more goals in football. This are passed on stories with np proof at all it can help you.
When was NP - novel - created?When was NP Dodge Company created?How many pages does NP - novel - have?What is the ISBN of NP novel?How does a loan account becomes NP account?Why is learning another language hard?
Language differs in snytactic structures and phonetics in semantic concepts.The evolution of language in historical-geographical-social cultural perspective have been specific for one language and different for the other.Variations within a language of a native speaker as vernacular language change in dialects,intonations etc. eg: gutturals in Persian & Arabic do not exist in indo European languages. There are different theories of native language learning and foreign language learning. Two areas are distinctly different: 1. The syntactic⦠Read More
What is the average hourly wage for a psychiatric nurse practitioner in NY state?Difference between deterministic and nondeterministic algorithm in design and analysis of algorithm?
Algorithm is deterministic if for a given input the output generated is same for a function. A mathematical function is deterministic. Hence the state is known at every step of the algorithm.Algorithm is non deterministic if there are more than one path the algorithm can take. Due to this, one cannot determine the next state of the machine running the algorithm. Example would be a random function.FYI,Non deterministic machines that can't solve problems in polynomial⦠Read More
What is the answer to P equals NP?
This is an unsolved problem in computer science; you can't expect to get an answer here, for a problem that nobody on Earth has solved yet! For more information, read the Wikipedia article 'P versus NP problem'. Briefly, it relates to the question whether or not there are problems that are 'hard' to solve, but - once solved - 'easy' to verify. This is one of the 'millenium problems'; if you can find a proof⦠Read More
NP - what is the meaning?
This questin would be related to the Salary details like as CTC, ECTC, NP. CTC Stands for Cost to Company, ECTC - Stands for Expected Cost to Company like as NP - Stands for What? Answer On the Internet, NP stands for 'no problem.' No is 'Notice Period'
What national park do moose live in?
I have personally seen moose in Grand Teton, Yellowstone, Isle Royale, and Denali. Moose can also be seen in just about every NP in the southern part of Alaska, as well as in Acadia NP, Glacier NP, and Rocky Mountain NP.
What are the disadvantages of being a nurse practitioner?
I have been a Nurse Practitioner for over 10 years. There are positive and negative aspects of every professional choices in life. I believe being a NP is the choice for me. I had practiced psychiatric nursing for many years, then after the birth of my daughter, I returned to school to switch clinical tracks. I have been a pediatric NP for the past 5 year. I feel that I am making a difference in⦠Read More
What does Np stand for?
Np stands for Neptunium the element after Uranium - number 93 If you're talking about a text message, 'np' is a shorthand for 'no problem.' In other contexts, it can mean a variety of things.
What is the design of step down transformer?
The formula for transformers is: Ns/Np = Vs/Vp, where Ns, Vs are number of turns and voltage in secondary and Np, Vp are in primary. If you want step up transformer, Np > Ns. And if step up transformer, then put Ns > Np.
How much are paintbrushes on neopets?
it depends on which paintbrush you want to buy. Like the baby paintbrush costs around 600,000 NP (at least if you go to the faerie queen's hidden tower it'd cost 600,000 NP. u can get tons of paintbrushes and rare items from the hidden tower: Most cost about 500,000 NP to like 4,000,000 NP (4 mil is the Maractite Paint Brush) The paintbrushes in auctions depends on the person who puts it up. some of⦠Read More
What does np or ns stand for in classifieds?
I believe NS means non-smoker, and NP means no pets.
Which element is Np?
Np is the elemental symbol for Neptunium. NPO means Non per os or 'nothing to be taken orally'. This is a common pre-op direction. Shorthand on the internet, np stands for no problem
Can a nurse practitioner function as a nurse if her job title and description is that of a nurse practitioner?What is the first np-hard problem?
You can use the bounded tiling problem. Given a problem in NP A, it has a turing machine M that recognizes its language. We construct tiles for the bounded tiling problem that will simulate a run of M. Given input x, we ask if there is a tiling of the plane and answer that will simulate a run of M on x. We answer true iff there is such a tiling.
What transfer case is in a 1989 Chevy 4x4 with a 350 and a 4-speed?
new process gear or 'NP 208' other transfer cases of prior years are: NP 203 - Full time 4WD. NP 205 - Cast iron gear driven NP 208 - Aluminum chain driven
How do you get NP fast on neopets?
play snow wars 2 you can get like 1000 np each time u play
What does ctc ectc np stand for?
ctc = cost to company ectc = expected cost to company np = notice period
What do you mean by np ectc and ctc?
NP = Notice Period CTC = Cost To Company ECTC = Expected Cost To Company
What do the initials np mean?
The initials 'np' are the lazy way of writing or typing out 'no problem'. Forged in fire destiny 2. Or , if you are on the site ' neopets' It stands for ' neopoints '
Why is neptunium's symbol Np?
The symbol Np is derived from the name of neptunium, by convention; Ne was impossible because is the symbol of neon.
This is a rough guide to the meaning of 'NP-Complete'. It is not intended to be an exact definition, but should help you to understand the concept.
These are just my personal ideas and are not meant to be 'rigorous'.
Its All About 'Time to Solve'
When you measure how long a program takes to run when it is given more and more difficult problems (such as sorting a list of 10 items, 20 items, 30 items etc) you can plot the times and come up with a function.
Example: a program's time increases by x2
So a problem that is twice as hard takes 4 times as long.
That program is in 'P', as it is solvable in 'Polynomial' time.
In this case the polynomial is:
t = x2
But if the time goes up exponentially or factorially, or something that exceeds what a polynomial can do, it is NOT in 'P' (it is not solvable in 'Polynomial' time).
P: can be solved in Polynomial time.
(How long it takes is defined by a polynomial) Amazing Computer can do what normal Computers can't
Now, the 'N' in 'NP' refers to the fact that you are not bound by the normal way a computer works, which is step-by-step. The 'N' actually stands for 'Non-deterministic'. This means that you are dealing with an amazing kind of computer that can run things simultaneously or could somehow guess the right way to do things, or something like that.
So this 'N' computer can solve lots more problems in 'P' time - for example it can just clone copies of itself when needed.
It is not a Super Computer (they are just very fast normal computers), it is really a 'Non-deterministic' computer, but I am calling it an Amazing Computer to give you the idea!
So, programs that take dramatically longer as the problem gets harder (i.e. not in 'P') could be solved quickly on this amazing 'N' computer and so are in 'NP'. Thus 'NP' means 'we can solve it in polynomial time if we can break the normal rules of step-by-step computing'.
NP: can be solved in Polynomial time using a
Non-deterministic method. (also includes P problems) Amazing Computers can also do what normal Computers can
Since this amazing 'N' computer can also do anything a normal computer can, we know that 'P' problems are also in 'NP'.
So, the easy problems are in 'P' (and 'NP'), but the really hard ones are *only* in 'NP', and they are called 'NP-complete'.
It is like saying there are things that People can do ('P'), there are things that SuperPeople can do ('SP'), and there are things *only* SuperPeople can do ('SP-complete').
NP-Complete: can be solved in Polynomial time
only using a Non-deterministic method. NP-Complete may not last
Oh, one more thing, it is believed that if anyone could *ever* solve an 'NP-Complete' problem in 'P' time, then *all* 'NP-complete' problems could also be solved that way by using the same method, and the whole class of 'NP-Complete' would cease to exist.
Traveling Salesman Problem
The classic example of 'NP-Complete' problems is the Traveling Salesman Problem.
Imagine you need to visit 5 cities on your sales tour. You know all the distances. Which is the shortest round-trip to follow? ABCEDA? ADECBA?
An obvious solution is to check all possibilities.
But this only works for small problems. If you add a new city it needs to be tried out in every previous combination.
So this method takes 'factorial time': t = n!
(Actually t = (n-1)! but it is still factorial.)
Imagine the program solves a 20-city problem in 1 second, then
Luckily, there are special ways to break the problem into sub-problems (called 'dynamic programming', but the best still take exponential time: t = 2n(2 with an exponent of n)
So a program that solves 20 cities in 1 second will solve 30-cities in about 10 minutes, and 60-cities in about 35,000 Years (still a bit too long).
But if we had the 'Amazing Computer' mentioned above it could, for example, create copies of itself to check all the possibilities, and hopefully solve the problem very quickly.
NP-Hard
When a problem's method for solution can be turned into an NP-Complete method for solution it is said to be 'NP-Hard'.
NP-Hard: as hard as any NP-problem, or maybe harder.
Anyway, I hope this 'quick and dirty' introduction has helped you .. now go and read something more rigorous.
(definition)
Definition:The complexity class of decision problems for which answers can be checked for correctness, given a certificate, by an algorithm whose run time is polynomial in the size of the input (that is, it is NP) and no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-complete if answers can be verified quickly, and a quick algorithm to solve this problem can be used to solve all other NP problems quickly.
Generalization (I am a kind of ..)
NP.
See alsoNP-hard, P.
Note:A trivial example of NP, but (presumably) not NP-complete is finding the bitwise AND of two strings of N boolean bits. The problem is NP, since one can quickly (in time Î(N)) verify that the answer is correct, but knowing how to AND two bit strings doesn't help one quickly find, say, a Hamiltonian cycle or tour of a graph. So bitwise AND is not NP-complete (as far as we know).
Other well-known NP-complete problems are satisfiability (SAT), traveling salesman, the bin packing problem, and the knapsack problem. (Strictly the related decision problems are NP-complete.)
'NP' comes from the class that a Nondeterministic Turing machine accepts in Polynomial time.
Author: PEB
ImplementationStas Busygin's home page with QUALEX and SAT01 (C++).More information
History, definitions, examples, etc. given in Comp.Theory FAQ, scroll down to P vs. NP. Eppstein's longer, but very good introduction to NP-completeness, with sections like Why should we care?, Examples of problems in different classes, and how to prove a problem is NP-complete. A compendium of NP optimization problems.
Scott Aaronson's Complexity Zoo
From xkcd 287 by Randall Munroe. Creative Commons Attribution-NonCommercial 2.5 License.
If you have suggestions, corrections, or comments, please get in touchwith Paul Black.
Entry modified 19 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.
Cite this as:
Paul E. Black, 'NP-complete', inDictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 19 February 2019. (accessed TODAY)Available from: https://www.nist.gov/dads/HTML/npcomplete.html Comments are closed.
|
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |