About a decade ago, Lutz presented resource-bounded measure as an analogue for classical Lebesgue measure in complexity theory. Resource-bounded measure has been commonly applied in complexity theory research in the following two forms.

1. Resource-bounded measure may be used to obtain quantitative characterization of the relative ``sizes'' of many complexity classes. Ideally this leads to separation results.
2. Hypotheses on the resource-bounded measure of complexity classes may be investigated. Some strong measure hypotheses are reasonable and seem to have more explanatory power than weaker, traditional complexity-theoretic hypotheses.

Resource-bounded dimension was recently introduced by Lutz as an effectivization of classical Hausdorff dimension for complexity theory. Resource-bounded measure is refined by resource-bounded dimension in the same way that Hausdorff dimension refines Lebesgue measure. The two application methods listed above for resource-bounded measure can also be used with resource-bounded dimension. Dimension provides a finer quantitative measure of complexity classes, and this provides a finer variety of strong hypotheses for investigation. We study both applications in this thesis.

In the first part of the thesis, a theory of scaled resource-bounded dimensions is developed. These scaled dimensions are then used to give dimension measures for many nonuniform complexity classes that are too fine to be analyzed by unscaled dimension. The latter portion of this thesis uses a hypothesis on the polynomial-time dimension of NP to investigate the approximability of the MAX3SAT optimization problem.

• M.S. Thesis, Iowa State University, 2001.
  [PostScript | PDF]

• Single-spaced version:
  [PostScript | PDF]