МА́ССОВАЯ ПРОБЛЕ́МА
-
Рубрика: Математика
-
Скопировать библиографическую ссылку:
МА́ССОВАЯ ПРОБЛЕ́МА, проблема нахождения алгоритма для решения бесконечной серии однотипных задач, зависящих от некоторого параметра. Простейшие примеры М. п.: сложить 2 данных числа, умножить 2 данных числа, проверить, является данное целое число простым или нет, разложить данную функцию в степенной ряд. Если такого алгоритма не существует, то говорят, что рассматриваемая М. п. неразрешима. Задачу о существовании алгоритма, решающего данную М. п., иногда называют проблемой разрешимости. Этот термин впервые появился в связи с проблемой распознавания выводимости формул в классич. исчислении предикатов. Вообще говоря, проблемой разрешимости данной М. п. естественно считать задачу о том, разрешима или нет эта М. п., т. е. вопрос о существовании искомого алгоритма.
См. также Алгоритмическая проблема.