Download here: http://gg.gg/viggu
Science and technology journalists pride themselves on the ability to explain complicated ideas in accessible ways, but there are some technical principles that we encounter so often in our reporting that paraphrasing them or writing around them begins to feel like missing a big part of the story. So in a new series of articles called ’Explained,’ MIT News Office staff will explain some of the core ideas in the areas they cover, as reference points for future reporting on MIT research.
In the 1995 Halloween episode of The Simpsons, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wandering across a dark surface etched with green gridlines and strewn with geometric shapes, above which hover strange equations. One of these is the deceptively simple assertion that P = NP.
In fact, in a 2002 poll, 61 mathematicians and computer scientists said that they thought P probably didn’t equal NP, to only nine who thought it did — and of those nine, several told the pollster that they took the position just to be contrary. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving. Roughly speaking, P is a set of relatively easy problems, and NP is a set that includes what seem to be very, very hard problems, so P = NP would imply that the apparently hard problems actually have relatively easy solutions. But the details are more complicated.
Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.
Imagine, for instance, that you have an unsorted list of numbers, and you want to write an algorithm to find the largest one. The algorithm has to look at all the numbers in the list: there’s no way around that. But if it simply keeps a record of the largest number it’s seen so far, it has to look at each entry only once. The algorithm’s execution time is thus directly proportional to the number of elements it’s handling — which computer scientists designate N. Of course, most algorithms are more complicated, and thus less efficient, than the one for finding the largest number in a list; but many common algorithms have execution times proportional to N2, or N times the logarithm of N, or the like.
A mathematical expression that involves N’s and N2s and N’s raised to other powers is called a polynomial, and that’s what the “P” in “P = NP” stands for. P is the set of problems whose solution times are proportional to polynomials involving N’s.
Obviously, an algorithm whose execution time is proportional to N3 is slower than one whose execution time is proportional to N. But such differences dwindle to insignificance compared to another distinction, between polynomial expressions — where N is the number being raised to a power — and expressions where a number is raised to the Nth power, like, say, 2N.
If an algorithm whose execution time is proportional to N takes a second to perform a computation involving 100 elements, an algorithm whose execution time is proportional to N3 takes almost three hours. But an algorithm whose execution time is proportional to 2N takes 300 quintillion years. And that discrepancy gets much, much worse the larger N grows.
NP (which stands for nondeterministic polynomial time) is the set of problems whose solutions can be verified in polynomial time. But as far as anyone can tell, many of those problems take exponential time to solve. Perhaps the most famous exponential-time problem in NP, for example, is finding prime factors of a large number. Verifying a solution just requires multiplication, but solving the problem seems to require systematically trying out lots of candidates.
So the question “Does P equal NP?” means “If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?” Part of the question’s allure is that the vast majority of NP problems whose solutions seem to require exponential time are what’s called NP-complete, meaning that a polynomial-time solution to one can be adapted to solve all the others. And in real life, NP-complete problems are fairly common, especially in large scheduling tasks. The most famous NP-complete problem, for instance, is the so-called traveling-salesman problem: given N cities and the distances between them, can you find a route that hits all of them but is shorter than … whatever limit you choose to set?
Given that P probably doesn’t equal NP, however — that efficient solutions to NP problems will probably never be found — what’s all the fuss about? Michael Sipser, the head of the MIT Department of Mathematics and a member of the Computer Science and Artificial Intelligence Lab’s Theory of Computation Group (TOC), says that the P-versus-NP problem is important for deepening our understanding of computational complexity.
“A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says.
Similarly, Sipser says, “the excitement around quantum computation really boiled over when Peter Shor” — another TOC member — “discovered a method for factoring numbers on a quantum computer. Peter’s breakthrough inspired an enormous amount of research both in the computer science community and in the physics community.” Indeed, for a while, Shor’s discovery sparked the hope that quantum computers, which exploit the counterintuitive properties of extremely small particles of matter, could solve NP-complete problems in polynomial time. But that now seems unlikely: the factoring problem is actually one of the few hard NP problems that is not known to be NP-complete.
Sipser also says that “the P-versus-NP problem has become broadly recognized in the mathematical community as a mathematical question that is fundamental and important and beautiful. I think it has helped bridge the mathematics and computer science communities.”
But if, as Sipser says, “complexity adds a new wrinkle on old problems” in mathematics, it’s changed the questions that computer science asks. “When you’re faced with a new computational problem,” Sipser says, “what the theory of NP-completeness offers you is, instead of spending all of your time looking for a fast algorithm, you can spend half your time looking for a fast algorithm and the other half of your time looking for a proof of NP-completeness.”
Sipser points out that some algorithms for NP-complete problems exhibit exponential complexity only in the worst-case scenario and that, in the average case, they can be more efficient than polynomial-time algorithms. But even there, NP-completeness “tells you something very specific,” Sipser says. “It tells you that if you’re going to look for an algorithm that’s going to work in every case and give you the best solution, you’re doomed: don’t even try. That’s useful information.”
NP-Complete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time. Intuitively this means that we can solve Y quickly if we know how to solve X quickly. A language B is NP-complete if it satisfies two conditions B is in NP Every A in NP is polynomial time reducible to B. If a language satisfies the second property, but not necessarily the first one, the language B is known as NP-Hard. Algorithm C(s, t) is a certifier for problem X if for every string s: s ∈ X iff there exists a string t such that C(s, t) = yes. NP = set of decision problems for which there exists a poly-time certifier.Many of the games and puzzles people play are interesting becauseof their difficulty: it requires cleverness to solve them. Oftenthis difficulty can be shown mathematically, in the form ofcomputational intractibility results: every NP-complete problem isin some sense a puzzle, and conversely many puzzles areNP-complete. Two-player games often have higher complexities suchas being PSPACE-complete.
WW (pp. 218-219; see referencesbelow) is disparaging of this sort of result, writing that ’thisasymptotic result says little about the difficulties of calculatinggood strategies’, describing NP-hard game positions as ’degenerate’and ’relatively dull’, and advocating (as a response to hardnessproofs) looking for additional rules and conditions that would makethe game easier. But to me NP-completeness is not the end but thebeginning of the study of a game: it shows that the game is complexenough that we can encode interesting computational problems withinit. If a game is in P, it becomes no fun once you learn ’the trick’to perfect play, but hardness results imply that there is no suchtrick to learn: the game is inexhaustible. And of courseNP-completeness or PSPACE-completeness doesn’t even rule out thepossibility of computing game values exactly; true, it seems toimply that worst-case-exponential algorithms are required, butthere is still plenty of interesting work in designing, analyzing,and implementing such algorithms.
There is a curious relationship between computational difficultyand puzzle quality. To me, the best puzzles are NP-complete(although some good puzzles are in P, relying on gaps in humanintuition rather than on computational complexity for theirdifficulty). Some puzzles are even harder than NP (for instance,sliding block puzzles and Sokoban are PSPACE-complete) but to methis means only that the problem can have an annoyingly longsequence of manipulations in its solution. For two-player games,one encounters a similar phenomenon at a higher level ofcomplexity. The tree of potential interactions in a game typicallygives rise to PSPACE-completeness results of a sort I find moreinteresting than PSPACE-completeness in puzzles. However some gamesare harder, EXPTIME-complete, which to me means that it maysometimes be necessary for a well-played game to go on for atediously long sequence of moves. Perhaps some games or puzzles inwhich the players start with incomplete knowledge of the game orpuzzle configuration might lead to other types of completeness(e.g. MA-completeness or #P-completeness) for finding the startingmove most likely to succeed, but I know of no such results.
I primarily list here real games and puzzles, games that wereinvented to be played, rather than to be analyzed. So I’m notincluding some of the more artificial entries in e.g. WW orGJ, such as ’sequential truth assignment’. If someone canpoint me to a tournament for these games, a copy of the game soldin stores, or a program for people to play them against theircomputers, I’ll consider adding them.
One caveat: NP-completeness is not a concept that applies to asingle puzzle or game position, or even a finite collection ofpositions. It only makes sense to talk about an infinite family ofproblems as being NP-complete. For this reason games like chesscannot themselves be NP-complete, as they only have a finite(albeit unthinkably large) number of possible positions. In manycases however there is a natural generalization from some finitegame or puzzle to an infinite family of game positions onarbitrarily large game boards, in which it makes sense to talkabout NP-completeness. The fact that these infinite generalizationsare computationally hard gives us some justification for believingthat the original finite games are also hard in some lesswell-defined sense.Index:
Puzzles and solitaire games:Alphametics;Clickomania;Cryptarithms;Cubic;15-puzzle;Instant Insanity;KPlumber;Mah Jongg;Pearl puzzles;Rush Hour;Shanghai;Sokoban
Two-player games:Amazons;Bridge-It;Checkers;Chess;Dots and boxes;Draughts;Go;Hex;Mastermind;Othello;Phutball;Reversi;Shannon switching game;TwixtSome useful general references:
*E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways foryour Mathematical Plays, Academic Press, 1982. We refer to this asWW.
*M. R. Garey and D. S. Johnson, Computers and Intractibility: aguide to the theory of NP-completeness, W.H. Freeman, 1979. Werefer to this as GJ.
*R. K. Guy, ed., Combinatorial Games, Proc. Symp. AppliedMath. 43, AMS, 1990. We refer to this as CG. Seeespecially A. S. Fraenkel, Complexity of games, CG 111-154,as well as Fraenkel’s introduction to the bibliography.
*R. J. Nowakowski, ed., More Games of No Chance,MSRI Publications #42, 2002.We refer to this as MGONC.AmazonsDescription: Players move queens on an n*n board, as part ofeach move shooting an arrow from the moved piece. Arrows move like a chessqueen when shot but are immovable afterwards. The arrows eventuallyblock the movement of the queens; the last player to complete a movewins. Game-play combines go-like goals of surrounding territory withchess-like tactics of blocking opposing pieces’ lines of play.The most commonly used starting configuration involves four queens ofeach color placed around the edges of a 10*10 board.
Status: PSPACE-complete. Endgames in which pieces of opposing colorsare separated from each other are NP-hard.
Follow our guide to create perfect HTML signature in Apple mail. Create a new signature. Let’s go to Mail Preferences Signatures and click “+” button. “Nicereply” name to your signature and add just your full name to your new email signature. Our sample email signature now looks like this. Create signatures In the Mail app on your Mac, choose Mail Preferences, then click Signatures. In the left column, select the email account where you want to use the signature. If All Signatures is selected when you create a signature, you’ll need to drag the new signature to an email account before you can use it. Custom email signature for mac mail. Launch the Mail app on your Mac. In the Menu Bar, click Mail. Select Preferences (or press ⌘, on the keyboard). Click the Signatures tab. There are many ways to create an email signature in Apple Mail. You could create it in plain HTML code, or you could do it in Microsoft Word. However, the easiest and best way to do it is by using Gimmio. When you create an email signature using Gimmio, it will be compatible across all email clients.
References:
*M. Buro, Simple Amazons endgames and their connection to Hamiltoncircuits in cubic subgrid graphs, Proc. 2nd Int. Conf. Computers andGames, 2000.
*R. A. Hearn, Amazons is PSPACE-complete,cs.CC/0502013.Checkers and DraughtsDescription: Players move pieces diagonally forward onesquare at a time on alternating squares of an n*n board, removingthe other players’ pieces by jumping diagonally over them. Objectis to leave opponent with no move by blocking or jumping allpieces. The 8*8 version is called checkers, but on larger boards itis called draughts.
Status: EXPTIME-complete.
References:
*GJ 256 [GP10].
*A. S. Fraenkel, M. R. Garey,D. S. Johnson, T. Schaefer, and Y. Yesha, The complexity ofcheckers on an N*N board - preliminary report, Proc. 19th IEEESymp. Found. Comp. Sci. (1978) 55-64.
*J. M. Robson. N by N checkers is Exptime complete. SIAM Journal onComputing, 13(2):252-267, May 1984.ChessDescription: This game is both too complicated and toowell-known to describe here in detail, but the basic idea is tomove pieces around an 8*8 board, capturing one’s opponents’ pieces,until the game is ended either by checkmate (one player winning byforcing the capture of the opposing player’s king) or by variouskinds of draws.
Status: This is a finite game, but generalizations to n*n boardsare EXPTIME-complete.
References:
*A. S. Fraenkel and D. Lichtenstein, Computing aperfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, Languages, and Programming,Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31(1981) 199-214.CryptarithmsDescription: In these puzzles, also known asalphametics, a sequence of letters is arranged in the form of anarithmetic problem, a famous example being The problem is to construct a 1-1 mapping from letters to digitsthat makes the arithmetic work out correctly.
Status: This is a finite problem, but generalizations to basesother than decimal are NP-complete.
References:
*D. Eppstein, On theNP-completeness of cryptarithms, SIGACT News 18(3)(1987) 38-40.Dots and boxesDescription: This childhood game is played with penciland paper, starting from a drawing of a rectangular lattice ofdots. The players alternately connect adjacent dots with linesegments; if a player forms a four-segment square he or she scoresa point and gets another move.
Status: WW describes a generalized version of the gamethat is NP-hard, by a reduction from finding many vertex-disjointcycles in graphs. The same result would seem to apply as well topositions from the actual game, by specializing their reduction totrivalent planar graphs. (This is very closely related to, but notquite the same as, maximum independent sets in maximal planargraphs.)
References:
*WW, chapter 16.E. Berlekamp,The Dots and BoxesGame: Sophisticated Child’s Play, A. K. Peters, 2000.CubicDescription: Something of a cross betweenSokoban andSame Game,this puzzle involves pushing blocks left or right in a polygonal region,where they are subject to a gravity that pulls them downward whenever possible.Blocks have colors, and when multiple blocks of the same colorbecome adjacent, they vanish. The goal is to eliminate all blocks.
Status: Friedman claims to prove that Cubic is NP-complete.His reduction clearly shows that it is NP-hard, but it is lessobvious to me that it is in NP.
References:
*E. Friedman,Cubic is NP-complete,Proc.Florida MAA Section Meeting, 2001.15-puzzleDescription: 15 of the 16 positions in a 4*4 matrix arefilled by tiles, leaving one unfilled hole. Tiles adjoining thehole can be shifted into the hole, the object being to form someparticular permutation of the tiles (typically forming a pictureout of fragments printed on the tiles).
Status: this is a finite problem, but can easily be generalizedto n*n matrices. Testing whether a solution exists is in P butfinding the solution with the fewest moves is NP-complete.
References:
*D. Ratner and M. Warmuth, Finding a shortestsolution for the N*N-extension of the 15-puzzle is intractable, J. Symb. Comp. 10 (1990) 111-137.GoDescription: This ancient game is played by placingstones on a 19*19 board. When a group of stones of one color iscompletely surrounded by stones of the other color, the surroundedgroup is removed from the board. The object is to control em
https://diarynote-jp.indered.space
Science and technology journalists pride themselves on the ability to explain complicated ideas in accessible ways, but there are some technical principles that we encounter so often in our reporting that paraphrasing them or writing around them begins to feel like missing a big part of the story. So in a new series of articles called ’Explained,’ MIT News Office staff will explain some of the core ideas in the areas they cover, as reference points for future reporting on MIT research.
In the 1995 Halloween episode of The Simpsons, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wandering across a dark surface etched with green gridlines and strewn with geometric shapes, above which hover strange equations. One of these is the deceptively simple assertion that P = NP.
In fact, in a 2002 poll, 61 mathematicians and computer scientists said that they thought P probably didn’t equal NP, to only nine who thought it did — and of those nine, several told the pollster that they took the position just to be contrary. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving. Roughly speaking, P is a set of relatively easy problems, and NP is a set that includes what seem to be very, very hard problems, so P = NP would imply that the apparently hard problems actually have relatively easy solutions. But the details are more complicated.
Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.
Imagine, for instance, that you have an unsorted list of numbers, and you want to write an algorithm to find the largest one. The algorithm has to look at all the numbers in the list: there’s no way around that. But if it simply keeps a record of the largest number it’s seen so far, it has to look at each entry only once. The algorithm’s execution time is thus directly proportional to the number of elements it’s handling — which computer scientists designate N. Of course, most algorithms are more complicated, and thus less efficient, than the one for finding the largest number in a list; but many common algorithms have execution times proportional to N2, or N times the logarithm of N, or the like.
A mathematical expression that involves N’s and N2s and N’s raised to other powers is called a polynomial, and that’s what the “P” in “P = NP” stands for. P is the set of problems whose solution times are proportional to polynomials involving N’s.
Obviously, an algorithm whose execution time is proportional to N3 is slower than one whose execution time is proportional to N. But such differences dwindle to insignificance compared to another distinction, between polynomial expressions — where N is the number being raised to a power — and expressions where a number is raised to the Nth power, like, say, 2N.
If an algorithm whose execution time is proportional to N takes a second to perform a computation involving 100 elements, an algorithm whose execution time is proportional to N3 takes almost three hours. But an algorithm whose execution time is proportional to 2N takes 300 quintillion years. And that discrepancy gets much, much worse the larger N grows.
NP (which stands for nondeterministic polynomial time) is the set of problems whose solutions can be verified in polynomial time. But as far as anyone can tell, many of those problems take exponential time to solve. Perhaps the most famous exponential-time problem in NP, for example, is finding prime factors of a large number. Verifying a solution just requires multiplication, but solving the problem seems to require systematically trying out lots of candidates.
So the question “Does P equal NP?” means “If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?” Part of the question’s allure is that the vast majority of NP problems whose solutions seem to require exponential time are what’s called NP-complete, meaning that a polynomial-time solution to one can be adapted to solve all the others. And in real life, NP-complete problems are fairly common, especially in large scheduling tasks. The most famous NP-complete problem, for instance, is the so-called traveling-salesman problem: given N cities and the distances between them, can you find a route that hits all of them but is shorter than … whatever limit you choose to set?
Given that P probably doesn’t equal NP, however — that efficient solutions to NP problems will probably never be found — what’s all the fuss about? Michael Sipser, the head of the MIT Department of Mathematics and a member of the Computer Science and Artificial Intelligence Lab’s Theory of Computation Group (TOC), says that the P-versus-NP problem is important for deepening our understanding of computational complexity.
“A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says.
Similarly, Sipser says, “the excitement around quantum computation really boiled over when Peter Shor” — another TOC member — “discovered a method for factoring numbers on a quantum computer. Peter’s breakthrough inspired an enormous amount of research both in the computer science community and in the physics community.” Indeed, for a while, Shor’s discovery sparked the hope that quantum computers, which exploit the counterintuitive properties of extremely small particles of matter, could solve NP-complete problems in polynomial time. But that now seems unlikely: the factoring problem is actually one of the few hard NP problems that is not known to be NP-complete.
Sipser also says that “the P-versus-NP problem has become broadly recognized in the mathematical community as a mathematical question that is fundamental and important and beautiful. I think it has helped bridge the mathematics and computer science communities.”
But if, as Sipser says, “complexity adds a new wrinkle on old problems” in mathematics, it’s changed the questions that computer science asks. “When you’re faced with a new computational problem,” Sipser says, “what the theory of NP-completeness offers you is, instead of spending all of your time looking for a fast algorithm, you can spend half your time looking for a fast algorithm and the other half of your time looking for a proof of NP-completeness.”
Sipser points out that some algorithms for NP-complete problems exhibit exponential complexity only in the worst-case scenario and that, in the average case, they can be more efficient than polynomial-time algorithms. But even there, NP-completeness “tells you something very specific,” Sipser says. “It tells you that if you’re going to look for an algorithm that’s going to work in every case and give you the best solution, you’re doomed: don’t even try. That’s useful information.”
NP-Complete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time. Intuitively this means that we can solve Y quickly if we know how to solve X quickly. A language B is NP-complete if it satisfies two conditions B is in NP Every A in NP is polynomial time reducible to B. If a language satisfies the second property, but not necessarily the first one, the language B is known as NP-Hard. Algorithm C(s, t) is a certifier for problem X if for every string s: s ∈ X iff there exists a string t such that C(s, t) = yes. NP = set of decision problems for which there exists a poly-time certifier.Many of the games and puzzles people play are interesting becauseof their difficulty: it requires cleverness to solve them. Oftenthis difficulty can be shown mathematically, in the form ofcomputational intractibility results: every NP-complete problem isin some sense a puzzle, and conversely many puzzles areNP-complete. Two-player games often have higher complexities suchas being PSPACE-complete.
WW (pp. 218-219; see referencesbelow) is disparaging of this sort of result, writing that ’thisasymptotic result says little about the difficulties of calculatinggood strategies’, describing NP-hard game positions as ’degenerate’and ’relatively dull’, and advocating (as a response to hardnessproofs) looking for additional rules and conditions that would makethe game easier. But to me NP-completeness is not the end but thebeginning of the study of a game: it shows that the game is complexenough that we can encode interesting computational problems withinit. If a game is in P, it becomes no fun once you learn ’the trick’to perfect play, but hardness results imply that there is no suchtrick to learn: the game is inexhaustible. And of courseNP-completeness or PSPACE-completeness doesn’t even rule out thepossibility of computing game values exactly; true, it seems toimply that worst-case-exponential algorithms are required, butthere is still plenty of interesting work in designing, analyzing,and implementing such algorithms.
There is a curious relationship between computational difficultyand puzzle quality. To me, the best puzzles are NP-complete(although some good puzzles are in P, relying on gaps in humanintuition rather than on computational complexity for theirdifficulty). Some puzzles are even harder than NP (for instance,sliding block puzzles and Sokoban are PSPACE-complete) but to methis means only that the problem can have an annoyingly longsequence of manipulations in its solution. For two-player games,one encounters a similar phenomenon at a higher level ofcomplexity. The tree of potential interactions in a game typicallygives rise to PSPACE-completeness results of a sort I find moreinteresting than PSPACE-completeness in puzzles. However some gamesare harder, EXPTIME-complete, which to me means that it maysometimes be necessary for a well-played game to go on for atediously long sequence of moves. Perhaps some games or puzzles inwhich the players start with incomplete knowledge of the game orpuzzle configuration might lead to other types of completeness(e.g. MA-completeness or #P-completeness) for finding the startingmove most likely to succeed, but I know of no such results.
I primarily list here real games and puzzles, games that wereinvented to be played, rather than to be analyzed. So I’m notincluding some of the more artificial entries in e.g. WW orGJ, such as ’sequential truth assignment’. If someone canpoint me to a tournament for these games, a copy of the game soldin stores, or a program for people to play them against theircomputers, I’ll consider adding them.
One caveat: NP-completeness is not a concept that applies to asingle puzzle or game position, or even a finite collection ofpositions. It only makes sense to talk about an infinite family ofproblems as being NP-complete. For this reason games like chesscannot themselves be NP-complete, as they only have a finite(albeit unthinkably large) number of possible positions. In manycases however there is a natural generalization from some finitegame or puzzle to an infinite family of game positions onarbitrarily large game boards, in which it makes sense to talkabout NP-completeness. The fact that these infinite generalizationsare computationally hard gives us some justification for believingthat the original finite games are also hard in some lesswell-defined sense.Index:
Puzzles and solitaire games:Alphametics;Clickomania;Cryptarithms;Cubic;15-puzzle;Instant Insanity;KPlumber;Mah Jongg;Pearl puzzles;Rush Hour;Shanghai;Sokoban
Two-player games:Amazons;Bridge-It;Checkers;Chess;Dots and boxes;Draughts;Go;Hex;Mastermind;Othello;Phutball;Reversi;Shannon switching game;TwixtSome useful general references:
*E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways foryour Mathematical Plays, Academic Press, 1982. We refer to this asWW.
*M. R. Garey and D. S. Johnson, Computers and Intractibility: aguide to the theory of NP-completeness, W.H. Freeman, 1979. Werefer to this as GJ.
*R. K. Guy, ed., Combinatorial Games, Proc. Symp. AppliedMath. 43, AMS, 1990. We refer to this as CG. Seeespecially A. S. Fraenkel, Complexity of games, CG 111-154,as well as Fraenkel’s introduction to the bibliography.
*R. J. Nowakowski, ed., More Games of No Chance,MSRI Publications #42, 2002.We refer to this as MGONC.AmazonsDescription: Players move queens on an n*n board, as part ofeach move shooting an arrow from the moved piece. Arrows move like a chessqueen when shot but are immovable afterwards. The arrows eventuallyblock the movement of the queens; the last player to complete a movewins. Game-play combines go-like goals of surrounding territory withchess-like tactics of blocking opposing pieces’ lines of play.The most commonly used starting configuration involves four queens ofeach color placed around the edges of a 10*10 board.
Status: PSPACE-complete. Endgames in which pieces of opposing colorsare separated from each other are NP-hard.
Follow our guide to create perfect HTML signature in Apple mail. Create a new signature. Let’s go to Mail Preferences Signatures and click “+” button. “Nicereply” name to your signature and add just your full name to your new email signature. Our sample email signature now looks like this. Create signatures In the Mail app on your Mac, choose Mail Preferences, then click Signatures. In the left column, select the email account where you want to use the signature. If All Signatures is selected when you create a signature, you’ll need to drag the new signature to an email account before you can use it. Custom email signature for mac mail. Launch the Mail app on your Mac. In the Menu Bar, click Mail. Select Preferences (or press ⌘, on the keyboard). Click the Signatures tab. There are many ways to create an email signature in Apple Mail. You could create it in plain HTML code, or you could do it in Microsoft Word. However, the easiest and best way to do it is by using Gimmio. When you create an email signature using Gimmio, it will be compatible across all email clients.
References:
*M. Buro, Simple Amazons endgames and their connection to Hamiltoncircuits in cubic subgrid graphs, Proc. 2nd Int. Conf. Computers andGames, 2000.
*R. A. Hearn, Amazons is PSPACE-complete,cs.CC/0502013.Checkers and DraughtsDescription: Players move pieces diagonally forward onesquare at a time on alternating squares of an n*n board, removingthe other players’ pieces by jumping diagonally over them. Objectis to leave opponent with no move by blocking or jumping allpieces. The 8*8 version is called checkers, but on larger boards itis called draughts.
Status: EXPTIME-complete.
References:
*GJ 256 [GP10].
*A. S. Fraenkel, M. R. Garey,D. S. Johnson, T. Schaefer, and Y. Yesha, The complexity ofcheckers on an N*N board - preliminary report, Proc. 19th IEEESymp. Found. Comp. Sci. (1978) 55-64.
*J. M. Robson. N by N checkers is Exptime complete. SIAM Journal onComputing, 13(2):252-267, May 1984.ChessDescription: This game is both too complicated and toowell-known to describe here in detail, but the basic idea is tomove pieces around an 8*8 board, capturing one’s opponents’ pieces,until the game is ended either by checkmate (one player winning byforcing the capture of the opposing player’s king) or by variouskinds of draws.
Status: This is a finite game, but generalizations to n*n boardsare EXPTIME-complete.
References:
*A. S. Fraenkel and D. Lichtenstein, Computing aperfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, Languages, and Programming,Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31(1981) 199-214.CryptarithmsDescription: In these puzzles, also known asalphametics, a sequence of letters is arranged in the form of anarithmetic problem, a famous example being The problem is to construct a 1-1 mapping from letters to digitsthat makes the arithmetic work out correctly.
Status: This is a finite problem, but generalizations to basesother than decimal are NP-complete.
References:
*D. Eppstein, On theNP-completeness of cryptarithms, SIGACT News 18(3)(1987) 38-40.Dots and boxesDescription: This childhood game is played with penciland paper, starting from a drawing of a rectangular lattice ofdots. The players alternately connect adjacent dots with linesegments; if a player forms a four-segment square he or she scoresa point and gets another move.
Status: WW describes a generalized version of the gamethat is NP-hard, by a reduction from finding many vertex-disjointcycles in graphs. The same result would seem to apply as well topositions from the actual game, by specializing their reduction totrivalent planar graphs. (This is very closely related to, but notquite the same as, maximum independent sets in maximal planargraphs.)
References:
*WW, chapter 16.E. Berlekamp,The Dots and BoxesGame: Sophisticated Child’s Play, A. K. Peters, 2000.CubicDescription: Something of a cross betweenSokoban andSame Game,this puzzle involves pushing blocks left or right in a polygonal region,where they are subject to a gravity that pulls them downward whenever possible.Blocks have colors, and when multiple blocks of the same colorbecome adjacent, they vanish. The goal is to eliminate all blocks.
Status: Friedman claims to prove that Cubic is NP-complete.His reduction clearly shows that it is NP-hard, but it is lessobvious to me that it is in NP.
References:
*E. Friedman,Cubic is NP-complete,Proc.Florida MAA Section Meeting, 2001.15-puzzleDescription: 15 of the 16 positions in a 4*4 matrix arefilled by tiles, leaving one unfilled hole. Tiles adjoining thehole can be shifted into the hole, the object being to form someparticular permutation of the tiles (typically forming a pictureout of fragments printed on the tiles).
Status: this is a finite problem, but can easily be generalizedto n*n matrices. Testing whether a solution exists is in P butfinding the solution with the fewest moves is NP-complete.
References:
*D. Ratner and M. Warmuth, Finding a shortestsolution for the N*N-extension of the 15-puzzle is intractable, J. Symb. Comp. 10 (1990) 111-137.GoDescription: This ancient game is played by placingstones on a 19*19 board. When a group of stones of one color iscompletely surrounded by stones of the other color, the surroundedgroup is removed from the board. The object is to control em
https://diarynote-jp.indered.space
コメント