Cтраница 1
Проблема выполнимости в теории первой ступени линейного порядка не элементарна. [1]
Проблема выполнимости в теории первого порядка единственной одноместной функции не элементарна. [2]
Проблема выполнимости, очевидно, принадлежит NP, так как легко проверить, удовлетворяет ли условиям задачи предложенный выбор букв. [3]
Докажите разрешимость проблемы выполнимости соотношения i sa Rz ( mod П), если П - конечная полугруппа, заданная таблицей умножения своих элементов. [4]
Прямой алгоритм для проблемы выполнимости требует примерно 2Л шагов для формулы с п переменными. Неизвестно, существуют ли неэкспоненциальные алгоритмы для проблемы выполнимости. [5]
Мы сводим к проблеме выполнимости для этого класса проблему о недопускании альтернирующим магазинным автоматом входного слова: согласно результатам из разд. [6]
Нижняя граница для класса Аккермана получена сведением проблемы выполнимости для этого класса [6, 17] к проблеме допустимости альтернирующим магазинным автоматом входной последовательности. [7]
Наряду с попытками найти частные решения проблемы разрешимости для PrL, определенные усилия были затрачены на решение проблемы выполнимости формулы PrL, то есть на поиск алгоритмической процедуры, позволяющей определить, выполнима ли данная формула PrL или нет. [8]
Если класс формул содержит только невыполнимые формулы и формулы с конечными моделями, то для формул из этого класса проблема выполнимости разрешима, так как и невыполнимые формулы, и формулы с конечными моделями можно рекурсивно перенумеровать. Фактически ограничивающие функции известны для каждого из рассматриваемых классов, и этот метод для них применим. [9]
В этом разделе мы сформулируем важную теорему, доказанную Куком [1] и утверждающую, что любой язык из определенного широкого класса языков NP сводится к конкретному языку 5, соответствующему проблеме выполнимости булевой формулы, заданной в конъюнктивной нормальной форме. [10]
Прямой алгоритм для проблемы выполнимости требует примерно 2Л шагов для формулы с п переменными. Неизвестно, существуют ли неэкспоненциальные алгоритмы для проблемы выполнимости. [11]
Доказательство Кука было основано на понятии сводимости, которое мы упоминали ранее, когда говорили о теории вычислимости. Он показал, что всякий частный случай задачи из NP может быть преобразован в соответствующий случай проблемы выполнимости таким образом, что оба они одновременно или имеют, или не имеют решения. Более того, это преобразование может быть выполнено за полиномиальное время. Другими словами, проблема выполнимости является достаточно общей для фиксации структуры любой задачи из NP. Отсюда следует, что если бы мы умели решить проблему выполнимости за полиномиальное время, то мы сумели бы построить алгоритм, работающий полиномиальное время, для любой задачи из NP. [12]
Алгоритм Кузина для проверки выполнимости и общезначимости формулы ( § 1.1.7) упрощается в применении к КНФ. Прежде всего, проблема общезначимости становится тривиальной: речь идет о проверке тавтологичности каждого дизъюнкта. Проблема выполнимости более интересна. Предположим для простоты, что проверяемая КНФ - приведенная. [13]
Две взаимно сводимые задачи называются полиномиально эквивалентными. Кук показал, что проблема выполнимости эквивалентна так называемой задаче клик в графах. [14]
Цель этого параграфа состоит в обобщении алгоритма Куайна и стратегии Девиса и Патнема на исчисление предикатов. Из § 1.1.11 мы знаем, как проверять выполнимость нормальных форм исчисления высказываний. Здесь будет показано, что проблема выполнимости клаузальной формы в исчислении предикатов не является существенно иной. [15]