|
| ▲ | caughtinthought 7 hours ago | parent | next [-] |
| Basically 3SAT algo isn't sub-exponential enough to absorb the arbitrary poly cost for the reduction So 3SAT+poly reduction ends up being exponential |
| |
|
| ▲ | Aunche 7 hours ago | parent | prev | next [-] |
| Suppose 3sat is solved in 2^sqrt(n). That's subexponential. An n^2 reduction from sat to 3sat is polynomial. However, an algorithm using this reduction with the discovered solution, would run in (2^sqrt(n))^2 which is just 2^n. |
| |
| ▲ | stbede 5 hours ago | parent | next [-] | | (2^sqrt(n))^2 = 2^sqrt(n) * 2^sqrt(n) = 2^(sqrt(n) + sqrt(n)) = 2^(2 sqrt(n)) but 2^(sqrt(n)^2) = 2^n | |
| ▲ | raegis 5 hours ago | parent | prev | next [-] | | That last statement is not correct. (2^sqrt(n))^2 equals 2^(2 * sqrt(n)). If you just take n=1 in your expression you can see the error, your (2^sqrt(n))^2 yields 4, while 2^n is just 2. | | | |
| ▲ | jballanc 6 hours ago | parent | prev [-] | | ...that's...not how exponents work | | |
| ▲ | Dylan16807 an hour ago | parent [-] | | The result is right, they wrote the parentheses in the wrong spot, don't be so shocked. |
|
|
|
| ▲ | nightshade1511 7 hours ago | parent | prev | next [-] |
| Suppose 3SAT can be solved in 2^(n^0.9) time (this is not the actual bound in paper). And another NP problem can be reduced to 3SAT in polynomial time, but the reduction increases the problem size from n to n^2. Then after the reduction the other NP problem can solved in 2^(n^1.8) time, so it does not mean all np problems are sub exponential. |
| |
|
| ▲ | csheehan10 4 hours ago | parent | prev | next [-] |
| To achieve this you would need to show that 3SAT is solvable in 2^{n^c} time for every c>0, not just a single c<1. In this case they have c = 1-0.5(\log \log n)/(\log n) which is approaching 1 for large n. |
|
| ▲ | imadr 7 hours ago | parent | prev [-] |
| Misunderstood your question sorry, I have no idea! |
