Publication:5628106
From MaRDI portal
zbMath0223.02031MaRDI QIDQ5628106
Publication date: 1970
03D20: Recursive functions and relations, subrecursive hierarchies
03D10: Turing machines and related notions
Related Items
Time-space tradeoffs for SAT on nonuniform machines, Arithmetic circuits: the chasm at depth four gets wider, Limits on alternation trading proofs for time-space lower bounds, The communication complexity of addition, Super-exponentials nonprimitive recursive, but rudimentary, Rudimentary reductions revisited, Bounded arithmetic, proof complexity and two papers of Parikh, Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms, Nonerasing, counting, and majority over the linear time hierarchy, Uniform constant-depth threshold circuits for division and iterated multiplication., A time lower bound for satisfiability, The role of rudimentary relations in complexity theory