Решаемая задача в математике и информатике¶
Решаемая задача — это задача, для которой существует алгоритм, позволяющий за конечное число шагов получить ответ при любых допустимых входных данных. Понятие противопоставляется неразрешимым задачам, для которых такого алгоритма не существует в принципе. Разграничение разрешимых и неразрешимых задач составляет предмет теории вычислимости — раздела математической логики и теории алгоритмов, сформировавшегося в 1930-е годы.
¶Определение и формализация
В строгом смысле задача называется разрешимой, если существует алгоритм (машина Тьюринга, рекурсивная функция или программа для абстрактной вычислительной модели), который для любого входа из области определения задачи за конечное время выдаёт корректный ответ и останавливается. Множество, для которого такая процедура существует, называется разрешимым, или рекурсивным.
Формализация понятия «алгоритм» была предложена независимо Аланом Тьюрингом (машина Тьюринга), Алонзо Чёрчем (лямбда-исчисление) и Эмилем Постом. Тезис Чёрча — Тьюринга утверждает, что эти модели эквивалентны и охватывают интуитивное понятие вычислимости.
¶Разрешимость и вычислительная сложность
Разрешимость не следует путать с практической вычислимостью. Задача может быть теоретически разрешимой, но требовать нереалистично больших ресурсов. Теория сложности вычислений классифицирует разрешимые задачи по затратам времени и памяти:
- P — задачи, решаемые за полиномиальное время;
- NP — задачи, решение которых проверяется за полиномиальное время;
- NP-полные — наиболее трудные задачи класса NP;
- EXPTIME — задачи, требующие экспоненциального времени.
Вопрос о совпадении классов P и NP остаётся одной из центральных нерешённых проблем математики и включён в список задач тысячелетия.
¶Неразрешимые задачи
Существование неразрешимых задач доказано в 1936 году. Классические примеры:
| Задача | Суть | Кем доказана неразрешимость |
|---|---|---|
| Проблема остановки | Определить, остановится ли программа на данном входе | Алан Тьюринг, 1936 |
| Проблема соответствий Поста | Существует ли сопоставление строк | Эмиль Пост, 1946 |
| Десятая проблема Гильберта | Разрешимость диофантовых уравнений | Юрий Матиясевич, 1970 |
| Проблема равенства слов | Эквивалентность слов в полугруппах | Пётр Новиков, 1955 |
Проблема остановки доказывается диагональным методом: предположение о существовании решающего алгоритма приводит к противоречию.
¶Российский вклад
Значительный вклад в теорию разрешимости внесли советские и российские математики. Андрей Марков-младший в 1947 году доказал неразрешимость проблемы равенства слов в конечно порождённых полугруппах и предложил понятие нормального алгорифма. Пётр Новиков получил аналогичный результат для групп. Юрий Матиясевич в 1970 году завершил решение десятой проблемы Гильберта, показав её алгоритмическую неразрешимость. Сергей Адяном в 1957 году доказана неразрешимость некоторых проблем для полугрупп и групп.
¶Практическое значение
Понятие решаемой задачи имеет прикладное значение в программировании и верификации. При проектировании систем важно понимать, какие свойства можно проверить автоматически, а какие принципиально не поддаются алгоритмической проверке. Например, задача проверки эквивалентности двух произвольных программ неразрешима, что ограничивает возможности автоматической оптимизации и верификации.
В то же время многие практически важные задачи разрешимы, хотя и трудоёмки. Для них разрабатываются приближённые и эвристические методы: жадные алгоритмы, динамическое программирование, методы ветвей и границ, метаэвристики.
¶Смежные понятия
Разрешимость связана с рядом других понятий:
- Полуразрешимость — существует алгоритм, который останавливается с ответом «да», если решение существует, но может работать бесконечно в противном случае;
- Перечислимость — множество значений вычислимой функции;
- Сводимость — сведение одной задачи к другой для доказательства неразрешимости.
Теорема Райса обобщает результат Тьюринга: любое нетривиальное свойство функции, вычисляемой программой, алгоритмически неразрешимо.
¶Примеры разрешимых задач
- Сортировка массива — решается за O(n log n);
- Проверка простоты числа — детерминированный тест AKS (2002);
- Задача о кратчайшем пути — алгоритм Дейкстры;
- Проверка выполнимости формул в логике высказываний — метод резолюций (NP-полная, но разрешимая);
- Задача линейного программирования — симплекс-метод.
¶Итоговая характеристика
Разграничение решаемых и неразрешимых задач задаёт фундаментальные границы возможностей вычислений. Оно определяет, что может быть автоматизировано в принципе, и служит теоретической основой информатики, математической логики и программирования.
Источники: Тьюринг А. «О вычислимых числах»; Марков А. А. «Теория алгорифмов»; Матиясевич Ю. В. «Десятая проблема Гильберта»; учебники по теории алгоритмов (Кормен, Ландау).