Задача ВЫП

Задача ВЫП

Задача выполнимости булевых формул (SAT или ВЫП) — задача распознавания, важная для теории вычислительной сложности.

Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций \wedge (И), \vee (ИЛИ) и \neg (HE). Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ЛОЖЬ и ИСТИНА так, чтобы формула стала истинной.

Согласно теореме Кука, доказанной Стивеном Куком в 1971-м году, задача SAT NP-полна.

Содержание

Точная формулировка

Чтобы четко сформулировать задачу распознавания, необходимо условиться об алфавите, с помощью которого задаются экземпляры языка. Этот алфавит должен быть фиксирован и конечен. В своей книге Хопкрофт, Мотвани и Ульман предлагают использовать следующий алфавит: {«\wedge», «\vee», «\neg», «(», «)», «x», «0», «1»}.

При использовании такого алфавита скобки и операторы записываются естественным образом, а переменные получают следующие имена: x1, x10, x11, x100 и т. д., согласно их номерам, записанным в двоичной системе счисления.

Пусть некоторая булева формула, записанная в обычной математической нотации, имела длину N символов. В ней каждое вхождение каждой переменной было описано хотя бы одним символом, следовательно, всего в данной формуле не более N переменных. Значит, в предложенной выше нотации каждая переменная будет записана с помощью O\left(\log{N}\right) символов. В таком случае, вся формула в новой нотации будет иметь длину O\left(N\log{N}\right) символов, то есть длина строки возрастет в полиномиальное число раз.

Например, формула a\wedge\neg(b\vee c) примет вид x1\wedge\neg(x10\vee x11).

Вычислительная сложность

В 1971-м году в статье Стивена Кука был впервые введен термин «NP-полная задача», и задача SAT была первой задачей, для которой доказывалось это свойство.

В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT. После появления результатов Кука была доказана NP-полнота для множества других задач. При этом чаще всего для доказательства NP-полноты некоторой задачи приводится полиномиальное сведение задачи SAT к данной задаче, возможно в несколько шагов, то есть с использованием нескольких промежуточных задач.

Частные случаи задачи SAT

Интересными важными частными случаями задачи SAT являются:

  • Задача выполнимости булевых формул в конъюнктивной нормальной форме (SATCNF или ВКНФ) — аналогичная задача, с наложенной на формулу условием: она должна быть записана в конъюнктивной нормальной форме. Задача ВКНФ также NP-полна.
  • Задача выполнимости булевых формул в k-конъюнктивной нормальной форме (k-SAT или k-ВЫП) — задача выполнимости при условии, что формула записана в k-конъюнктивной нормальной форме. Эта задача является NP-полной при k\geq 3.
  • Задача выполнимости булевых формул в 2-конъюнктивной нормальной форме имеет полиномиальное решение, то есть принадлежит классу P.

См. также

Ссылки

Примечания


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


Смотреть что такое "Задача ВЫП" в других словарях:

  • Задача SAT — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… …   Википедия

  • Задача выполнимости булевых формул — (SAT или ВЫП) важная для теории вычислительной сложности алгоритмическая задача. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача заключается в следующем: можно ли… …   Википедия

  • Задача N тел — Гравитационная задача N тел формулируется следующим образом. В пустоте находится N материальных точек, взаимодействующих по закону тяготения Ньютона. В начальный момент времени заданы массы, положения и скорости. Требуется найти положения точек… …   Википедия

  • Задача n-тел — Гравитационная задача N тел формулируется следующим образом. В пустоте находится N материальных точек, взаимодействующих по закону тяготения Ньютона. В начальный момент времени заданы массы, положения и скорости. Требуется найти положения точек… …   Википедия

  • Гравитационная задача N тел — является классической проблемой небесной механики и гравитационной динамики Ньютона. Она формулируется следующим образом. В пустоте находится N материальных точек, массы которых известны {mi}. Пусть попарное взаимодействие точек подчинено закону… …   Википедия

  • Гравитационная задача N-тел — формулируется следующим образом. В пустоте находится N материальных точек, взаимодействующих по закону тяготения Ньютона. В начальный момент времени заданы массы, положения и скорости. Требуется найти положения точек для всех последующих моментов …   Википедия

  • Гравитационная задача n-тел — формулируется следующим образом. В пустоте находится N материальных точек, взаимодействующих по закону тяготения Ньютона. В начальный момент времени заданы массы, положения и скорости. Требуется найти положения точек для всех последующих моментов …   Википедия

  • Статистика теоретическая — наука, занимающаяся изучением приемов систематического наблюдения над массовыми явлениями социальной жизни человека, составления численных их описаний и научной обработки этих описаний. Таким образом, теоретическая статистика есть наука… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • Русская литература — I.ВВЕДЕНИЕ II.РУССКАЯ УСТНАЯ ПОЭЗИЯ А.Периодизация истории устной поэзии Б.Развитие старинной устной поэзии 1.Древнейшие истоки устной поэзии. Устнопоэтическое творчество древней Руси с X до середины XVIв. 2.Устная поэзия с середины XVI до конца… …   Литературная энциклопедия

  • Суворов, Александр Васильевич — (князь Италийский, граф Рымникский) — генералиссимус Российских войск, фельдмаршал австрийской армии, великий маршал войск пьемонтских, граф Священной Римской империи, наследственный принц Сардинского королевского дома, гранд короны и кузен …   Большая биографическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»