Xiaoyang Gu

Title: Xiaoyang Gu

Main Research Question: How can resource-bounded dimension theory be used to investigate polynomial size circuits?

Methodology: The study uses resource-bounded measure and dimension, a powerful tool for examining the quantitative structure within complexity classes. It specifically focuses on the relationship between polynomial size circuits and uniform complexity classes.

Results: The research shows that for every i≥0, P/polyi.o. has ith order scaled p3-strong dimension 0. It also demonstrates that P /polyi.o.has p3-dimension 1 /2, p3-strong dimension 1. These results improve previous measure results of Lutz (1992) and dimension results of Hitchcock and Vinodchandran (2004).

Implications: The findings provide valuable insights into the structure of polynomial size circuits, contributing to a deeper understanding of computational complexity. The improved measurement of P /polyi.o. using scaled dimensions and strong dimensions could lead to new techniques for analyzing and designing efficient circuits.

Additional Information: The study uses the equivalence between time-bounded Kolmogorov complexity KT and circuit-size complexity of strings to measure the class of polynomial size circuits more precisely. It also improves a recent result by Hitchcock and Vinodchandran [8] from dimension to scaled strong dimension by showing that for all i∈N, dim(i)p3(P/poly) = Dim(i)p3(P/poly) = 0.

Link to Article: https://arxiv.org/abs/0404044v2 Authors: arXiv ID: 0404044v2