Geodesic
About Tseitin transformation in logical equations
Prikladnaâ diskretnaâ matematika, no. 4 (2009), pp. 28-50

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is devoted to the applications of Tseitin transformations in some propositional logics areas connected with the systems of logical equations. It is shown that Tseitin transformations of the system of logical equations do not change the number of its solutions and a bijection is pointed between the solutions of the system and its transformation result. Some results related to the usage of Tseitin transformations in obtaining bounds for the complexity of the propositional proof systems are given. By using Tseitin transformations, the simplest proofs of the NP-completeness problem for the solvability of a 2-degree logical equations system and of the $\#P$-completeness problem for counting the number of satisfying assignments for any Horne CNF are constructed too. By using Tseitin transformations, it is also shown that the ROBDD for any Boolean function given in a Horne CNF or in a CNF with 2-literal disjuncts may not be build for a polynomial time if $P\neq NP$.
Keywords: logical equations, Tseitin transformations, propositional proof systems, NP-completeness. 
@article{PDM_2009_4_a2,
     author = {A. A. Semenov},
     title = {About {Tseitin} transformation in logical equations},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {28--50},
     publisher = {mathdoc},
     number = {4},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2009_4_a2/}
}
TY  - JOUR
AU  - A. A. Semenov
TI  - About Tseitin transformation in logical equations
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2009
SP  - 28
EP  - 50
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2009_4_a2/
LA  - ru
ID  - PDM_2009_4_a2
ER  - 
%0 Journal Article
%A A. A. Semenov
%T About Tseitin transformation in logical equations
%J Prikladnaâ diskretnaâ matematika
%D 2009
%P 28-50
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2009_4_a2/
%G ru
%F PDM_2009_4_a2
A. A. Semenov. About Tseitin transformation in logical equations. Prikladnaâ diskretnaâ matematika, no. 4 (2009), pp. 28-50. http://geodesic.mathdoc.fr/item/PDM_2009_4_a2/