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
Fulltext:
PDF file (271 kB)
Bibliographic databases:
©
Steklov Math. Inst. of RAS
, 2024