Time-space tradeoffs in the counting hierarchy, Proceedings 16th Annual IEEE Conference on Computational Complexity, pp.295-302, 2001. ,
DOI : 10.1109/CCC.2001.933896
Alternation, Coo88] S. A. Cook. Short propositional formulas represent nondeterministic computations, pp.114-133, 1981. ,
DOI : 10.1145/322234.322243
Finite state Markov decision processes, 1972. ,
Time???Space Lower Bounds for the Polynomial???Time Hierarchy on Randomized Machines, SIAM Journal on Computing, vol.36, issue.3, pp.563-594, 2006. ,
DOI : 10.1137/050642228
An improved time-space lower bound for tautologies, Proc. of Computing and Combinatorics (COCOON), Springer LNCS 5609, pp.429-438, 2009. ,
Nondeterministic polynomial time versus nondeterministic logarithmic space, Proc. IEEE Conference on Computational Complexity (CCC), pp.52-60, 1997. ,
DOI : 10.1109/ccc.1997.612300
Time-space tradeoffs for nondeterministic computation, Proceedings 15th Annual IEEE Conference on Computational Complexity, pp.2-13, 2000. ,
DOI : 10.1109/CCC.2000.856730
Time-space lower bounds for satisfiability, Journal of the ACM, vol.52, issue.6, pp.835-865, 2005. ,
DOI : 10.1145/1101821.1101822
On time versus space III, Mathematical Systems Theory, vol.20, issue.1, pp.13-28, 1986. ,
DOI : 10.1007/BF01704903
On Time Versus Space, Journal of the ACM, vol.24, issue.2, pp.332-337, 1977. ,
DOI : 10.1145/322003.322015
Alternation and the power of nondeterminism Towards separating nondeterminism from determinism, Proc. ACM STOC, pp.344-34629, 1983. ,
On the complexity of SAT, 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), pp.459-464, 1999. ,
DOI : 10.1109/SFFCS.1999.814618
Simulations among multidimensional Turing machines, 1980. ,
Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape, SIAM Journal on Computing, vol.16, issue.1, pp.195-202, 1987. ,
DOI : 10.1137/0216016
TIME-SPACE LOWER BOUNDS FOR NP-COMPLETE PROBLEMS, Current Trends in Theoretical Computer Science, pp.265-291, 2004. ,
DOI : 10.1142/9789812562494_0015
A Survey of Lower Bounds for Satisfiability and Related Problems, Foundations and Trends?? in Theoretical Computer Science, vol.2, issue.3, pp.197-303, 2007. ,
DOI : 10.1561/0400000012
A time lower bound for satisfiability, Theoretical Computer Science, vol.348, issue.2-3, pp.311-320, 2005. ,
DOI : 10.1016/j.tcs.2005.09.020
Rudimentary predicates and Turing calculations, Soviet Math. Doklady, vol.11, pp.1462-1465, 1970. ,
On time versus space II, JCSS, vol.22, pp.312-327, 1981. ,
On determinism versus nondeterminism and related problems, Proc. IEEE FOCS, pp.429-438, 1983. ,
Satisfiability Is Quasilinear Complete in NQL, Journal of the ACM, vol.25, issue.1, pp.136-145, 1978. ,
DOI : 10.1145/322047.322060
Time-space tradeoffs for SAT on nonuniform machines [Vio09] E. Viola. On approximate majority and probabilistic time, JCSS Computational Complexity, vol.63, issue.183, pp.268-287337, 2001. ,
Inductive Time-Space Lower Bounds for Sat and Related Problems, computational complexity, vol.15, issue.4, pp.433-470, 2006. ,
DOI : 10.1007/s00037-007-0221-1
Algorithms and resource requirements for fundamental problems, 2007. ,
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pp.179-219, 2008. ,
DOI : 10.1109/CCC.2007.34