Speedup for Natural Problems and NP=?coNP

Details Speedup for Natural Problems and NP=?coNP Speedup for Natural Problems and NP=?coNP

2009-06-20

arxiv.org/abs/0906.3765v1

Computer Science

Computational Complexity

7 pages

Scientific paper

Informally, 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 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.

Affiliated with

Also associated with

No associations

Rating

Speedup for Natural Problems and NP=?coNP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Speedup for Natural Problems and NP=?coNP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Speedup for Natural Problems and NP=?coNP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-13257