О подходах к построению полиномиальных алгоритмов решения задач дискретной оптимизации относящихся к классу NP-полных задач

Abstract

Рассматривается возможность построения полиномиальных алгоритмов решения задач определения максимальных независимых множеств и решения SAT-задач. Во многих прикладных задачах синтеза и анализа вычислительных систем и сетей и разработки специального математического обеспечения для их функционирования требуется найти в конечном множестве объектов максимальную систему объектов, попарно не связанных друг с другом, или же выбрать минимальную систему объектов, связанных со всеми другими. Формулировки подобных задач на языке теории графов приводят к понятиям независимости и покрытия.