3 ms·
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
by nhaehnle 9y ago
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 9y agoThe 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 9y agoAnd now my new crypto startup will be the first to market this with YDAAS (Yelling Drunkards As A Service).