ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: not given Adelson-Velsky, George M., Bar-Ilan University, Israel NP = P There exists the polynomial Algorithm solving the Problem of CNF executing. The next Reasons and Assertions are used:

1) The bipartitive graph of a given CNF consists of the vertices corresponding to the variables x_{1}, x_{2}, …, x_{n}, the vertices corresponding to the disjunctions y_{1}, y_{2}, …, y_{m}. If the disjunction y_{i} contains the variable x_{j}, it has the edge (y_{i}, x_{j}) with the sign +, if it contains their negation, this edge has got the sign −. There is a CNF equivalent to the given one in that each variable is included into 1 or 2 disjunctions and its negation is included into 1 negation. There are two cycles with the change of signs: each vertex x_{j} in such a cycle is incident with the edges (x_{j}, y_{i′}) and (x_{j}, y_{i′′}) with different signs. There is the evaluation that is smaller than m^{2} and is connected with these cycles. There is the consequence of Reductions CNF_{1} → CNF_{2} → … → CNF_{n} with decrease of the aforementioned evaluation.