Проблема разрешимости

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Проблема разрешимости — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров[1].

Например, проблема «дано два числа: и ; делится ли на является проблемой разрешимости. Ответ может быть дан либо «да», либо «нет» и зависит от значений и . Метод решения проблемы разрешимости, представленный в форме алгоритма, называется разрешающей процедурой для этой проблемы. Так, разрешающая процедура для проблемы разрешимости «дано два числа: и ; делится ли нацело на должна определять совокупность действий, которые следует предпринять для проверки делимости нацело на для данных чисел. Один из таких алгоритмов — деление столбиком — изучается в начальной школе. Остаток, равный нулю, означает ответ «да», в противном случае — «нет». Проблема разрешимости, для которой существует разрешающая процедура, называется разрешимой.

Не все математические задачи могут быть сформулированы как проблемы разрешимости. Вычисление произведения двух чисел, поиск наиболее быстрого алгоритма умножения чисел и оптимизационные задачи, в частности задача коммивояжёра в классической постановке, не являются проблемами разрешимости. В теории сложности алгоритмов это приводит к различению понятий NP-полноты и NP-трудности.

Исследования в области теории рекурсии часто сфокусированы на проблемах разрешимости, поскольку к ним без потери общности сводятся многие задачи.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Том Стюарт. Теория вычислений для программистов. — Litres, 2015-06-24. — С. 329. — 386 с. — ISBN 9785457831230.

Литература[править | править вики-текст]