Nondeterministic polynomial time versus nondeterministic logarithmic space: time-space tradeoffs for satisfiability

This publication has 26 references indexed in Scilit:

• Near-Optimal Time-Space Tradeoff for Element Distinctness
  SIAM Journal on Computing, 1994
• Relativized isomorphisms of NP-complete sets
  computational complexity, 1993
• PP is as Hard as the Polynomial-Time Hierarchy
  SIAM Journal on Computing, 1991
• Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
  Journal of the ACM, 1990
• Nearly linear time
  Published by Springer Nature ,1989
• The problem of space invariance for sequential machines
  Information and Computation, 1988
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
  IEEE Annals of the History of Computing, 1984
• Rudimentary Predicates and Relative Computation
  SIAM Journal on Computing, 1978
• Two-Tape Simulation of Multitape Turing Machines
  Journal of the ACM, 1966
• On the Computational Complexity of Algorithms
  Transactions of the American Mathematical Society, 1965