EN|RU Volume 18, No 3, 2011, P. 76-83 UDC 519.85 A. N. Maksimenko Sat polytopes are faces of polytopes of the traveling salesman problem Abstract: Let $U=\{u_1,u_2,\dots,u_d\}$ be a set of boolean variables and $C$ be a boolean formula over $U$ in conjunctive normal form. Denote by $Y$ the set of characteristic vectors of all satisfying truth assignments for $C$. The SAT polytope, denoted by $S(U,C)$, is the convex hull of $Y$. Denote by $T_n$ the asymmetric traveling salesman polytope. We show that $S(U,C)$ is a face of $T_n$, for $n=|U|+2\operatorname{len}(C)$, and $\operatorname{len}(C)$ is the size of the formula $C$. Ill. 1, Bibliogr. 9. Keywords: TSP polytope, SAT polytope, face. Maksimenko Aleksandr Nikolaevich 1 1. P. G. Demidov Yaroslavl State University, 144 Soyuznaia str., 150008 Yaroslavl, Russia e-mail: maksimenko_a_n@mail.ru © Sobolev Institute of Mathematics, 2015