Time-space lower bounds for SAT on uniform and non-uniform machines
- 7 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- On the complexity of SATPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Nondeterministic polynomial time versus nondeterministic logarithmic space: time-space tradeoffs for satisfiabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An O(T log T) reduction from RAM computations to satisfiabilityTheoretical Computer Science, 1991
- Short propositional formulas represent nondeterministic computationsInformation Processing Letters, 1988
- Towards separating nondeterminism from determinismTheory of Computing Systems, 1984
- Some connections between nonuniform and uniform complexity classesPublished by Association for Computing Machinery (ACM) ,1980
- Relations Among Complexity MeasuresJournal of the ACM, 1979
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Time- and tape-bounded turing acceptors and AFLsJournal of Computer and System Sciences, 1970
- Two-Tape Simulation of Multitape Turing MachinesJournal of the ACM, 1966