Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-064 | 25th June 2004 00:00

Exponential time reductions and sparse languages in NEXP

RSS-Feed




TR04-064
Authors: Piotr Faliszewski
Publication: 9th August 2004 19:02
Downloads: 1194
Keywords: 


Abstract:

In this paper we define a many-one reduction which is allowed to work in exponential time but may only output polynomially many symbols. We show that there are no NEXP-hard sparse languages under our reduction unless EXP=UEXP.



ISSN 1433-8092 | Imprint