N РАЗ
-
Определение класса NTIME
- NTIME(f(n)) — класс задач, решаемых недетерминированной машиной Тьюринга за время O(f(n)).
- f(n) — функция, определяющая время работы машины.
- n — размер входных данных.
-
Свойства NTIME
- Машина отклоняет данные, если ответ «нет», и принимает их, если «да».
- Детерминированная машина M с временем работы O(f(n)) проверяет сертификат длины O(f(n)).
-
Пространственные ограничения
- Пространство для машины не ограничено, но ограничено временем работы.
-
Связь с другими классами сложности
- NP определяется через NTIME.
- NEXP также определяется через NTIME.
- Недетерминированные машины решают больше задач за асимптотически большее время по сравнению с детерминированными машинами.
- NTIME связан с DSPACE.
-
Обобщение NTIME
- Время, определяемое с помощью чередующихся машин Тьюринга, является обобщением NTIME.
Полный текст статьи: