Speedup in Computational Complexity

by

Welcome to this new blog aimed at promoting discussion of speedup for natural computational problems, that is, the question in computational complexity of whether a problem has a best algorithm. The intention is to have a series of guest posts by researchers in the field and to provide a shared, user maintained bibliography of work on the topic.

I believe this blog is necessary because the topic is interesting and underappreciated. It is a fundamental property of a computational problem as to whether it does or does not have an optimal algorithm. While a few classic results on speedup versus optimality are widely known, such as Blum’s speedup for artificially constructed languages and Levin’s optimal NP search algorithm, other key results on speedup for natural problems are not familiar. For instance, there is no best Strassen-style bilinear identity for matrix multiplication. The existence of efficient algorithms for MM is linked to key problems in combinatorics such as the Erdos-Rado sunflower conjecture (see Alon et al) and efforts to lower the MM exponent have recently resumed. Curiously, four of the five problems with a gap between their monotone and nonmonotone circuit complexity rely upon integer or matrix multiplication, which are conjectured to have speedup. As another example, Stockmeyer’s PhD thesis presented a result on speedup for natural problems that had been virtually forgotten. It has also been established that if there is an infinitely often (i.o.) superpolynomial speedup for the time required to accept any (paddable) coNP-complete language, then all (paddable) coNP-complete languages have this speedup, which is equivalent to a superpolynomial speedup in proof length in propositional proof systems for tautologies.

I have argued that there is a correspondence between the properties “has no algorithm at all” and “has no best algorithm” by demonstrating that a 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 (paddable) coNP-complete language. A literature review on speedup can be found here.

Please feel free to contribute by commenting on blog posts or adding papers to the shared bibliography and also let me know if you would like to make a guest post on a topic of general interest or on your latest research.

Hunter Monroe

Advertisements

Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: