Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-025 | 11th March 2009 00:00

A New Look at Some Classical Results in Computational Complexity

RSS-Feed




TR09-025
Authors: Arnaldo Moura, Igor Carboni Oliveira
Publication: 21st March 2009 10:25
Downloads: 3970
Keywords: 


Abstract:

We propose a generalization of the traditional algorithmic space and
time complexities. Using the concept introduced, we derive an
unified proof for the deterministic time and space hierarchy
theorems, now stated in a much more general setting. This opens the
possibility for the unification and generalization of other results
that apply to both the time and space complexities. As an example,
we present a similar approach for the gap theorems.



ISSN 1433-8092 | Imprint