News for hackers. Stuff that matters.

A comment on The Financial Industry Is Having Its Napster Moment. Parent comment

Re:The Financial Industry Is Having Its Napster Moment by javajosh on Friday April 08, 2016 @03:31AM (#11453149)
>The problem of market pricing in the economy is NP-hard.

Is it? I mean, I see how it's reflexive (and so chaotic) but NP-hard is the halting problem: given a program and it's input, decide if it halts. E.g. what is the input to your market function? It's like asking if the world halts.

The thing about all complexity analysis is that it ignores input/output.

[ Parent | on HN ]
Re:The Financial Industry Is Having Its Napster Moment by Scarblac on Friday April 08, 2016 @03:45AM (#11453192)
NP-hard is the class of problems that are at least as hard as NP. The halting problem is in there, but it isn't decidable _at all_.

Just that its NP-hard doesn't mean it's as hard as the halting problem, it could be easily decidable in exponential time.

Complexity analysis is all about the size of the input, it doesn't ignore it.

[ Parent | on HN ]