Zap. Nauchn. Sem. POMI, 2001, Volume 277

Zapiski Nauchnykh Seminarov POMI

RUS ENG

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

2001, Volume 277

Contents

Computational complexity theory. Part VI

	Combined hierarchies of finite random access machines A. P. Beltiukov		5–13
	Algorithms for SAT and upper bounds on their complexity M. A. Vsemirnov, E. A. Hirsch, E. Ya. Dantsin, S. V. Ivanov		14–46
	Double-exponential growth of the number of vectors of solutions of polynomial systems D. Yu. Grigor'ev		47–52
	Upper bounds on the height of terms in the solution of the semiunification problem V. B. Zhizhkun		53–79
	Upper bound on the height of terms in proofs with bound-depth-restricted cuts B. Yu. Konev		80–103
	A polynomial lower bound for the size of any $k$-min-wise independent set of permutations S. A. Norin		104–116