Link to Original Source
Slashdot videos: Now with more Slashdot!
We've improved Slashdot's video section; now you can view our video interviews, product close-ups and site visits with all the usual Slashdot options to comment, share, etc. No more walled garden! It's a work in progress -- we hope you'll check it out (Learn more about the recent updates).
Link to Original Source
So I didn't buy it. And I've never played 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)*
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.
Shouldn't it be "255" and not "265"?
Sorry, they had to ship the article before it passed QA. We have created a support ticket and are working on a patch to resolve the problem.