A Post's program for complexity theory
Harry Buhrman, Leen Torenvliet · UvA-DARE (University of Amsterdam) · 2005
In 1944, E. Post proposed a program that would lead to the identification of separate degrees of recursively enumerable sets. Post proposed to identify structural properties that sets of different degrees would not share. Thus proving such a property for sets in one degree would imply that these sets are not in the other. We propose a similar program for the separation of complexity classes and identify three properties that are potential separators: auto-reducibility, robustness, and mitoticity. Some partial results that do separate complexity classes have already been established. Also, answering the question whether complete sets in certain classes do or do not have these properties either way gives an answer to separation problems of central interest.