Name
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 [HPV77] 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,then DTIME(t) subset of or equal to DSPACE(t(1-epsilon)) for some constant epsilon > 0. We can also apply the same techniques to prove an unconditional result, a trade-off type of theorem for the size and depth of a non-uniform circuit that simulates a uniform computation. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-45077-1_29 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
space simulations,non-uniform depth,block respecting computation | Alternating polynomial,Discrete mathematics,Combinatorics,Polynomial,Minimal polynomial (linear algebra),Homogeneous polynomial,Monic polynomial,Reciprocal polynomial,Wilkinson's polynomial,Matrix polynomial,Mathematics | Conference |
Volume | Issue | ISSN |
2751 | 057 | 0302-9743 |
Citations | PageRank | References |
3 | 0.38 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard J. Lipton | 1 | 6412 | 1796.57 |
| Anastasios Viglas | 2 | 197 | 15.97 |