[bawolff]

> the extended thesis it depends on is "No physical procedure can decide an NP-complete problem in polynomially many steps."

I think part of the confusion here, is that usually the extended church turing thesis means that any physical computation can be efficiently (in polynomial time) simulated by a deterministic turing machine. (And thus if quantum computers exist and BQP is a superset of P, the proposition is false). I've never seen it defined before as above. But im definitely not a complexity theorists.

[steve_gh]

But remember that "efficient" in terms of P and NP is about scaling. P == NP doesn't necessarily mean that a practically efficient algorithm can be found. The polynomial exponents involved may be large: O(N^1000) does eventually scale better than O(e^N), but that doesn't mean it is practically useful!

[bawolff]

This is pretty unrelated to the topic at hand, but people say that as if its a cop out answer to the conundrum, however i think it would be both the most intersting and most unlikely outcome to the whole p vs np saga. Possibly even more crazy than the answer being uncomputable.

Think about what that would mean. It essentially amounts to a loop nested 1000 times would be enough. 1001 tumes is more than needed, 999 times is enough. Having high transition points like that in math is super rare and interesting. Things are usually either a small number or infinity; almost never a large number. Like i can't think of any non contrived polynomial time problems you would actually want to solve that are worse than n^20, let alone n^100 (excluding cheating by fixing one of the parameters as part of the problem). I don't know what such a result would mean but it would be fascinating.

[Timwi]

What non-contrived polynomial time problem can you think of that is n^20? I'm really curious.