Редактирование: Полнота относительно L-сведения. NL-полнота. P-полнота
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
− | В классах, являющихся подмножествами <tex>\mathrm{P}</tex>, не используют <tex>\mathrm{\widetilde{P}}</tex>-сведение по Карпу, так как оно оказывается | + | В классах, являющихся подмножествами <tex>\mathrm{P}</tex>, не используют <tex>\mathrm{\widetilde{P}}</tex>-сведение по Карпу, так как оно оказывается бесполезно. Для них применяется <tex>\mathrm{\widetilde{L}}</tex>-сведение (с <tex>O(\log n)</tex> дополнительной памяти). |
{{ Определение | {{ Определение |