доказательство NP-полноты задачи.

[Чудо-в-перьях]

Всем добрый день!))

Мне нужно доказать, что некоторая алгоритмическая задача (алгоритм построения выводов в силлогистике ) является NP-полной (или, в случае неудачи, показать, что она решается за полиномиальное время) .Т.е. я должна доказать, что задача SAT (проверка выполнимости булевой формулы в КНФ) также сложна, как и вычисление р-та данным алгоритом? Какие тут может быть общий план действий? И что лучше всего почитать?))))

[Xaositect]

Гэри М., Джонсон Д. — Вычислительные машины и труднорешаемые задачи

[Чудо-в-перьях]

Спасибо большое!!)))

[Профессор Снэйп]

Чудо-в-перьях в сообщении #250033 писал(а):

Мне нужно доказать, что некоторая алгоритмическая задача является NP-полной (или, в случае неудачи, показать, что она решается за полиномиальное время) .

А почему именно эти две альтернативы. Разве NP-задача не может быть одновременно не полиномиальной и не NP-полной?

[Xaositect]

Профессор Снэйп в сообщении #250143 писал(а):

А почему именно эти две альтернативы. Разве NP-задача не может быть одновременно не полиномиальной и не NP-полной?

Может. Но среди стественных задач таких мало.

Хотя вот задача определения истинности в какой-то теории вполне может быть даже не NP-полной, а более сложной.

[Профессор Снэйп]

Xaositect в сообщении #250150 писал(а):

Хотя вот задача определения истинности в какой-то теории вполне может быть даже не NP-полной, а более сложной.

Даже алгоритмически неразрешимой может оказаться

Теория первого порядка натуральных чисел (со сложением и умножением), насколько я помню, даже не арифметична. Вроде бы эквивалентна $\varnothing^{(\omega)}$ по Тьюрингу

[Xaositect]

Профессор Снэйп в сообщении #250157 писал(а):

Даже алгоритмически неразрешимой может оказаться

Ну, силлогистика не арифметика, такого быть не должно.

[Профессор Снэйп]

Xaositect в сообщении #250175 писал(а):

Ну, силлогистика не арифметика, такого быть не должно.

Ага, там всё должно быть перечислимо. Насчёт разрешимости...

Кто-нибудь из математиков может похвастаться, что знает эту самую силлогистику? Или это сугубо прерогатива философов, юристов и прочих гуманитарев? Я, например, практически совершенно не знаю

[Xaositect]

Профессор Снэйп в сообщении #250189 писал(а):

Кто-нибудь из математиков может похвастаться, что знает эту самую силлогистику? Или это сугубо прерогатива философов, юристов и прочих гуманитарев? Я, например, практически совершенно не знаю

Лукасевич Я. — Аристотелевская силлогистика с точки зрения современной формальной логики

[Чудо-в-перьях]

Профессор Снэйп
Она разрешимая, но сложность алгоритма поиска вывода в натуральных исчислениях различных силлогистик точно больше полиномиальной. Скорее всего, она NP (вроде что-то получилось за выходные набросать--теперь надо проверить).
Жалко, что силлогистика мало используется в математике: по сути, это фрагмент исчисления предикатов, в ряде случаев экзистенциальный. А в него у нас один препод даже всю ЛП погружал.. тут масса разных иснтересный вещей вылезает Не зря, не зря Л. Кэрролл так любил силлогистику)) у него есть совершенно зверские примеры в "Истории с узелками", которые не только гуманитариев с ума сведут))