Оглавление
ВРЕМЯ ОЖИДАНИЯ
-
Определение и иерархия сложности EXPTIME
- EXPTIME – класс задач, решаемых детерминированной машиной Тьюринга за экспоненциальное время.
- Включает в себя более сложные оракулы и квантификаторы, чем P.
- Обобщается на задачи с двойной экспоненциальной временной сложностью.
-
Связь с другими классами сложности
- EXPTIME соотносится с PSPACE, NP, NEXPTIME, EXPSPACE и другими классами.
- Теорема об иерархии во времени и пространстве утверждает, что P ∈ EXPTIME, NP ∈ NEXPTIME и PSPACE ∈ EXPSPACE.
-
Формальное определение и отношения с другими классами
- EXPTIME может быть переформулирован как класс пространства APSPACE.
- Неопределенность в отношении точных включений между классами P, NP, PSPACE и EXPTIME.
-
Задачи с полным временем выполнения
- Задачи, решаемые за время EXPTIME, считаются самыми сложными в этом классе.
- Проблема остановки и ее упрощенные версии являются важными проблемами в EXPTIME.
- Задачи, связанные с играми, такими как шахматы, шашки и Го, могут быть завершены по времени из-за экспоненциальной зависимости от размера доски.
-
Завершение времени в сжатых схемах
- Сжатые схемы используются для описания графиков в меньшем объеме.
- Задачи с P-полными графами могут быть решены в сжатом схемном представлении за короткое время.
-
Рекомендации
- Статья не содержит конкретных рекомендаций, а представляет собой обзор теории сложности и связанных с ней концепций.