Финитно-аппроксимационный подход к изучению сложности рекурсивных предикатов

Рассмотрено расширение аксиоматики сложности М. Блюма, которое позволило исследовать сложность ограниченных аппроксимаций рекурсивных предикатов при весьма общих предположениях о типе вычислительного процесса. Доказан факт существования минимальных ограниченных аппроксимаций рекурсивных предикатов и возможность получения неулучшаемых оценок сложности минимальных ограниченных аппроксимаций. Получены окончательные оценки сложности ограниченных аппроксимаций при фиксированных понятиях вычислительного процесса (для конечных автоматов и для машин Тьюринга). Получена нижняя оценка сложности минимальных аппроксимаций для предиката “вхождение”. Библ. – 25 назв.