Полный (сложность)
-
Определение сложности задач
- Задача p считается завершенной для класса сложности C, если она является «самой сложной» в этом классе.
- Задача p называется сложной для C, если существует сокращение от любой задачи из C к p.
- Если задача сложна для класса и для его члена, то она считается решенной для этого класса.
-
Полные классы сложности
- NP-complete — первый и наиболее известный полный класс, содержащий множество трудноразрешимых задач.
- Задачи, которые являются сложными для класса C, называются C-hard, например NP-жесткие.
-
Вычислительная сложность и рекурсивное перечисление
- Предполагается, что сокращение не имеет более высокой вычислительной сложности, чем сам класс.
- Классы сложности с рекурсивным перечислением имеют известные проблемы, в отличие от классов без рекурсивного перечисления.
-
Примеры неполных классов сложности
- Существуют классы сложности, в которых нет полных проблем, например, язык M, для которого BPPM не имеет полных проблем.
-
Рекомендации
- Статья не содержит конкретных рекомендаций.
Полный текст статьи: