On Relaxation Polytope of 3-satisfiability Problem
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.
References
1. Бондаренко, В.А. Полиэдральные графы и сложность в комбинаторной оптимизации / В. А. Бонда-ренко. - Яросл. гос. ун-т. - Ярославль, 1995. - 126 с.
2. Деза, М. М. Геометрия разрезов и метрик / М.М. Деза, М. Лоран; пер. Е. Пантелеевой и П. Сергеева / под ред. В. Гришухина. - М.: МЦНМО, 2001. - 736 с.
3. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. - М.: Мир, 1982. - 416 с.
4. Емеличев, В.А. Многогранники, графы, оптимизация / В.А. Емеличев, М.М. Ковалев, М. К. Кравцов. - М.: Наука, 1981. - 344 с.
5. Ильичев, А.П. О крайних точках многогранников многоиндексных транспортных задач / А.П. Ильичев, В.Н. Шевченко // Комбинаторно-алгебраические методы в прикладной математике. - Горький: Изд-во ГГУ, 1981. - С. 66 - 72.
6. Борисов, С.Е. О нецелочисленных вершинах трехиндексных транспортных многогранников / С. Е. Борисов, Р. В. Филипов // Современные проблемы математики и информатики: Сборник научных трудов молодых ученых, аспирантов и студентов / Яросл. гос. ун-т. Ярославль, 1999. - Вып. 2. - С. 153 - 156.
Review
For citations:
Uryvaev B.V. On Relaxation Polytope of 3-satisfiability Problem. Modeling and Analysis of Information Systems. 2007;14(2):7-11. (In Russ.)
Views:
425
Email this article 