3 ms·
Oops, this is what I get for not reading carefully :) But this is interesting: it implies, if I'm not mistaken, it implies that we haven't ever proven that a f
by fiddlerwoaroof 7y ago
Oops, this is what I get for not reading carefully :) But this is interesting: it implies, if I'm not mistaken, it implies that we haven't ever proven that a function takes exponential time, just that we haven't found any algorithms for certain problems faster than exponential time. I hadn't considered P != NP this way before...
- gpm 7y agoNo, we know that P != EXP_TIME, by the time hierarchy theorem - i.e. we know some problems (and we do have concrete examples) take exponential time. What we don't know is that there exists a problem that requires exponential time (or otherwise greater than polynomial) where we can create a proof that a answer is correct which is checkable in polynomial time. https://en.wikipedia.org/wiki/Time_hierarchy_theorem https://en.wikipedia.org/wiki/Time_hierarchy_theorem