Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-057 | 19th September 2002 00:00

Non-uniform Depth of Polynomial Time and Space Simulations

RSS-Feed




TR02-057
Authors: Richard J. Lipton, Anastasios Viglas
Publication: 25th September 2002 22:05
Downloads: 1215
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint