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

Zap. Nauchn. Sem. LOMI, 1974 Volume 40, Pages 10–13 (Mi znsl2676)

A reduction of proposittional tautologihood to graph-coloring in three colors

G. V. Davydov, P. Yu. Suvorov


Abstract: Given a disjunctive normal form $A$ of the length $l$ graph $\Gamma_A$ is constructed such that the number of $\Gamma_A$ is $c\cdot l$ and $\Gamma_A$ has a coloring of vert exes in three colors if and only if $A$ is not a tautology.

UDC: 51.01:164+519.1



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024