The Structure of Feasible Computation

该奖项资助了两个相关的项目：探索多项式时间可计算集P类的结构，以及探索P中尖锐有界层次的结构和应用。早期的工作（与Steve Homer一起）探索了可伸缩性，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.