## "Zapiski Nauchnyh Seminarov POMI"

VOL. ** 277**
This issue is entitled **" Computational complexity theory. Part VI"**
editor ** M.A. Vsemirnov**

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

** Paging: 119 pp.
**-
** Language: Russian
**

Back to the Petersburg Department of
Steklov Institute of Mathematics