ECCC-Report TR09-056https://eccc.weizmann.ac.il/report/2009/056Comments and Revisions published for TR09-056en-usThu, 20 Sep 2012 20:53:07 +0300
Revision 2
| Speedup for Natural Problems and Noncomputability |
Hunter Monroe
https://eccc.weizmann.ac.il/report/2009/056#revision2A resource-bounded version of the statement "no algorithm recognizes all non-halting Turing machines" is equivalent to an infinitely-often (i.o.) superpolynomial speedup for the time required to accept any coNP-complete language and also equivalent to a superpolynomial speedup in proof length in propositional proof systems for tautologies, each of which implies P!=NP. This suggests a correspondence between the properties 'has no algorithm at all' and 'has no best algorithm' which seems relevant to open problems in computational and proof complexity.Thu, 20 Sep 2012 20:53:07 +0300https://eccc.weizmann.ac.il/report/2009/056#revision2
Revision 1
| Speedup for Natural Problems |
Hunter Monroe
https://eccc.weizmann.ac.il/report/2009/056#revision1Informally, a language L has speedup if, for any Turing machine (TM) for L, there exists one that is better. Blum showed that there are computable languages that have almost-everywhere speedup. These languages were unnatural in that they were constructed for the sole purpose of having such speedup. We identify an intuitive condition which, like several others in the literature, implies that accepting any coNP-complete language has an infinitely-often (i.o.) superpolynomial speedup. We also exhibit a natural problem which unconditionally has a weaker type of i.o. speedup based upon whether the full input is read. Neither speedup pertains to the worst case.
Sun, 27 Sep 2009 06:28:41 +0200https://eccc.weizmann.ac.il/report/2009/056#revision1
Paper TR09-056
| Speedup for Natural Problems and coNP?=NP |
Hunter Monroe
https://eccc.weizmann.ac.il/report/2009/056Informally, a language L has speedup if, for any Turing machine for L, there exists one that is better. Blum showed that there are computable languages that have almost-everywhere speedup. These languages were unnatural in that they were constructed for the sole purpose of having such speedup. We identify a condition apparently only slightly stronger than P!=NP which implies that accepting any coNP-complete language has an infinitely-often (i.o.) superpolynomial speedup and NP!=coNP. We also exhibit a natural problem which unconditionally has a weaker type of i.o. speedup based upon whether the full input is read. Neither speedup pertains to the worst case.
Thu, 02 Jul 2009 11:27:03 +0300https://eccc.weizmann.ac.il/report/2009/056