Cтраница 2
Подчеркнем, что описанный способ кодирования не единственно возможный. Различные же способы кодирования содержательно; одной и той же задачи приводят, вообще говоря, к формально различным ( с точки зрения теории вычислительной сложности) задачам. [16]
В настоящей работе рассматривается проблема нахождения множества всех совершенных сочетаний в - однородном гиперграфе. Частный случай этой задачи состоит в нахождении какого-либо совершенного сочетания в G. С точки зрения теории вычислительной сложности [3] этот частный случай эквивалентен задаче распознавания, содержит ли данный гиперграф совершенное сочетание. Для всякого I 3 задача нахождения в гиперграфе G совершенного сочетания является NP-полной. [17]
Конкретный вид таких условий определяется содержательной спецификой решаемых задач. Чтобы определить А ( х, у), следует зафиксировать ( описанный неформально) класс задач, способ кодирования отдельных задач класса двоичными словами и способ декодирования двоичных слов в объекты, способные служить решениями рассматриваемых задач. Подчеркнем, что все эти этапы не являются предметом изучения теории сложности. Объектом исследования теории вычислительной сложности является предикат А ( х, у) - булева функция на множестве пар двоичных слов. [18]
Вычислительные машины рассматриваются, по крайней мере, в трех аспектах. Во-первых, для нас они представляют практически универсальную область приложений. Прикладную сторону рассматриваемых задач можно проиллюстрировать на примере конструирования операционных систем общего назначения, хотя ряд проблем может иметь первостепенную важность в других применениях. Во-вторых, вычислительные машины должны рассматриваться как инструмент, позволяющий реализовать перечислительные и приближенные. Наконец, информатика породила теорию вычислительной сложности, которую мы здесь рассматриваем применительно к задачам упорядочения. [19]