Оглавление
ВРЕМЯ ОЖИДАНИЯ
-
Определение DTIME
- DTIME – это время, необходимое для решения задачи детерминированной машиной Тьюринга.
- Используется для классификации задач по количеству вычислительных шагов.
-
Классы сложности
- Классы сложности определяются в терминах DTIME и включают задачи, решаемые за определенное количество времени.
- Существуют ограничения на объем памяти, но не на другие ресурсы сложности.
-
Важность и иерархия сложности
- DTIME соответствует реальному времени вычислений и является устойчивым к изменениям в вычислительной модели.
- P – это класс задач, решаемых за полиномиальное время, и является одним из самых больших классов сложности.
- EXPTIME включает задачи, решаемые за экспоненциальное время, и является более широким классом.
-
Модель машины и обобщения
- Для надежных классов, таких как P, модель машины может варьироваться, но это не влияет на мощность ресурса.
- Существуют различные обобщения DTIME, включая NTIME для недетерминированных машин Тьюринга и ATIME для переменных машин Тьюринга.
Полный текст статьи: