Average dependence and random oracles
Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer · 2003
A reconstruction of the foundations of complexity theory relative to random oracles is begun. The goals are to identify the simple, core mathematical principles behind randomness; to use these principles to push hard on the current boundaries of randomness; and to eventually apply these principles in unrelativized complexity. The focus in this work is on quantifying the degree of separation between NP/sup R/ and coNP/sup R/ relative to a random oracle R. A technique called average dependence is introduced and used to investigate what is the best lower bound on the size of nondeterministic circuits that accept coNP/sup R/ sets and how close a coNP/sup R/ set can come to 'approximating' an arbitrary NP/sup R/ set. The results show that the average dependence technique is a powerful method for addressing certain random oracle questions but that there is still much room for improvement. Some open questions are briefly discussed.>