The Structure of Feasible Computation

该奖项资助了两个相关的项目：探索多项式时间可计算集的类P的结构，以及探索P中的尖锐有界层次结构的结构和应用。 早期的工作（与史蒂夫·霍默）探讨了可伸缩性，P中集合的排序属性，作为确定类P的P-同构度结构的工具。 这些问题的强度的各种排序性质的集合在P进行了探讨。 可伸缩性，即P-可排序性的P-同构闭包，实际上比P-可排序性更强吗？ 什么时候订购一个集合比赋予它的普查功能更难？ 此外，当两个集合在P中具有相似的密度P-同构？ 我们也可以通过考虑自约化性质来考虑类内集合的结构。 先前的工作表明了一系列的结果的形式，'一个集是在P，如果它有以下两个自约属性，'这是继续，在最近的工作自约集。 P是一个大类，包括在多项式时间内可识别的集合，其中多项式具有大的次数。这似乎是一个太大的类被认为是可行的，所以本研究研究的类在有限的多项式时间和O（log n）位的非确定性定义的P。

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.