Hacker News Reader

A different but related point: NP-hard problems (and other kind of hard problems, like EXPSPACE-hard problems) are (in general) hard only _in the worst case_. This means that a problem might be NP-hard (or worse), but we may have algorithms which solve every instance of the problem which could possibly arise _in practice_ "fast". This is because for these problems, the really hard instances are so very rare and/or esoteric that they don't turn up in practice.

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

Yep, totally agree - it gets so much worse. I don't recall going much further than NP hard in my undergraduate courses but another guy I did my PhD with was a researcher into QSAT which is PSPACE-complete (fails the "verify a token in polynomial time" condition of NP-complete).

There are so many different complexity classes, P and NP are just the start.

> - Require additional space bounded above by an exponential function in the input.

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

>> NP-complete is essentially shorthand for belonging to a class of problems that are computationally very hard

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

I think "computationally very hard" means exactly what you say NP-complete problems are ("very hard to solve efficiently"). Typically when one talks about the computational difficulty of an algorithm, they are talking about the computational resources it takes, not the amount a human has to think to come up with the algorithm.