Dimension, Halfspaces, and the Density of Hard Sets

作者：Harkins Ryan C; Hitchcock John M^*

来源：Theory of Computing Systems, 2011, 49(3): 601-614.

DOI：10.1007/s00224-010-9288-1

We use the connection between resource-bounded dimension and the online mistake-bound model of learning to show that the following classes have polynomial-time dimension zero.
1. The class of problems which reduce to nondense sets via a majority reduction.
2. The class of problems which reduce to nondense sets via an iterated reduction that composes a bounded-query truth-table reduction with a conjunctive reduction.
Intuitively, polynomial-time dimension is a means of quantifying the size and complexity of classes within the exponential time complexity class E. The class P has dimension 0, E itself has dimension 1, and any class with dimension less than 1 cannot contain E. As a corollary, it follows that all sets which are hard for E under these types of reductions are exponentially dense. The first item subsumes two previous results and the second item answers a question of Lutz and Mayordomo. Our proofs use Littlestone's Winnow2 algorithm for learning r-of-k threshold functions and Maass and Turan's algorithm for learning halfspaces.

• 出版日期2011-10