John M. Hitchcock
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
John M. Hitchcock has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Elvira Mayordomo
Departamento de Informática e Ingeniería de Sistemas, Instituto de Investigación en Ingeniería de Aragón, Universidad de Zaragoza, Zaragoza, Spain
1 shared publication - Jack H. Lutz
Department of Computer Science Iowa State University 50011 Ames IA USA
1 shared publication - Krishna B. Athreya
Iowa State University
1 shared publication
Latest Publications
- 19 July 2004
- Published by Springer Nature in Theory of Computing Systems
- Vol. 38 (5) , 559-571
Correspondence Principles for Effective Dimensions
- 19 July 2004
- Published by Springer Nature in Theory of Computing Systems
- Vol. 38 (5) , 559-571
Correspondence Principles for Effective Dimensions
- Open Access
Small Spans in Scaled Dimension
Juedes and Lutz (1995) proved a small span theorem for polynomial-time many-one reductions in exponential time. This result says that for language A decidable in exponential time, either the class of languages reducible to A (the lower span) or the class of problems to which A can be reduced (the upper span) is small in the sense of resource-bounded measure and, in particular, that the degree of A is small. Small span theorems have been proven for increasingly stronger polynomial-time reductions, and a small span theorem for polynomial-time Turing reductions would imply BPP != EXP. In contrast to the progress in resource-bounded measure, Ambos-Spies, Merkle, Reimann, and Stephan (2001) showed that there is no small span theorem for the resource-bounded dimension of Lutz (2000), even for polynomial-time many-one reductions. Resource-bounded scaled dimension, recently introduced by Hitchcock, Lutz, and Mayordomo (2003), provides rescalings of resource-bounded dimension. We use scaled dimension to further understand the contrast between measure and dimension regarding polynomial-time spans and degrees. We strengthen prior results by showing that the small span theorem holds for polynomial-time many-one reductions in the -3rd-order scaled dimension, but fails to hold in the -2nd-order scaled dimension. Our results also hold in exponential space. As an application, we show that determining the -2nd- or -1st-order scaled dimension in ESPACE of the many-one complete languages for E would yield a proof of P = BPP or P != PSPACE. On the other hand, it is shown unconditionally that the complete languages for E have -3rd-order scaled dimension 0 in ESPACE and -2nd- and -1st-order scaled dimension 1 in E.
Open AccessSmall Spans in Scaled Dimension
Juedes and Lutz (1995) proved a small span theorem for polynomial-time many-one reductions in exponential time. This result says that for language A decidable in exponential time, either the class of languages reducible to A (the lower span) or the class of problems to which A can be reduced (the upper span) is small in the sense of resource-bounded measure and, in particular, that the degree of A is small. Small span theorems have been proven for increasingly stronger polynomial-time reductions, and a small span theorem for polynomial-time Turing reductions would imply BPP != EXP. In contrast to the progress in resource-bounded measure, Ambos-Spies, Merkle, Reimann, and Stephan (2001) showed that there is no small span theorem for the resource-bounded dimension of Lutz (2000), even for polynomial-time many-one reductions. Resource-bounded scaled dimension, recently introduced by Hitchcock, Lutz, and Mayordomo (2003), provides rescalings of resource-bounded dimension. We use scaled dimension to further understand the contrast between measure and dimension regarding polynomial-time spans and degrees. We strengthen prior results by showing that the small span theorem holds for polynomial-time many-one reductions in the -3rd-order scaled dimension, but fails to hold in the -2nd-order scaled dimension. Our results also hold in exponential space. As an application, we show that determining the -2nd- or -1st-order scaled dimension in ESPACE of the many-one complete languages for E would yield a proof of P = BPP or P != PSPACE. On the other hand, it is shown unconditionally that the complete languages for E have -3rd-order scaled dimension 0 in ESPACE and -2nd- and -1st-order scaled dimension 1 in E.
- 15 April 2003
- Published by Elsevier in Information Processing Letters
- Vol. 86 (1) , 9-12
Gales suffice for constructive dimension
- 15 April 2003
- Published by Elsevier in Information Processing Letters
- Vol. 86 (1) , 9-12
Gales suffice for constructive dimension
- Open Access
Effective Strong Dimension, Algorithmic Information, and Computational Complexity
The two most important notions of fractal dimension are {\it Hausdorff dimension}, developed by Hausdorff (1919), and {\it packing dimension}, developed by Tricot (1982). Lutz (2000) has recently proven a simple characterization of Hausdorff dimension in terms of {\it gales}, which are betting strategies that generalize martingales. Imposing various computability and complexity constraints on these gales produces a spectrum of effective versions of Hausdorff dimension. In this paper we show that packing dimension can also be characterized in terms of gales. Moreover, even though the usual definition of packing dimension is considerably more complex than that of Hausdorff dimension, our gale characterization of packing dimension is an exact dual of -- and every bit as simple as -- the gale characterization of Hausdorff dimension. Effectivizing our gale characterization of packing dimension produces a variety of {\it effective strong dimensions}, which are exact duals of the effective dimensions mentioned above. We develop the basic properties of effective strong dimensions and prove a number of results relating them to fundamental aspects of randomness, Kolmogorov complexity, prediction, Boolean circuit-size complexity, polynomial-time degrees, and data compression.
Open AccessEffective Strong Dimension, Algorithmic Information, and Computational Complexity
The two most important notions of fractal dimension are {\it Hausdorff dimension}, developed by Hausdorff (1919), and {\it packing dimension}, developed by Tricot (1982). Lutz (2000) has recently proven a simple characterization of Hausdorff dimension in terms of {\it gales}, which are betting strategies that generalize martingales. Imposing various computability and complexity constraints on these gales produces a spectrum of effective versions of Hausdorff dimension. In this paper we show that packing dimension can also be characterized in terms of gales. Moreover, even though the usual definition of packing dimension is considerably more complex than that of Hausdorff dimension, our gale characterization of packing dimension is an exact dual of -- and every bit as simple as -- the gale characterization of Hausdorff dimension. Effectivizing our gale characterization of packing dimension produces a variety of {\it effective strong dimensions}, which are exact duals of the effective dimensions mentioned above. We develop the basic properties of effective strong dimensions and prove a number of results relating them to fundamental aspects of randomness, Kolmogorov complexity, prediction, Boolean circuit-size complexity, polynomial-time degrees, and data compression.
- 23 October 2002
- Published by Elsevier in Theoretical Computer Science
- Vol. 289 (1) , 861-869
MAX3SAT is exponentially hard to approximate if NP has positive dimension
- 23 October 2002
- Published by Elsevier in Theoretical Computer Science
- Vol. 289 (1) , 861-869
MAX3SAT is exponentially hard to approximate if NP has positive dimension
- Open Access
Gales Suffice for Constructive Dimension
Supergales, generalizations of supermartingales, have been used by Lutz (2002) to define the constructive dimensions of individual binary sequences. Here it is shown that gales, the corresponding generalizations of martingales, can be equivalently used to define constructive dimension.
Open AccessGales Suffice for Constructive Dimension
Supergales, generalizations of supermartingales, have been used by Lutz (2002) to define the constructive dimensions of individual binary sequences. Here it is shown that gales, the corresponding generalizations of martingales, can be equivalently used to define constructive dimension.