## Pac-Man Is NP-Hard 195

Posted
by
samzenpus

from the not-all-fun-and-games dept.

from the not-all-fun-and-games dept.

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."
## Re:Pac-Man Was 'Solved' (Score:5, Informative)

Yup, posted on /. a while back

http://games.slashdot.org/story/10/12/03/2237200/pac-mans-ghost-behavior-algorithms [slashdot.org]

--->

http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior [gameinternals.com]

--->

http://home.comcast.net/~jpittman2/pacman/pacmandossier.html [comcast.net]

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)

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)

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

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)

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

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

http://en.wikipedia.org/wiki/NP-hard [wikipedia.org]

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

http://en.wikipedia.org/wiki/PSPACE-complete [wikipedia.org]

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

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)

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)

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)

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)*

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)

Roughly speaking, NP-hard ... 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.

(NP = non-polynomial)means that it scales non-polynomially fastNo, 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)

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)

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)

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)

## I'm ridin' spinners, they don't stop (Score:5, Informative)

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].