Time-space lower bounds for SAT on uniform and non-uniform machines

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 07 Nov 2002Publisher:IEEE Comput. SocJournal:Proceedings 15th Annual IEEE Conference on Computational Complexity

Authors: Iannis Tourlakis;

doi: 10.1109/ccc.2000.856732

Time-space lower bounds for SAT on uniform and non-uniform machines

- Summary
- Metrics

Abstract

The arguments used by R. Kannan (1984), L. Fortnow (1997), and Lipton-Viglas (1999) are generalized and combined with a new argument for diagonalizing over machines taking n bits of advice on inputs of length n to obtain the first nontrivial time-space lower bounds for SAT on non-uniform machines. In particular we show that for any a 0 and any /spl epsiv/ 0 and all rationals r/spl ges/1, DTISP(n/sup r/, n/sup l-/spl epsiv//)/spl sub//spl ne/NTIM E(n/sup r/). We show how extending our uniform separations can lead to a separation of SC and NP.

Related Organizations

University of Toronto
Canada

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average