MIT/LCS/TM-131 TIME, SPACE AND RANDOMNESS

Space and time are the fundamental parameters of complexity theory. The thesis of this paper is that randomness is of equal importance. We intro-duce a notion of randomness (based on Kolmogorov-Chaitin-Randomness), which we suspect will contribute to the understanding of some of the cen-tral problems in complexity theory. The purpose of this paper is primarily conceptual, though several easy theorems are given which clarify the relation-ship of this notion of randomness to the NP = P question, the complexity of integer factoring, and the sets computable in random polynomial time. Finally, using factoring as an example, we raise the possibility of performing experiments on functions of unknown complexity to indicate the extent of their tractability. 3 I. Motivation- An analogy with chemistry At a philosophical level there is a similarity between chemistry and num