Catch up on stories from the past week (and beyond) at the Slashdot story archive

typodupeerror

## Pac-Man Is NP-Hard195

MrSeb writes "An Italian researcher with a penchant for retro games — or perhaps just looking for an excuse to play games in the name of science! — has used computational complexity theory to decide, once and for all, just how hard video games are. In a truly epic undertaking, Giovanni Viglietta of the University of Pisa has worked out the theoretical difficulty of 13 old games, including Pac-Man, Doom, Lemmings, Prince of Persia, and Boulder Dash. Pac-Man, with its traversal of space, is NP-hard. Doom, on the other hand, is PSPACE-hard."
This discussion has been archived. No new comments can be posted.

## Pac-Man Is NP-Hard

• #### Re:Pac-Man Was 'Solved' (Score:5, Informative)

on Thursday January 26, 2012 @07:03PM (#38834959)

Yup, posted on /. a while back

--->

--->

I don't know what it is but reading about the internals of how games worked (algorithms, data structures, tricks, etc.) is neat.

• #### Re:What does the hell does NP Hard mean? (Score:4, Informative)

on Thursday January 26, 2012 @07:11PM (#38835011) Homepage

I had the same issue, but better wiki luck... NP-hard was confusing as the article kind of defines it by itself. However, there is a link in it to a more sensible version:

http://en.wikipedia.org/wiki/P_versus_NP_problem [wikipedia.org]

• #### Re:What does the hell does NP Hard mean? (Score:5, Informative)

on Thursday January 26, 2012 @07:13PM (#38835023)
• #### Re:What does the hell does NP Hard mean? (Score:3, Informative)

on Thursday January 26, 2012 @07:13PM (#38835025)
It means it isn't computationally solvable in linear time. A computer would only be able to solve very very simple permutations of an NP hard problem in reasonable amount of time. The more complexity added to the problem space makes the time it takes to solve grow to be something most people would not wait around for.

i.e. Traveling Salesman (look it up, its the classic problem) problem for 4 cities is pretty easy and quickly solved for by a computer. However 100 or 1000 cities takes much much longer for the best algorithms we have to solve it. (think minutes -> days -> decades for orders of magnitude larger problem space)

There's a bit more math to a detailed explanation and this isn't entirely accurate in measurements, but this is the gist of it.
• #### Re:What does the hell does NP Hard mean? (Score:4, Informative)

by jd (1658) <imipak@yah[ ]com ['oo.' in gap]> on Thursday January 26, 2012 @07:14PM (#38835037) Homepage Journal
• #### Re:What does the hell does NP Hard mean? (Score:3, Informative)

by Anonymous Coward on Thursday January 26, 2012 @07:20PM (#38835075)

An oversimplification though - it really means it's not solvable in deterministic polynomial time. An algorithm with O(n^12328372) would still fall under P, because it's solvable deterministically in Polynomial time.

• #### Re:What does the hell does NP Hard mean? (Score:5, Informative)

on Thursday January 26, 2012 @07:47PM (#38835289) Journal

It means it isn't computationally solvable in linear time.

No, it can't be solved in POLYNOMIAL time. For instance, comparative sorting cannot be done in linear, yet is not NP-hard.

Something that is O(n^12387349892319348917359872394872328349872398723985729375982734598275) is in fact insanely hard, yet still not NP-hard.

• #### Re:What does the hell does NP Hard mean? (Score:5, Informative)

by Anonymous Coward on Thursday January 26, 2012 @07:53PM (#38835313)
More or less correct, but you are slightly confused on the definition of NP-Hard.
• NP is the set of problems that can be verified in polynomial time.
• NP-Hard is the set of problems which are provably at least as hard as any problem in NP (in the sense that a solution to an NP-Hard problem can be used to solve any problem in NP with only polynomial additional effort).
• NP-Complete is the intersection of NP-Hard and NP.

It is believed that P != NP, and if any problem that is NP-Hard (usually one just says NP-Complete) turns out to be solvable in polynomial time, then P = NP.

• #### Re:What does the hell does NP Hard mean? (Score:2, Informative)

on Thursday January 26, 2012 @07:57PM (#38835347)
To solve a problem that has 'n' parts in it:

PSpace hard means the problem is relatively simple, maybe check n things n times, which is only n*n things. For example, "For n cities, find the sum of all the distances between all the cities".

NP hard usually means you have to start at one part, then make a new decision each time you want to move on to the next part. The classic example is: "for n cities, start at a city and find the shortest possible distance to visit each city once". Since you have to make a new decision every time, you can solve this problem using permutations: you have n choices for the first city, then n-1 choices for the next city, then n-2 choices for the next city, and so on. To check ALL of the possible routes you can take and select the shortest, you need to check (n)*(n-1)*(n-2)* ... * (2) * (1) things. That's a factorial, and is denoted n!.

So for 12 cities:
12*12 = 144
12! = 479,001,600

For 20 cities:
20*20 = 400
20! = 2.432902008×10^18

The "search space" for problems that are NP Hard explodes to quickly to solve any reasonably sized problem. So basically, computers can solve problems that are PSpace hard, but they can't really solve any NP hard problems that are worth solving. E.g., to solve the NP Hard "traveling salesperson" problem I described above for all the cities in Italy, there's something like 12000 cities, which is (almost) impossible to solve with a computer. For fun:

12000*12000 = 144,000,000
12000! = 1.201858406×10^43741 (and that's just nuts)

The above is not the only way a problem can be NP Hard, but all these kinds of problems have "similar" classes of "time complexity". If you model this "time complexity" (that is, count the number of things you have to check) as a function, PSpace hard problems are polynomials at worst. NP Hard are worse than polynomials. The notation used here is called "Big Oh", and the above two problems are O(n^2) and O(n!), respectively.
• #### Re:What does the hell does NP Hard mean? (Score:5, Informative)

by Anonymous Coward on Thursday January 26, 2012 @08:02PM (#38835375)

Roughly speaking, NP-hard (NP = non-polynomial) means that it scales non-polynomially fast ... e.g. if an algorithm is O(n^n) then it is NP-hard but if it is O(n^3) than it is only P-hard. By this definition, even O(n^lg(n)) is NP-hard and O(N^100) is "only" P-hard.

No, no, no, no. NP does not mean "non-polynomial". In fact, all "P" problems are also "NP". NP means "nondeterministic polynomial", i.e, polynomial in a non-deterministic machine (think a computer with an infinite number of CPUs). It is unlikely that they are "P" ("deterministic polynomial"), but it has not been proven either way. Also, a problem being NP-hard doesn't imply that it is NP. It actually may be harder than NP: in general, to say that a problem is X-hard means that there is no problem of class X that is "harder" than it.

For the precise definition of "harder", the wikipedia article http://en.wikipedia.org/wiki/P_versus_NP_problem is pretty good.

(Hmm. it seems I can't log in from the comment box...)

• #### Re:What does the hell does NP Hard mean? (Score:4, Informative)

on Thursday January 26, 2012 @08:21PM (#38835495)

Assuming NP != P your first sentence is correct. And maybe this is what laymen should know about it. However for completeness...

In general a problem is presented as a string of n bits and the algorithm (Turing Machine) has to decide whether it is acceptable or not (good or bad etc.) For example, take the graph coloring problem. This involves a graph on m vertices and you have to color it using k colors such that neighboring vertices have different colors. The input to the algorithm is a description of the graph and k as a bit-string. And the bit-string is acceptable if there is a proper coloring.

If the Turing machine can decide whether the bit-string with n bits is acceptable in less than p(n) steps where n is a polynomial, then the problem is in P.

NP does *not* stand for Not P.

NP means that there is a witness to the acceptability of a bit-string that can be verified in p(n) steps. For example, the witness for the graph coloring is an actual assignment of the colors to the vertices. It is quite straightforward to verify that the coloring is proper (no neighboring vertices have the same color, it takes less than n^2 color comparisons. NP stands for Nondeterministic Polynomial, I am
not a fan of the name.

NP-Hard means that the problem is such that any NP problem can be reduced to it (with a polynomial correspondance). Therefore, if you had a polynomial algorithm for it than you had one for *all* NP problems. This would imply P=NP and is doubtful to be true. In other words a proof of NP-hardness means: Yes, it is harder than P, at least most scientists think so.

I have no idea yet how the Pac-Man problem is represented as a bit-string. I will find out tomorrow on a lecture...

It is worth mentioning the class co-NP. This is a the class of problems for which there is a witness that the input is *not* acceptable. Think what witness could easily verify that a graph is not k colorable... For example existence of a full k+1 subgraph would suffice but other constructions also prohibit k coloring which have no full k subgraph in them. I do not recall from the top of my head whether k coloring is co-NP or not. But I think it is not, here is why:

There is a conjecture that may have more chance than P = NP. And that is: P = NP intersect co-NP. That is if both acceptability and non-acceptibility can be polynomially verified then there would be a guaranteed polynomial algorithm. So far this appears to be the case.
The last famous problem that is NP and co-NP at the same time and was found to be in P was prime testing.

And of course there are many, many other complexity classes...

• #### Re:What does the hell does NP Hard mean? (Score:5, Informative)

on Thursday January 26, 2012 @08:45PM (#38835639) Journal

Mod parent down, please. The definition of NP above is circular -- if NP actually stood for non-polynomial, then P!=NP by definition. That would be begging the question.

Rather, NP means "nondeterministic polynomial time." [wikipedia.org] It is the class of problems whose solutions can be verified in polynomial time. NP-hard are the "hardest" problems in this class. All algorithms known to solve problems in this class are super-polynomial. The question of "P==NP?" really amounts to "is there an undiscovered polynomial solution to every problem that we currently think is NP-hard?" or even more simply, "if a problem's solution can be verified in polynomial time, can the solution be discovered in polynomial time?"

• #### Re:Tetris isn't NP-hard anymore (Score:1, Informative)

by Anonymous Coward on Friday January 27, 2012 @03:06AM (#38837069)
Posting anon to preserve mod upvotes for the article.

It makes sense, and I kinda laughed when I saw the comment and instantly knew it was Tepples. The guy has coded the most configurable version of Tetris I've ever seen [pineight.com] after all.
• #### Key words: prior to 2001 (Score:4, Informative)

<tepples&gmail,com> on Friday January 27, 2012 @07:59AM (#38838285) Homepage Journal
Most Tetris products prior to 2001, such as Super Tetris 3 for Super Famicom, use the old randomizer, possibly with some slight modification to ensure no immediate repeats.
• Tetris for Game Boy has a 2/32 chance of the same piece and a 5/32 chance of each other piece.
• Tetris for NES will reroll once if the piece matches the last piece.
• Tetris the Grand Master will reroll three or five times if matches one of the last four pieces.
• The New Tetris for Nintendo 64 deals from a 63-card deck with nine of each shape.
• New games, such as Tetris Worlds, Tetris DS, and Tetris Party, all use the new randomizer that shuffles sets of all 7 shapes. Start a new game of Tetris DS and notice how the falling piece and the next 6 pieces are all different.
• #### I'm ridin' spinners, they don't stop (Score:5, Informative)

<tepples&gmail,com> on Friday January 27, 2012 @08:06AM (#38838319) Homepage Journal

tetris DS does get to the point where the piece lands nearly as soon as it appears

This behavior is called 20G [harddrop.com], and it's also seen in "Death" mode of Tetris the Grand Master 2 [youtube.com] and "Shirase" mode of Tetris the Grand Master 3 [youtube.com].

however you can keep it from fixing to the stack by rotating it and wiggling it constantly.

This infinite spin [ytmnd.com] behavior has become the standard since 2001 [harddrop.com], despite reviewers' assertions that "it actually breaks Tetris" [gamespot.com].

#### Related LinksTop of the: day, week, month.

"For the man who has everything... Penicillin." -- F. Borquin

Working...