A case in point is the granddaddy of them all, the Boolean Satisfiability Problem [1], or SAT for short, which was the first problem shown to be NP-hard. We now have algorithms which can solve, in reasonable amounts of time, SAT instances which contain up to millions of clauses [2]:
"... efficient and scalable algorithms for SAT were developed over the last decade and have contributed to dramatic advances in our ability to automatically solve problem instances involving tens of thousands of variables and millions of constraints"
Another way in which NP-and-other hardness does not necessarily spell doom in practice is illustrated by the problem of type-checking programs written in the functional language ML (or in another language which has a Hindley-Milner type system). This problem is hard (and complete) for the class EXPTIME [3] (which means: much worse than NP-hard), but this doesn't pose problems in practice: modern ML compilers can easily type-check large programs which are thrown at them. One "explanation" for this contrast is given by the existence of an algorithm for type-checking ML programs [4] which runs in time O(2^{k} n) where
a) n is the size of the program, and
b) k is the maximum _nesting depth_ of type declarations in the program
Since programs which are written by humans (or otherwise found in the wild) do not usually have type declarations more than about 10-deep or so, this algorithm solves the type-checking problem (which is extremely hard, in theory!) in essentially _linear_ time in the input size.So the bottom line is that a problem being NP-(or worse)-hard doesn't automatically mean that we can't actually solve it in practice.
[1] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem
[2] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#...
[3] http://www.seas.upenn.edu/~sweirich/types/archive/1989/msg00...
[4] Orna Lichtenstein and Amir Pnueli. 1985. Checking that finite state concurrent programs satisfy their linear specification. In Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '85).
There are so many different complexity classes, P and NP are just the start.
> - May require an unbounded (though obviously finite) amount of time.
How can an algorithm that uses bounded space take unbounded time? Since the computation cannot be in the same memory state twice (otherwise it would loop), if it uses s bits of space it must complete in time O(2^s).
In general, SPACE(f(n)) ⊆ DTIME(2^f(n)).
That is actually incorrect, and is a common and serious misunderstanding of beginners. NP-complete problems are not hard to solve (e.g. via brute force). They are however very hard to solve efficiently (i.e. in polynomial time).
It's totally correct, but it always bothers me a little to see people talk about NP in those terms; much, much more difficult problems are known. Recreational wikipedia reading taught me a while ago the the regexp equivalence problem ("do these two given regular expressions define the same language?") is EXPSPACE-complete, where EXPSPACE contains all the problems that:
- Require additional space bounded above by an exponential function in the input.
- May require an unbounded (though obviously finite) amount of time.
That second point is a doozy, and the problem so accessible that I'm fairly sure many people have independently come up with it and wished for a solution. That's not going to happen, though; a solution would be good for much more than just deciding whether two regexps are equivalent. Any NP-complete problem is utterly trivial by comparison.