Comment by cwillu
17 hours ago
How much effort has been expended on optimizing those reductions though? I have a harder time believing that one can hang one's belief in P!=NP on that particular hook.
17 hours ago
How much effort has been expended on optimizing those reductions though? I have a harder time believing that one can hang one's belief in P!=NP on that particular hook.
There are so many just barely sub-exponential function shapes between 2^(n / sqrt ln n) {this result} and 2^(log n) {polynomial time}!
The challenge is the initial reduction from an arbitrary problem in NP to the problem you want to prove NP-complete.
In the usual approach, you assume a nondeterministic Turing machine (or equivalent) that solves the problem and a time bound (which can be an arbitrarily large polynomial). You then create a boolean expression that can be satisfied if and only if the Turing machine accepts the original problem instance. Unfortunately all constructions so far have included the time bound as a factor of the size of the expression.