The Nature of the Problem: Computational Complexity from Factories to Theoretical Computer Science 1954-1976

• In Event: Knowledge Economies

English Abstract

Theoretical computer science is concerned with the analysis of abstract computational “problems” in terms of their characteristic difficulty. While the work of Alonzo Church and Alan Turing (1936) on the limits of computation is well known, the continued study of the difficulty of computational problems after the invention of the electronic computer, is less well known, including during the early era of early work between the 1950s and 1970s which culminated in the conceptualization of the famous ‘P versus NP’ problem. This paper introduces a new project on this history, focusing on the early, practical context of research in the 1950s and the ties between computational complexity theory and operations research. It focuses on one particular problem, the job-shop scheduling problem (JSP), which asks to determine in advance the best schedule for a set of workers and machines in a custom parts factory. This was an eminently practical problem for computer researchers looking to develop industrially useful algorithms for the manufacturers investing in computing machines. It also turned out to be an incredibly challenging problem that forced new thinking about the study of algorithms and the nature of computational difficulty. This paper follows JSP from the 1950s until 1976 (when it was shown to be NP-Complete) to understand the broader context, concepts, and practices of theoretical computer science during an important, early period. It also sheds light on the disciplines and people involved in early computer science.

Author

• Devin Kennedy, University of Wisconsin-Madison