Timeline for Super-linear time complexity lower bounds for any natural problem in NP?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2019 at 12:07 | comment | added | Hermann Gruber | +1: I changed my mind after considering Gil Kalai's comments and re-reading the accepted answer. Those nonlinear lower bounds are only known if the tapes are conceptually infinite only to the right (akin to the set $\mathbb N$) and not bi-infinite (like the set $\mathbb Z$). Somehow this provably causes overhead for moving the read/write head. For random access machines, moving the read/write head comes "for free" by definition. | |
| Dec 24, 2019 at 21:37 | comment | added | Gil Kalai | @HermannGruber, I suppose that for random access Turing machines the best known lower bounds are linear, right? | |
| Dec 24, 2019 at 21:36 | history | edited | Gil Kalai | CC BY-SA 4.0 |
added 259 characters in body
|
| Dec 24, 2019 at 11:49 | comment | added | Hermann Gruber | Thanks for commenting years after your answer! The accepted answer cites a superlinear lower bound for multitape Turing machines. I agree that circuit lower bounds are important, but it is a different model than what was asked for. | |
| Dec 24, 2019 at 10:58 | comment | added | Gil Kalai | @HermannGruber yes indeed my answer was based on what I know for circuits (as elaborated in my comment). But I believe nothing better is known for the (general) Turing machine model. If you know otherwise please let us know. In any case the circuit model is important so the answer is very relevant to the question. | |
| Dec 24, 2019 at 8:59 | comment | added | Hermann Gruber | -1: Your answer concerns nonuniform circuit families, not Turing machines or RAMs. | |
| Nov 29, 2009 at 21:22 | vote | accept | Rune | ||
| Dec 18, 2009 at 20:21 | |||||
| Nov 21, 2009 at 14:20 | comment | added | Gil Kalai | Here is a citation and a link : Uri Zwick, A 4n lower bound on the combinatorial complexity of certain symmetric Boolean functions over the basis of unate dyadic Boolean functions SIAM Journal on Computing 20, 499-505 (1991) An explicit lower bound of 5n-o (n) for boolean circuits, K Iwama, O. Lachish, H Morizumi, and R. Raz springerlink.com/index/XCP1TCRY1C236RDT.pdf The introduction of the second paper and the slow incremental improvements may give some idea on the difficulty of the problem. | |
| Nov 14, 2009 at 22:23 | comment | added | Sam Nead | Could you flesh this out? Or give a link to a reference? Why is finding super-linear lower bounds hard? If it is obvious, I apologize in advance. | |
| Nov 11, 2009 at 6:10 | history | answered | Gil Kalai | CC BY-SA 2.5 |