RUS  ENG
Full version
JOURNALS // Modelirovanie i Analiz Informatsionnykh Sistem // Archive

Model. Anal. Inform. Sist., 2007 Volume 14, Number 2, Pages 7–11 (Mi mais127)

On relaxation polytope of 3-satisfiability problem

B. V. Uryvaev

Yaroslavl State University

Abstract: The properties of a polytope associated with the 3-satisfiability problem are investigated. Particularly, we prove that values of its vertice coordinates can be represented by fractions with arbitrarily large denominators.

UDC: 519.6

Received: 18.05.2007



© Steklov Math. Inst. of RAS, 2024