[nhaehnle]

On the question of whether it's intuitive or not: NP-complete problems tend to have fairly little structure. A problem like boolean satisfiability has basically no structure: all you have is a soup of clauses. The "tricky" problems that have solutions in P get their solutions from clever exploitation of structure.

At least, that's how it becomes more intuitive to me.

[dom0]

The structure of a problem specifies it; an unstructured problem is less well-specified, and that makes it intuitively more difficult to approach.

E.g. summation of a column of decimal numbers is a highly structured problem that's very easy to solve. Parsing the speech of yelling drunkards is not so structured, and much harder to solve.

[wybiral]

And now my new crypto startup will be the first to market this with YDAAS (Yelling Drunkards As A Service).