Дозволу проблема

ДОЗВОЛУ ПРОБЛЕМА виникла у зв’язку з усвідомленням неможливості провести деякі побудови дозволеними методами. Першими прикладами нерозв’язних завдань з’явилися рішення радикалів рівнянь вище четвертого ступеня і неможливість провести деякі побудови циркулем і лінійкою.

Загальна формулювання проблеми дозволу наступна: даний клас методів Ф, даний клас проблем Р. Можна знайти єдиний метод f ∈Φ (дозволяє метод), що дозволяє вирішити кожну з проблем Р, для якої в принципі існує рішення?

Часто в текстах з логіки та математики розглядається більш приватна формулювання проблеми дозволу, звана алгоритмічної разрешимостью, в якій дозволяє метод повинен бути алгоритмом, тобто клас методів Φ фіксується і вважається безліччю алгоритмів. Історично алгоритмічна нерозв’язності була першим явно виділеним випадком загальної проблеми дозволу. Останнім часом у зв’язку з усвідомленням різниці між теоретичною і практичної вычислимостью з’явилася третя формулювання, коли дозволяє метод – не просто алгоритм, а алгоритм обмеженою складності. Напр., лінійна розв’язність – розв’язність програмою, вычислимая за лінійний час відносно довжини вихідних даних, NP-повна проблема – проблема, вирішувана лише програмою повного перебору.

Прикладами різною мірою нерозв’язних проблем є:

побудова моделі будь несуперечливої класичної теорії – нерозв’язна однозначно визначеними (без аксіоми вибору) теоретико-множинними функціоналами; перевірка істинності формул арифметики (відповідності) програм їх специфікації – нерозв’язна засобами формальних теорій з алгоритмічно заданою множиною аксіом;

перевірка довідності формальної арифметики або в класичній логіці предикатів – алгоритмічно нерозв’язна; завдання нормалізації висновків у логіці предикатів – нерозв’язна примітивно-рекурсивними алгоритмами;

завдання перебудови природного виведення в резолюционный – нерозв’язна алгоритмами, що роблять не більше

22}(k раз)

кроків, де n – довжина виводу, k – будь-яке фіксоване число; перевірка тавтологичности формул класичної логіки висловлювань – переборно вирішувана, але нерозв’язна менш ніж переборными алгоритмами.

Зауважимо, що нерозв’язності проблеми означає лише відсутність єдиного методу, хоча в кожному конкретному випадку її можна намагатися вирішувати, якщо рішення не претендує на занадто велику спільність. Останнім часом виявилося загальна властивість приватних рішень нерозв’язних проблем: по мірі розширення класу розв’язуваних завдань складність методів з деякого моменту швидко зростає, а ефективність настільки ж швидко убуває.

Точно так же результат про досить простий розв’язання проблеми може виявитися дезорієнтує, якщо ця достатня простота досягається лише на дуже великих об’єктах, а для малих все одно доводиться практично діяти перебором. Прикладом тут може служити класична задача про розфарбування карт чотирма кольорами.

Зведення до нерозв’язних проблем стало настільки ж потужним методом встановлення некоректності завдань яких рішень, яким є у фізиці зведення до можливості побудувати вічний двигун. Напр., того, хто написав програму, яка шукає зациклення в інших програмах, не будуть слухати, якщо він сам не надасть приклади, коли його програма не працює або працює неправильно.

Нерозв’язності проблеми розкладу числа на прості множники досить простим алгоритмом стала основою сучасної теорії надійних індивідуальних шифрів.

Одним з методів вирішення складних проблем є перехід до імовірнісним алгоритмам дозволу і до квантових обчислень. Показано, що для багатьох переборних задач є швидкі алгоритми, вирішальні їх зі як завгодно близькою до 1 наперед заданою ймовірністю.

Н.Н. Непейвода

Нова філософська енциклопедія. У чотирьох томах. / Ін-т філософії РАН. Науково-ред. рада: В. С. Стьопін, А. А. Гусейнов, Г. Ю. Семигін. М., Думка, 2010, т. III, Н – С, с. 402-403.