TR02-057 Authors: Richard J. Lipton, Anastasios Viglas

Publication: 25th September 2002 22:05

Downloads: 2009

Keywords:

We discuss some connections between polynomial time and non-uniform, small depth circuits. A connection is shown with simulating deterministic time in small space. The well known result of Hopcroft, Paul and Valiant showing that space is more powerful than time can be improved, by making an assumption about the connection of deterministic time computations and non-uniform, small depth circuits. To be more precise, we prove the following: If every linear time deterministic computation can be done by non-uniform circuits of polynomial size and sub-linear depth (for example, if P is in non-uniform NC), then DTIME(t) is in DSPACE(t^{1-e}) for some constant e>0.