Timeline for Subexponentially solvable hard graph problems
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 19, 2010 at 21:37 | vote | accept | Mohammad Al-Turkistany | ||
| Dec 13, 2010 at 3:02 | comment | added | Boaz Barak | Indeed, for these kinds of reasons Impagliazzo, Paturi and Zane argued that when asking about $2^{\Omega(n)}$ vs $2^{o(n)}$ complexity you need to set $n$ to be the size of the witness (which you need to define as part of the problem). In the $k$-clique case the witness is of size $\log \binom{|V|}{k} \sim k\log |V|$ for small $k$, while, as you say, you can assume w.l.o.g there are at least $k|V|$ edges and the input size is much larger than the witness size. | |
| Dec 8, 2010 at 16:24 | history | answered | Luca Trevisan | CC BY-SA 2.5 |