×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Pac-Man Is NP-Hard

samzenpus posted more than 2 years ago | from the not-all-fun-and-games dept.

Math 195

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

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

195 comments

stupid (-1, Troll)

Anonymous Coward | more than 2 years ago | (#38834767)

This shit is stupid.

Tetris isn't NP-hard anymore (5, Interesting)

tepples (727027) | more than 2 years ago | (#38834799)

I am reminded of an proof from a few years ago [slashdot.org] that Tetris is NP-hard. But this proof is for old versions of Tetris that used a pure randomizer, not the new bag style generator in games since 2001 [harddrop.com]. This randomizer incidentally allows playing forever [harddrop.com].

Re:Tetris isn't NP-hard anymore (5, Insightful)

Anonymous Coward | more than 2 years ago | (#38834851)

It would be more accurate to say Tetris isn't Tetris anymore.

Re:Tetris isn't NP-hard anymore (-1)

Anonymous Coward | more than 2 years ago | (#38834881)

most versions of tetris use pure randomizers, faggot.

Re:Tetris isn't NP-hard anymore (5, Interesting)

Formalin (1945560) | more than 2 years ago | (#38834967)

I think the gameboy one stopped speeding up and some point, letting you play forever, well at least until you ran into a batch of randomness that gave you too many bad pieces.

The NES one, on the other hand, was actually impossible after a certain level... the blocks fell faster than you could get them to the edges of the screen.

There was a version of tetris someone made, maybe from here... that always gave you the worst possible piece.
Googling 'ragetris' tells me it was called 'hatetris [qntm.org]'.

Not entirely related to things being NP-hard, but yeah.

Re:Tetris isn't NP-hard anymore (1)

Formalin (1945560) | more than 2 years ago | (#38835057)

Hmmm. Further research tells me the bit about NES getting to impossible speeds is only a figment of my imagination. Perhaps it was a different version...

Achin' to play some tetris now. It's been years...

Re:Tetris isn't NP-hard anymore (1)

Lehk228 (705449) | more than 2 years ago | (#38835459)

tetris DS does get to the point where the piece lands nearly as soon as it appears, however you can keep it from fixing to the stack by rotating it and wiggling it constantly.

Re:Tetris isn't NP-hard anymore (0)

Anonymous Coward | more than 2 years ago | (#38835721)

fire up emacs, m-x tetris

Re:Tetris isn't NP-hard anymore (1)

Anonymous Coward | more than 2 years ago | (#38836591)

No, you're correct. In NES tetris, past level 29, it is generally considered humanly impossible to get the pieces to the sides of the well (though it can still be done with emulators, framestepping, etc.).

Re:Tetris isn't NP-hard anymore (0)

Anonymous Coward | more than 2 years ago | (#38836675)

https://www.youtube.com/watch?v=gIy7xF68H1w

"This is the fastest speed the NES game is capable of", apparently.

CAPTCHA: deadly

Re:Tetris isn't NP-hard anymore (1)

Anonymous Coward | more than 2 years ago | (#38835141)

bastet, bastard tetris.

Re:Tetris isn't NP-hard anymore (0)

Anonymous Coward | more than 2 years ago | (#38836161)

Many versions of Tetris have a 'bastard mode' that does that.

Re:Tetris isn't NP-hard anymore (0)

Anonymous Coward | more than 2 years ago | (#38836335)

The gameboy version sped up forever also.

I know this because I had a Game Genie with codes to get only the long straight blocks... After a certain point it would move too fast to get them to the sides, as you described.

and Pac-Man never was (1)

Trepidity (597) | more than 2 years ago | (#38835293)

They use a pretty conveniently screwed up variant of Pac-Man for their proof, not the actual Pac-Man, where there's free choice and arbitrarily fast transitions between the different ghost modes, so it's even further from true here than for Tetris.

Re:and Pac-Man never was (5, Interesting)

hal2814 (725639) | more than 2 years ago | (#38835677)

They didn't actually use Pac-Man in their proof. They modeled up a close approximation which is not Pac-Man at all. For example, FTA:

"We assume full configurability of the amount of ghosts and ghost houses, speeds, and the durations of Chase, Scatter, and Frightened modes (see [1] for definitions)."

That's all well and good but there is no configurability with the level designs, amount of ghosts, or ghost houses.

Re:and Pac-Man never was (0)

Anonymous Coward | more than 2 years ago | (#38836607)

The "conveniently screwed up variant" was necessary because in the original Pac-Man, the ghost behavior is not random, so "perfect play" is possible by traversing the maze on each level in a specific pattern (ignoring the buggy split-screen level).

Re:Tetris isn't NP-hard anymore (2)

b4dc0d3r (1268512) | more than 2 years ago | (#38835663)

I am embarrassed to say, this is the most interesting comment I have seen on this site in well over X;X3 years. You know the changes in the Tetris engine, and links to a strategy guide for playing Tetris infinitely.

Screw mod points, I salute you, sir or madam or intermediate.

nothing of value was gained (3, Funny)

kyrio (1091003) | more than 2 years ago | (#38834801)

I'm pretty sure we knew this from actually playing the games.

Re:nothing of value was gained (5, Insightful)

fuzzyfuzzyfungus (1223518) | more than 2 years ago | (#38834905)

It would actually be somewhat surprising(especially with games where the twitch factor keeps the player from strategizing too deeply) if you could discern the computational complexity of a game just by playing it....

Naively, I'd imagine that a human player most closely resembles a stochastic hill-climbing agent, providing the input at each tick that seems most likely to improve their situation in the relatively short term. That would make them brutally efficient at some problems, miserably hung up on local maxima or discontinuities in others; but not necessarily provide much correlation between difficulty of play and difficulty of problem.

Re:nothing of value was gained (4, Insightful)

martin-boundary (547041) | more than 2 years ago | (#38835171)

Naively, I'd imagine that a human player most closely resembles a stochastic hill-climbing agent,

That's too naive. Most game players don't just play the game once (start game, yay, play, win a little, die, never play this game again). Instead, they play many times, and use their previous knowledge as leverage to improve their performance.

That puts the hill climbing analogy into more modern optimization territory, like multiple randomized restarts, adaptive strategies, etc. As such, the odds of winning are high when players are willing to put in the hours.

Re:nothing of value was gained (5, Interesting)

VortexCortex (1117377) | more than 2 years ago | (#38836671)

Most game players don't just play the game once (start game, yay, play, win a little, die, never play this game again).

I'd have to disagree, as both a Game Player and Game Developer. Gone are the days when Sonic or MegaMan sat in your console for weeks while you tried endlessly to beat it. Today's game players are EXACTLY like what you describe. That's why we have to baby them & lead them into playing the game -- They have many other options, a virtually endless supply of games to Try and fail at until one lets them win.

I sit "average" gamers of all age ranges in front of the games from yesteryears and the majority do exactly what you describe when given a choice to switch between any classic game on the shelf. They play the longest on familiar or easy to play titles.

PacMan is HARD. Rarely will you find a decent arcade with 5 lives instead of 3, and longer power-up periods (selectable via dip switches or .conf files). However, people don't play games to beat them, now they play to be entertained, and an unforgiving game that eats your quarters or $50 at once can't compete with the free casual games of today.

I think some balance can be found -- A short introduction to get you interested in the mechanics and/or story, followed by an increasingly engaging experience, but there's a fine line between too steep a learning curve and too boring of a game.

As for whether or not PacMan is NP Hard, I'd say that since it's 100% fully deterministic it's actually not. It's easy as hell to map out then play perfectly every single time afterwards, especially if you have the source code "running" through your brain and can can predict exactly what the Ghosts will do. Also, the same damn level over and over again is quite boring... That's why when I was required to learn JavaScript I created my own rendition [memebot.com] that was non deterministic (pseudorandomly so) as well as had many differing levels.

Re:nothing of value was gained (2)

johnnyb (4816) | more than 2 years ago | (#38836489)

Interestingly, there is a conference this summer dealing with humans and their abilities to perform computation. It's titled Engineering and Metaphysics [eandm2012.com], and deals with the relationship between humans, physics, and reality.

Re:nothing of value was gained (1)

JustSomeProgrammer (1881750) | more than 2 years ago | (#38835089)

I was actually quite surprised that a game that is developed through a simple program would be NP-Hard and that a more advanced game with more stuff to do is actually easier.

How can Pac-Man be hard when there are patterns? (0)

Anonymous Coward | more than 2 years ago | (#38834919)

Just program in the patterns.

Pac-Man Was 'Solved' (1)

Anonymous Coward | more than 2 years ago | (#38834929)

Pac-Man is solved. There's a book on how to beat it (sorry, I don't know the title). Well, at least the book tells you how to play the game until the arcade glitches out...

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

UnknownSoldier (67820) | more than 2 years ago | (#38834959)

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.

What does the hell does NP Hard mean? (5, Insightful)

hairyfish (1653411) | more than 2 years ago | (#38834931)

Yes I RTFA and wiki'd it but that page makes no sense to me either. Can someone give me the NP Hard/PSpace Hard for dummies version? Or maybe give me an analogy using football fields?

Re:What does the hell does NP Hard mean? (-1)

Anonymous Coward | more than 2 years ago | (#38834947)

Let me give it a shot.

If you are gay, therefore you are a nigger.

If you are a nigger, you're not necessarily gay.

Hope that clears things up. I await my Nobel.

Re:What does the hell does NP Hard mean? (-1)

Anonymous Coward | more than 2 years ago | (#38835013)

It's comments like these that makes it easier to pass laws limiting free speech. So if you post this message, you can be proven a commie supporter but a commie supporter can't be proven to post this message.

Re:What does the hell does NP Hard mean? (0, Troll)

Anonymous Coward | more than 2 years ago | (#38834963)

Here [4chan.org] is a site that may be more your speed.

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

RJFerret (1279530) | more than 2 years ago | (#38835011)

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? (-1)

Anonymous Coward | more than 2 years ago | (#38835021)

Mathematicians have wet dreams over the term NP-hard but IMHO it's a bit misleading. It doesn't describe how hard a problem is in an absolute sense ... it describes how quickly the difficulty scales up as more inputs are added.

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.

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

Anonymous Coward | more than 2 years ago | (#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? (0)

Anonymous Coward | more than 2 years ago | (#38836523)

You can't have an "infinite number" of anything. Infinity doesn't work that way. It simply means arbitrarily large, as in "given any finite value N, I have more than N CPU's in my computer". There's no concept of an infinite number.

Also, nondeterminism doesn't really work the way that would imply. A more exact definition is that if you already have the answer you can confirm it deterministically in the complexity class. You're basically saying that you want to simultaneously test every possible answer on a separate CPU in parallel and have the one which tests positive report back, but for someone who's trying to learn the concept, your way is only confusing.

Re:What does the hell does NP Hard mean? (0)

Anonymous Coward | more than 2 years ago | (#38835483)

wtf is g? gravity? define your variables. ef'ing math...

Re:What does the hell does NP Hard mean? (0)

Anonymous Coward | more than 2 years ago | (#38836303)

it is not g(n), but rather lg(n) which is the binary logarithm, i.e. log_2 (n). Unlike science where 10 is the natural base or calculus where e is, in comp sci, 2 is the natural base and so complexity often uses lg() rather than log() or ln(). lg(n) infinity, n^lg(n) is still bigger. Even more extreme would be something like O(n^ lg(lg(n)) for which n must be bigger than 2^(2^100) to beat n^100. This n is more than 10^(10^10), a 1 followed by 10 billion 0's.

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

Morty (32057) | more than 2 years ago | (#38835639)

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:What does the hell does NP Hard mean? (2)

ProfessorPillage (1964602) | more than 2 years ago | (#38835955)

Right, except that NP-hard problems don't have to be in the NP class, they can be harder. They are the problems, not necessarily in NP, that are at least as hard as the hardest problems in NP. You're thinking of NP-complete or equivalent.

Re:What does the hell does NP Hard mean? (2)

Jason1729 (561790) | more than 2 years ago | (#38836561)

Totally wrong. First, as the previous response said NP-hard is a separate set from NP. The intersection of the two sets is called NP-complete. NP-hard are the "hardest" problems in this class is axiomatically wrong because NP-hard is not a subset of NP.

Second, by definition of NP-hard, given a polynomial-time solution to any NP-hard problem, you can solve *every* NP problem in polynomial time, so what you meant to say is The question of "P==NP?" really amounts to "is there a polynomial-time solution to any problem that has been rigorously proven to be NP-hard?

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

JustSomeProgrammer (1881750) | more than 2 years ago | (#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? (3, Informative)

Anonymous Coward | more than 2 years ago | (#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? (0)

Anonymous Coward | more than 2 years ago | (#38836495)

But an oversimplification that didn't use the phrase "polynomial time" without defining it, like (literally) every other response that offered an explanation, and therefore provided the only real explanation.

Re:What does the hell does NP Hard mean? (0)

Anonymous Coward | more than 2 years ago | (#38835091)

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

Not quite. NP hard problems have a worst-case exponential complexity.
So the class of problems that is not NP-hard include those solvable in linear, polynomial, time etc. (not just linear time)

Re:What does the hell does NP Hard mean? (2)

FrootLoops (1817694) | more than 2 years ago | (#38835449)

Also not quite. NP-hard problems can be as difficult as one likes. The key is that, given an oracle for an NP-hard problem, you can solve any NP problem within a polynomial amount of time (where calls to the oracle take unit time).

Another point to be mindful of is that there are runtimes between polynomial and exponential.

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

snowgirl (978879) | more than 2 years ago | (#38835289)

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? (1)

FrootLoops (1817694) | more than 2 years ago | (#38835399)

Mod up (or mod GP down). Confusing linear and polynomial time is a horrible mistake, and even then the GP assumes P != NP without saying so.

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

sustik (90111) | more than 2 years ago | (#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? (2, Insightful)

lgw (121541) | more than 2 years ago | (#38835183)

OK, without the wiki dive, here's the short version:

  • * P is the set of problems that can be solved in polynomial (or better) time.
    * NP-Complete is the set of problems that (probably) can't be solved in polynomial time, but the solution can be verified in polynomial time.
    * NP-Hard is the set of all problems that can't be solved in polynomial time.

    Only two of those are actiually distinct. We think P and NP-complete are different, which would mean NP-Complete and NP-Hard are the same (IIRC).

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

Anonymous Coward | more than 2 years ago | (#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? (2)

dkf (304284) | more than 2 years ago | (#38835423)

We think P and NP-complete are different, which would mean NP-Complete and NP-Hard are the same (IIRC).

There are many problems that are wholly outside polynomial complexity (used to work with some, years ago, and they were brutes even with a Top-500 supercomputer of the day). That means that NP-Hard must not be just NP-Complete; there's got to be higher levels in there.

Re:What does the hell does NP Hard mean? (2)

lgw (121541) | more than 2 years ago | (#38835507)

But could you verify the solutions in polynomial time?

Re:What does the hell does NP Hard mean? (0)

Anonymous Coward | more than 2 years ago | (#38835745)

That doesn't matter for being NP-hard. As another AC posted above, "NP-Hard is the set of problems which are provably at least as hard as any problem in NP", and an NP-Complete problem is one that is both NP and NP-hard.

Re:What does the hell does NP Hard mean? (0)

Anonymous Coward | more than 2 years ago | (#38836557)

Mod down, this is plain wrong.

Re:What does the hell does NP Hard mean? (0)

Anonymous Coward | more than 2 years ago | (#38835231)

So, say the way a computer solves a problem is like going through a maze. At each step, you can choose one of a few paths, and eventually you'll reach an exit (symbolizing you've solved the problem), or you'll have covered the entire maze and you can conclude that there aren't any exits, so you stop trying.

Say that the maze can be enormous -- infinite, even. If we're going to classify a maze as P, it means that there is a deterministic method for walking that maze where you can find an exit, or safely conclude that there aren't any exits. And, this method has to work in polynomial time -- this means that as the maze grows larger, the number of steps it takes to deterministically traverse this maze doesn't grow faster than some polynomial function. So, if you have a maze of size N, then any deterministic function to traverse that maze that is guaranteed to complete in less than N^p steps (for a fixed p) can be considered polynomial time. (contrast this with a function that traverses a maze of size N in N^N steps, or N! steps -- these functions grow much more quickly than polynomial functions).

All of the mazes that are solvable this way are considered to be in class P (which stands for Polynomial Time).

Now say that we remove the deterministic constraint (but everything else stays the same). This means that at each step, instead of choosing one path to take you can simultaneously try each path. This doesn't mean you get to skip steps -- if you had to go left, then right, then left to get to an exit, you'd still have to go through those three steps. It's more like, you can make a copy of yourself every time you face a decision, and send all of your copies down each path.

In this case, if *any one* of the paths you take yields an exit, or concludes that it's impossible to find an exit, then you consider the maze solved. If you can still solve this maze in polynomial time with your new super powers (and we only count the number of steps the 'solution' copy took), then we consider it a part of the class NP (which stands for non-deterministic polynomial time --- *NOT* non-polynomial time, as many people mistakenly believe).

There you have it --

There are all kinds of really useful and interesting problems that are in NP (the traveling salesman problem is a good example), and NP is the go to definition of a problem space that is infeasible to solve with computers (a lot of cryptography depends on the crypto system being theoretically infeasible to crack, rather than impossible to crack). So proving things are in various problem classes has a lot of utility.

NP-Hard is a subset of NP problems --- if a problem is in NP-Hard, then it's at least as hard as the hardest problem in NP.

Re:What does the hell does NP Hard mean? (1)

Jason1729 (561790) | more than 2 years ago | (#38836629)

Mostly wrong, and even the parts that a right, you make far more confusing than the need to be. I think you're using your maze example to try and represent branching within the algorithm and only confusing yourself. How would the maze for multiplying two numbers together (a P algorithm) look different from the maze for the satisfiability problem (an NP-complete algorithm)? I really can't picture your maze for either of them.

As far as your nondeterminism allowing you to simultaneously try each path, make copies of yourself, etc. It's just confusing, it makes NP harder to understand, and really clouds what's actually going on. Look at it this way. Nondeterminism allows you to always choose the correct path. Every branch you come to, you have the magic ability to pick the correct path on the first try. I call it a magic ability, you call it a super power. Forget about trying to understand how you're trying all paths; the whole concept is a mathematical model, so why inflate it with bloat trying to explain something that need not be explained?

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

Faulkner39 (955290) | more than 2 years ago | (#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? (2)

Faulkner39 (955290) | more than 2 years ago | (#38835469)

Correction: I confused PSpace with P. The above definition is for P and NOT PSpace. Haven't spent much time thinking about complexities ABOVE NP hard. PSpace actually considers the "memory" you need to solve the problem. This is relevant when you talk about Turing machines, where you have to use "tape" that you "write on" while solving the problem. The thing that's been proved is that you only need a polynomial amount of memory (relative to 'n') to solve problems that need NP Hard time.

Re:What does the hell does NP Hard mean? (0)

Anonymous Coward | more than 2 years ago | (#38835355)

Suppose that n football players are standing in a field, and want to pass the ball between them so that each player gets the ball exactly once. The question is whether this is possible so that the ball never travels more than x feet.

This problem is NP. One of the things this means is that, if the answer is 'yes', then I can give you some extra information that will help you "easily" (see below) verify it, but if it's 'no' then I cannot. For example, I can give you the correct order to pass the ball, if one exists, and you can "easily" verify that it qualifies.

This problem is also NP-hard. This means that if you could "easily" solve this problem yourself (without my hint), then you could do the same for *every* NP problem out there. This would have significant implications, for example many security techniques rely on some NP problem being "hard" to solve.

It is conjectured and widely believed, but not yet proved or disproved, that NP is different than P, meaning that NP-hard problems cannot be "easily" solved.

In the above, "easy" means that there's some polynomial p(n) and an algorithm which always solves the problem correctly within time p(n), for any size n of the problem.

PS: I'm not an American. Good thing wikipedia's article about football is clearer than about NP.

Re:What does the hell does NP Hard mean? (1)

godrik (1287354) | more than 2 years ago | (#38835759)

I read so much wrong answer replying to you post I attempt a new explanation.

A problem is in P if there is a polynomial time algorithm to solve it. It means, that there is a algo which will always find the correct answer AND the algorithm an instance of the problem in at most a*n^b operations, where a and b are constants and n is the size of the smallest file that can contain an instance of the problem. Example of problems in P includes: deciding whether a number is divisible by2, whether a number is prime, finding a shortest path between two points in a city, solving linear equations,...

A problem is in NP, if a solution of an instance of a this problem has a solution whose size is at most a*n^b. I do not care about algorithms that generate that solution, juste about the size of the solution. Interestingly, all problem that are in P are also in NP. The reverse, might or might not be true.

A problem is NP-hard if, assuming we have an algorithm that can solve that problem in constant time for (think one assembly instruction on your computer), it can be used to solve all the problems in NP in polynomial time.

If a problem is NP-hard AND in NP, then the problem is said to be NP-complete. This class of problem is interesting because, some mathematical techniques have been used to show that some practically relevant problems are NP-complete: the most comon one if the post delivery problem: "is it possible to deliver the mail for all the inhabitant of a given city while travelling less than a given number of miles".

There are no known polynomial algorithms for NP-complete problems. And actually, most theoreticians believe that we do not know any because no such algorithm exist. So if you have an algorithm that solve all problems in a*n^b operations, then b is typically not a constant, it is a function of n. (or at least we believe)

Notice that all the talk on P, NP and NP-complete consider ALL the instances of a given problem. Some instances might be easy for some algorithms but if a problem is NP-complete (or NP hard), then there exists an instance which the algorithm can not solve in polynomial time (or at least that what we believe).

Interestingly, all NP-complete problems are "equivalent", if we can solve one in polynomial time, we can solve them all in polynomial time. That mandate the search for weird problems that can be shown to be NP-complete. Because solving any of them in polynomial time would solve them all. And we have been trying to do that for more than 60 years.

Moreover, because of how NP is defined, all NP-complete problems can be solved by an exponential algorithm (one that would take less than a*n^(b*n^c), where a, b and c are constants)

P-space is a little bit different. All the classes I mentionned before, P, NP, NP-Complete are interested in runtime of the algorithm and are sometimes called P-time, NP-time, NP-time-complete. P-space is interested in how much memory is required to solve a problem. Interestingly, P-time and NP-time are in P-space.

Showing that doom is P-space-hard is interesting because there are not too many practically relevant problems that are shown to be P-space-hard.

I hope it helps people understand.

Re:What does the hell does NP Hard mean? (0)

Anonymous Coward | more than 2 years ago | (#38835869)

Yes I RTFA and wiki'd it but that page makes no sense to me either. Can someone give me the NP Hard/PSpace Hard for dummies version? Or maybe give me an analogy using football fields?

That's OK, just hand me your nerd card. The door's over there, please take the first left and you'll find Digg if you keep walking.

Re:What does the hell does NP Hard mean? (1)

Surt (22457) | more than 2 years ago | (#38835915)

So, most computer scientists assume P != NP. But there's no proof (yet).

NP-hard is a class of problems, the solution of which is guaranteed not more efficient than NP. That is, there is a demonstrated way to convert an NP-complete problem (let's call that problem NPC) to the hard problem (NPH), and the conversion can be done in polynomial time.

How does that work? Well, if you were able to solve the NPH problem more efficiently (in polynomial time or better), you'd first use the conversion (costing you only polynomial time, as required above), then use your efficient NPH solver (again, polynomial time), and the combined solution would be polynomial time (The additive time of two polynomial algorithms is also polynomial). If you had any such NPH solution, it would be a satisfactory proof that P = NP. If you assume that P != NP (as most of us do ...), then this means that NPH, like NPC and NP are, in fact, 'harder' than problems that are merely polynomial in difficulty.

So understanding all that, NPH is a class of problems. It includes all NPC problems as a subset, plus some problems that are even harder.

Re:What does the hell does NP Hard mean? (1)

betterunixthanunix (980855) | more than 2 years ago | (#38836269)

  1. P -- problems that can be solved in time that grows according to some polynomial of the size of problem (e.g. sorting -- can be solved in n^2 time by bubble sort).
  2. NP -- problems that can be verified in polynomial time; we think that some of these problems cannot be solved in polynomial time. For example, graph three colorability is in NP and is not known to be in P; this means that if I show you a 3-colored graph, you can check that it is indeed 3-colored in polynomial time, but if I give you a graph and ask you to compute its 3-coloring, the amount of work you do will be exponential in the size of the graph (unless P=NP).
  3. NP-complete -- problems for which any polynomial time solution would imply a polynomial time solution for any NP problem and for which a proof that shows there is no polynomial time algorithm would imply that none of the NP-complete problems can be solved in polynomial time.
  4. NP-hard -- problems which any NP-complete problem can be reduced to i.e. given an NP-complete problem, it can be reexpressed as an NP-hard problem. Another way to state this is that NP hard problems cannot be solved faster than NP complete problems. Note that while a polynomial time solution to an NP-hard problem would imply P=NP, it is not the case that a proof that NP-hard != P implies P!=NP.
  5. PSPACE -- problems which can be solved using a polynomial amount of space. Note that this not only includes P, but also NP and NP-hard, as well as even harder to solve problems.
  6. PSPACE-complete -- same as NP-complete, but for PSPACE rather than NP.
  7. PSPACE-hard -- ditto.

...or you can consult the nearest copy of Goldreich's computational complexity text, which covers these in more detail than Slashdot ever could.

Re:What does the hell does NP Hard mean? (2)

elsurexiste (1758620) | more than 2 years ago | (#38836333)

Ron Fagin (a heavyweight in this topic) once told me about this in layman's terms. Can't remember precisely, but this is more or less what he said:

I assume you know Sudoku. Solving a Sudoku game from the clues has a certain difficulty (complexity). Compare it with just verifying that a Sudoku with all its squares filled is a valid solution. You can see that verifying a solution is much faster than finding one! In general, we can accept that verifying is faster than solving... but even though it's intuitive, no one has proven it :) .

He left out what he meant about complexity, though...

This is why religion is still popular (1)

Powercntrl (458442) | more than 2 years ago | (#38836429)

Complex mathematical probability equations can make your brain hurt even if you are the person your non-techie friends and family call when their computer "got some viruses off the Internet". Personally, it helps me relate to why lesser folks can't understand simpler scientific principles (like fuckin' magnets) and prefer "that's how God made things" as their explanation.

No it's not (0)

Anonymous Coward | more than 2 years ago | (#38834973)

I guess he forgot to play the actual stand-up game. There's a pattern.

http://www.math.montana.edu/~hyde/pacman/

I used to play from the moment my mom went into the grocery store, until she checked out.

Re:No it's not (0)

Anonymous Coward | more than 2 years ago | (#38835343)

Since you obviously don't understand what "NP-hard" means why do you bother posting?

What is the ideal level of complexity? (1)

jd (1658) | more than 2 years ago | (#38834999)

Assuming that this method of measuring complexity is actually useful, is there an ideal level of theoretical complexity in a computer game?

(This is not necessarily the same as the complexity of play - Doom is, after all, very easy to play but PSPACE-hard problems are extremely difficult problems to solve.)

Any retro-gamers here want to determine the theoretical complexity of Wizardry, Atic Atac, Knightlore, Citadel or Cholo?

Is there any correlation between the complexity and how long the game stuck in people's minds?

Re:What is the ideal level of complexity? (2)

GoodNewsJimDotCom (2244874) | more than 2 years ago | (#38835123)

Speaking as a game designer/programmer, I like it when games are too hard to solve outright, but not too hard to employ strategies based on your current state. The more possible strategies people can employ in different situations gives people the fun-factor.

Pacman is NOTHING!!! (1)

oldhack (1037484) | more than 2 years ago | (#38835317)

NP-hard Pacman's got nothing on Undecidable Ms. Pacman. You don't even wanna know about sheer evil that is Mrs. Pacman.

Re:Pacman is NOTHING!!! (3, Funny)

godrik (1287354) | more than 2 years ago | (#38835603)

NP-hard Pacman's got nothing on Undecidable Ms. Pacman.

There is a known theorem that says: "As soon as you throw women in, nothing is decidable anymore!"

I'm NP-Hard (0, Offtopic)

Anonymous Coward | more than 2 years ago | (#38835411)

Thats what my wife said.

Get a real job (0, Offtopic)

Anonymous Coward | more than 2 years ago | (#38835485)

This is just why the Italian economy is failed.

Where is dem pretty pictures? (1)

Bonobo_Unknown (925651) | more than 2 years ago | (#38835501)

Holy shit I don't want to read an article, led alone a scientific, peer reviewed article. Isn't there a pretty picture of a graph somewhere?

What I got from the comments is.. (4, Insightful)

Anonymous Coward | more than 2 years ago | (#38835807)

....that for a bunch of nerds nobody seems to know what NP really stands for

How you define the problems matter (4, Interesting)

JoshuaZ (1134087) | more than 2 years ago | (#38835823)

This is a good example of how you define the problems mattering. For example he declares Starcraft to be at least NP-hard. But if one is allowed to use trigger events and some other aspects of the scenario editor one can actually fully model a Turing machine in Starcraft. You do this in a straightforward way by giving trigger based instructions to a unit (say a probe) and have it move along a line where having some other specified unit in an adjacent spot represents a 1, or one has a 0 if the unit isn't there. This is a much stronger result than the result he has. But it seems that his version of Starcraft as defined doesn't let you use event triggers (or at least he doesn't mention them). So he only gets the weaker result of Starcraft being NP hard.

In the 1970s and 1980s, showing something was NP-hard used to be a big deal and there are a lot of papers from that time period. As the techniques improved one occasionally got some fun with someone showing that some new game was NP hard or NP complete (Tetris was done a few years ago as was Minesweeper). But these are really not considered to have any real insight. This paper is a bit more impressive because of the sheer number of games, and the systematic way he approaches the games especially his Metatheorem 1 and Metatheorem 2. Those two results are not obvious. Overall this is quite clever and makes for a fun read.

he got at least one detail wrong (2)

PJ6 (1151747) | more than 2 years ago | (#38835841)

For Load Runner -

On the rst traversal, the avatar can safely land on top of the enemy and dig a hole on the left. The AI will make the enemy fall in the hole, so the avatar may follow it, land on its top again, and proceed through a ladder, while the enemy remains forever trapped in the hole below. The avatar cannot attempt to traverse the gadget a second time without getting stuck in the hole where the enemy previously was.

That's just not true. Grain of skepticism += 1.

Re:he got at least one detail wrong (0)

Anonymous Coward | more than 2 years ago | (#38836199)

For Load Runner -

On the rst traversal, the avatar can safely land on top of the enemy and dig a hole on the left.
The AI will make the enemy fall in the hole, so the avatar may follow
it, land on its top again, and proceed through a ladder, while the enemy
remains forever trapped in the hole below. The avatar cannot attempt to
traverse the gadget a second time without getting stuck in the hole where
the enemy previously was.

That's just not true. Grain of skepticism += 1.

What is wrong with that? If you cannot replicate that gadget, you probably are not playing with the original Load Runner, but a remake, or a sequel, or a clone. There are levels in the original game that are based precisely on that behavior of the monsters (I'm referring to the sentence "The AI will make the enemy fall in the hole"). Just try the arcade version (MAME), look for a level that has some similar configuration, and see for yourself. Mastering the enemies' reactions and AI in Lode Runner is a key aspect for beating harder levels, so pretty much any experienced player should agree that the gadget works as described in the paper.

Re:he got at least one detail wrong (0)

Anonymous Coward | more than 2 years ago | (#38836551)

I hope the Lode/Load typo is yours. Off to check TFA...

Re:he got at least one detail wrong (1)

Anonymous Coward | more than 2 years ago | (#38836631)

Yes, it's a typo. The game is Lode Runner, and the gadget described in the paper works in the original version of the game. It does not work in some later remakes, such as Sierra's "Lode Runner: The Legend Returns," dated 1994.

Hard to believe (1)

garaged (579941) | more than 2 years ago | (#38836025)

It is hard to believe since I played continually over 2 hours without loosing all lives, I remember I found a single path tha would allow me to continue playing with phantoms running at really fast pace, the hard part was to be constant, but doable nevertheless

Bejeweled? (0)

Anonymous Coward | more than 2 years ago | (#38836163)

I would like an thorough analysis of how hard Bejeweled (PopCap Games) is.

(HTML5)
http://bejeweled.popcap.com/html5

The crowd at Slashdot has really changed... (0)

11011001 (710307) | more than 2 years ago | (#38836165)

since only a few years ago. The comments on this story are very disappointing.

Old games (1)

White Flame (1074973) | more than 2 years ago | (#38836237)

Doom is being lumped into the same game era as Pac-Man? Why am I suddenly getting a desire to have a lawn?

Re:Old games (0)

Anonymous Coward | more than 2 years ago | (#38836647)

Doom is being lumped into the same game era as Pac-Man? Why am I suddenly getting a desire to have a lawn?

You mean, to defend with a shotgun, and tell kids to get off of it, right?

Mommy? (-1)

Anonymous Coward | more than 2 years ago | (#38836605)

Susie: Mommy... Why do I have to die? Why is there no cure for cancer? (cough cough) Why is it that no one has figured out how to cure us?

Susie's Mommy: Because the people who could have figured it out were too busy playing Pac-Man, Susie. I'm sorry.

Ms. Pac Man (0)

Anonymous Coward | more than 2 years ago | (#38836689)

That should please Ms. Pac Man

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...