RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

2002, Volume 293

| General information | Contents |


Computational complexity theory. Part VII


Systems of pair of $q$-distant representatives and graph colorings
P. A. Golovach
5
Public-key cryptography and invariant theory
D. Yu. Grigor'ev
26
On non-abelian homomorphic public-key cryptosystems
D. Yu. Grigor'ev, I. N. Ponomarenko
39
Blocks in $k$-connected graphs
D. V. Karpov
59
Solution lifting method for handling Meta-variables in the TH$\exists$OREM$\forall$ system
B. Yu. Konev, T. Jebelean
94
An upper bound $O(2^{0.16254n})$ for Exact 3-Satisfiability: a simpler proof
A. S. Kulikov
118
A $2^{|E|/4}$-time Algorithm for MAX-CUT
A. S. Kulikov, S. S. Fedin
129
Hard satisfiable formulas for DPLL-type algorithms
S. I. Nikolenko
139
Intertible infinitary calculus without loop rules for a restricted FTL
R. Pliuškevičius
149


© Steklov Math. Inst. of RAS, 2024