НТАЙМ

N РАЗ Определение класса NTIME NTIME(f(n)) — класс задач, решаемых недетерминированной машиной Тьюринга за время O(f(n)).  f(n) — функция, определяющая […]

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. 

Полный текст статьи:

НТАЙМ — Википедия

Оставьте комментарий

Прокрутить вверх