Geodesic

Computational complexity theory. Part VI

Sommaire

Combined hierarchies of finite random access machines
p. 5-13
Algorithms for SAT and upper bounds on their complexity
p. 14-46
Double-exponential growth of the number of vectors of solutions of polynomial systems
p. 47-52
Upper bounds on the height of terms in the solution of the semiunification problem
p. 53-79
Upper bound on the height of terms in proofs with bound-depth-restricted cuts
p. 80-103
A polynomial lower bound for the size of any $k$-min-wise independent set of permutations
p. 104-116