68 research outputs found
Beyond NP: The work and legacy of Larry Stockmeyer
No full textShortly after Steven Cook and Richard Karp showed the existence of many natural NP-complete languages, researchers started to realize the great importance of the P versus NP problem and the difficulty of settling it. One graduate student at the Massachusetts Institute of Technology started to look beyond NP, asking what problems have a higher complexity and how do we classify them. Larry Stockmeyer discovered an amazing structure of complexity classes that continues to direct the research in complexity to this day. Stockmeyer passed away on July 31, 2004 at the age of 55 and in this paper we review some of his research and th
General Terms Theory
No full textThe complexity of algorithms tax even the resources of sixty billion gigabits--or of a universe full of bits; Meyer and Stockmeyer had proved, long ago, that, regardless of computer power, problems existed which could not be solved in the life of the universe
Local Computations on Static and Dynamic Graphs
No full textThe purpose of this paper is a study of computation that can be done locally in a distributed network. By locally we mean within time (or distance) independent of the size of the network. In particular we are interested in algorithms that are robust, i.e., perform well even if the underlying graph is not stable and links continuously fail and come-up. We introduce and study the happy coloring & orientation problem and show that it yields a robust local solution to the (d; m)-dining philosophers problem of Naor and Stockmeyer [20]. This problem is similar to the usual dining philosophers problem, except that each philosopher has access to d forks but needs only m of them to eat. We give a robust local solution if m dd=2e (necessity of this inequality for any local solution was known previously). Two other problems we investigate are: (1) the amount of initial symmetry-breaking needed to solve certain problems locally (for example, our algorithms need considerably less symmetry-breaking..
Optimal orientations of cells in slicing floorplan designs
No full textA methodology of VLSI layout described by several authors first determines the relative positions of indivisible pieces, called cells, on the chip. Various optimizations are then performed on this initial layout to minimize some cost measure such as chip area or perimeter. If each cell is a rectangle with given dimensions, one optimization problem is to choose orientations of all the cells to minimize the cost measure. A polynomial time algorithm is given for this optimization problem for layouts of a special type called slicings. However, orientation optimization for more general layouts is shown to be NP-complete (in the strong sense)
Logic and Formal Languages]: Mathematical Logic—mechanical theorem proving
No full textAbstract. An exponential lower bound on the circuit complexity of deciding the weak monadic second-order theory of one successor (WS1S) is proved. Circuits are built from binary operations, or 2-input gates, which compute arbitrary Boolean functions. In particular, to decide the truth of logical formulas of length at most 610 in this second-order language requires a circuit containing at least 10 125 gates. So even if each gate were the size of a proton, the circuit would not fit in the known universe. This result and its proof, due to both authors, originally appeared in 1974 in the Ph.D. thesis of the first author. In this article, the proof is given, the result is put in historical perspective, and the result is extended to probabilistic circuits.
An Age-Threshold Algorithm for Garbage Collection in Log-Structured Arrays and File Systems
No full text- …
