The Structure of Feasible Computation

点击翻译按钮获取中文摘要

This award funds two related projects: an exploration of the structure of the class, P, of polynomial time computable sets, and an exploration of the structure and applications of the Sharply Bounded Hierarchy within P. Earlier work (with Steve Homer) explored scalability, an ordering property of sets in P, as a tool for determining the P-isomorphism degree structure of the class P. This work raised more questions than it answered. These questions about the strength of various ordering properties on sets in P are explored. Is scalability, the P-isomorphism closure of P-rankability, actually stronger than P-rankability? When is it harder to order a set than to give its census function? In addition, when are two sets in P with similar densities P-isomorphic? One can also consider the structure of the sets within the class by considering self-reducibility properties. Prior work showed a series of results of the form, `a set is in P if it has the following two self-reducibility properties,` which is continued, in light of recent work on self-reducible sets. P is a large class, including sets recognizable in polynomial time, where the polynomial has a large degree. This seems to be too large a class to be considered feasible, so this research studies classes within P defined by limited polynomial time and O(log n) bits of nondeterminism.