maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State Universitymais-1117Research ArticleОригинальные статьиArticlesО релаксационном многограннике задачи «3-выполнимость»On Relaxation Polytope of 3-satisfiability ProblemУрываевБ. В.UryvaevB. V.boreas@rambler.ruЯрославский государственный университетRussian Federation200720062007142711Copyright © Урываев Б.В., 20072007Урываев Б.В.Uryvaev B.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1117

Исследуются свойства многогранника, ассоциированного с задачей «3-выполнимость». Устанавливается, в частност

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Бондаренко, В.А. Полиэдральные графы и сложность в комбинаторной оптимизации / В. А. Бонда-ренко. - Яросл. гос. ун-т. - Ярославль, 1995. - 126 с.Бондаренко, В.А. Полиэдральные графы и сложность в комбинаторной оптимизации / В. А. Бонда-ренко. - Яросл. гос. ун-т. - Ярославль, 1995. - 126 с.Деза, М. М. Геометрия разрезов и метрик / М.М. Деза, М. Лоран; пер. Е. Пантелеевой и П. Сергеева / под ред. В. Гришухина. - М.: МЦНМО, 2001. - 736 с.Деза, М. М. Геометрия разрезов и метрик / М.М. Деза, М. Лоран; пер. Е. Пантелеевой и П. Сергеева / под ред. В. Гришухина. - М.: МЦНМО, 2001. - 736 с.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. - М.: Мир, 1982. - 416 с.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. - М.: Мир, 1982. - 416 с.Емеличев, В.А. Многогранники, графы, оптимизация / В.А. Емеличев, М.М. Ковалев, М. К. Кравцов. - М.: Наука, 1981. - 344 с.Емеличев, В.А. Многогранники, графы, оптимизация / В.А. Емеличев, М.М. Ковалев, М. К. Кравцов. - М.: Наука, 1981. - 344 с.Ильичев, А.П. О крайних точках многогранников многоиндексных транспортных задач / А.П. Ильичев, В.Н. Шевченко // Комбинаторно-алгебраические методы в прикладной математике. - Горький: Изд-во ГГУ, 1981. - С. 66 - 72.Ильичев, А.П. О крайних точках многогранников многоиндексных транспортных задач / А.П. Ильичев, В.Н. Шевченко // Комбинаторно-алгебраические методы в прикладной математике. - Горький: Изд-во ГГУ, 1981. - С. 66 - 72.Борисов, С.Е. О нецелочисленных вершинах трехиндексных транспортных многогранников / С. Е. Борисов, Р. В. Филипов // Современные проблемы математики и информатики: Сборник научных трудов молодых ученых, аспирантов и студентов / Яросл. гос. ун-т. Ярославль, 1999. - Вып. 2. - С. 153 - 156.Борисов, С.Е. О нецелочисленных вершинах трехиндексных транспортных многогранников / С. Е. Борисов, Р. В. Филипов // Современные проблемы математики и информатики: Сборник научных трудов молодых ученых, аспирантов и студентов / Яросл. гос. ун-т. Ярославль, 1999. - Вып. 2. - С. 153 - 156.

The authors declare that there are no conflicts of interest present.