ECCC-Report TR02-057https://eccc.weizmann.ac.il/report/2002/057Comments and Revisions published for TR02-057en-usWed, 25 Sep 2002 22:05:46 +0300
Paper TR02-057
| Non-uniform Depth of Polynomial Time and Space Simulations |
Richard J. Lipton,
Anastasios Viglas
https://eccc.weizmann.ac.il/report/2002/057We 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.
Wed, 25 Sep 2002 22:05:46 +0300https://eccc.weizmann.ac.il/report/2002/057