Paper Info

Title | ||
---|---|---|

Time—space tradeoffs for satisfiability |

Abstract | ||
---|---|---|

We give the first nontrivial model-independent time–space tradeoffs for satisfiability. Namely, we show that SAT cannot be solved in n 1+ o (1) time and n 1− ε space for any ε >0 general random-access nondeterministic Turing machines. In particular, SAT cannot be solved deterministically by a Turing machine using quasilinear time and n space. We also give lower bounds for log-space uniform NC 1 circuits and branching programs. Our proof uses two basic ideas. First we show that if SAT can be solved nondeterministically with a small amount of time then we can collapse a nonconstant number of levels of the polynomial-time hierarchy. We combine this work with a result of Nepomnjaščiı that shows that a nondeterministic computation of superlinear time and sublinear space can be simulated in alternating linear time. A simple diagonalization yields our main result. We discuss how these bounds lead to a new approach to separating the complexity classes NL and NP . We give some possibilities and limitations of this approach. |

Year | DOI | Venue |
---|---|---|

2000 | 10.1006/jcss.1999.1671 | Journal of Computer and System Sciences - Eleventh annual conference on computational learning theory&slash;Twelfth Annual IEEE conference on computational complexity |

Keywords | Field | DocType |

space tradeoffs,random access,branching program,lower bound,turing machine,satisfiability | Complexity class,Discrete mathematics,Combinatorics,Nondeterministic algorithm,Computer science,DSPACE,Turing machine,PSPACE,Time complexity,Time hierarchy theorem,NP | Journal |

Volume | Issue | ISSN |

60 | 2 | 0022-0000 |

Citations | PageRank | References |

29 | 1.12 | 26 |

Authors | ||

1 |

Authors (1 rows)

Cited by (29 rows)

References (26 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Lance Fortnow | 1 | 2788 | 352.32 |