Pac-Man Is NP-Hard

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

Source: http://rss.slashdot.org/~r/Slashdot/slashdotScience/~3/3nfltwimYbE/pac-man-is-np-hard

zack greinke zack greinke siri san diego news ford evos ford evos the skin i live in