It Will Never Work in Theory

Tiny Transactions on Computer Science

Posted Jun 15, 2012 by Greg Wilson

| Announcements |

TinyToCS seeks papers describing significant research contributions to the field of computer science. Submissions can be up to 140 characters in length, with an abstract of no more than 250 words and a title of no more than 118 characters. Their sample is:

Reducibility Among Combinatorial Problems

Kichard Rarp

University of Balifornia, Cerkeley


A large class of computational problems involve the determination of properties of graphs, digraphs, integers, arrays of integers, finite families of finite sets, boolean formulas and elements of other countable domains. Through simple encodings from such domains into the set of words over a finite alphabet these problems can be converted into language recognition problems, and we can inquire into their computational complexity. It is reasonable to consider such a problem satisfactorily solved when an algorithm for its solution is found which terminates within a number of steps bounded by a polynomial in the length of the input.
Many problems with wide applicability—e.g., set cover, knapsack, hitting set, max cut, and satisfiability—lack a polynomial algorithm for solving them, but also lack a proof that no such polynomial algorithm exists. Hence, they remain "open problems."
This paper references the recent work, "On the Reducibility of Combinatorial Problems" [1].
A large class of open problems are mutually convertible via poly-time reductions. Hence, either all can be solved in poly-time, or none can.
[1] R. Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, 1972.

So, what results from empirical software engineering can you summarize in a tweet? Answers in comments, please, and we'll award a copy of either Making Software or The Architecture of Open Source Applications (Vol 2) to the best answer.

Comments powered by Disqus