Задача разрешимости: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Addbot (обсуждение | вклад) м Перемещение 17 интервики на Викиданные, d:q3262192 |
Нет описания правки |
||
Строка 2:
Например, проблема ''«дано два числа ''x'' и ''y'', делится ли ''x'' на ''у''?»'' является проблемой разрешимости. Ответ может быть дан либо «да» либо «нет» и зависит от значений ''x'' и ''y''. Метод решения проблемы разрешимости, представленный в форме алгоритма, называется разрешающей процедурой для этой проблемы. Так, разрешающая процедура для проблемы разрешимости ''«дано два числа ''x'' и ''y'', делится ли нацело ''x'' на ''у''?»'' должна определять совокупность действий, которые следует предпринять для проверки делимости нацело ''x'' на ''у'' для данных ''x'' и ''y''. Один из таких алгоритмов [[деление столбиком]] изучается в начальной школе. Остаток равный нулю означает ответ «да», иначе «нет». Проблема разрешимости, для которой существует разрешающая процедура, называется разрешимой.
Не все математические задачи могут быть сформулированы как проблемы разрешимости. Вычисление произведения двух чисел, поиск наиболее быстрого алгоритма умножения чисел и [[Оптимизация (математика)|оптимизационные задачи]], в частности, [[задача коммивояжёра]] в классической постановке не являются проблемами разрешимости. В теории сложности алгоритмов это приводит к различению понятий [[NP-полнота|NP-полноты]] и [[NP-трудность|NP-трудности]].
Исследования в области [[теории рекурсии]] часто сфокусированы на проблемах разрешимости, поскольку к ним без потери общности сводятся многие задачи.
| |||