"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