Timeline for Is SAT in P if there are exponentially many clauses in the number of variables?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2012 at 9:15 | vote | accept | Numerator | ||
| Jul 21, 2012 at 19:05 | comment | added | Xodarap | @Numerator: you are doing $2^{\log n}=n$ checks, where $n$ is the length of the input. | |
| Jul 12, 2012 at 11:37 | comment | added | Luke Mathieson | Remember that to be in P you want an algorithm that runs in polynomial time in the size of the input. In this case, if we denote the size of the input as N we know that $\text{#clauses } \leq N$. Hence we also have $n=O(log N)$ so the $2^n$ assignments only amount to a polynomial in the overall input size $N$. Don't let texts trick you when they use the variable $n$, it's just a variable, not a special magic number that is always the best measure for the size of the input. Sorry about the formatting, I'm typing this on my phone. | |
| Jul 12, 2012 at 10:09 | comment | added | Numerator | But a $2^n$ checks is still defined as plynoimal time? | |
| Jul 12, 2012 at 9:04 | history | answered | Luke Mathieson | CC BY-SA 3.0 |