Редактирование: Класс P
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 10: | Строка 10: | ||
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его; | # если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его; | ||
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его. | # если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
== Свойства класса P == | == Свойства класса P == | ||
Строка 74: | Строка 69: | ||
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref> | * проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref> | ||
− | Но существуют задачи не из <tex>\mathrm{P}</tex>, так как из [[теорема о временной иерархии|теоремы о временной иерархии]] следует, что <tex>\exists L \in \mathrm{EXP}\setminus\mathrm{P}</tex>. | + | Но существуют задачи и не из <tex>\mathrm{P}</tex>, так как из [[теорема о временной иерархии|теоремы о временной иерархии]] следует, что <tex>\exists L \in \mathrm{EXP}\setminus\mathrm{P}</tex>. |
Строка 91: | Строка 86: | ||
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex> | <tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex> | ||
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]]. | Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]]. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
}} | }} | ||
Строка 109: | Строка 91: | ||
<references/> | <references/> | ||
− | [[Категория: | + | [[Категория: Теория сложности]] |