Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Anastasios Viglas:

TR02-057 | 19th September 2002
Richard J. Lipton, Anastasios Viglas

Non-uniform Depth of Polynomial Time and Space Simulations

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 ... more >>>

ISSN 1433-8092 | Imprint