сокращение отображения за полиномиальное время для NP
Просто найдите текст ignore: ": hidden" в файле проверки jquery и прокомментируйте его. После комментариев это никогда не потеряет никаких скрытых элементов для проверки ...
Спасибо
1 ответ
B находится в NP, поэтому есть некоторая машина Тьюринга, назовем ее M (B), которая решает B за полиномиальное время. Кроме того, поскольку A сводится к B за полиномиальное время, существуют TM, давайте назовем их M (R) и M (R '), которые преобразуют входные экземпляры A во входные экземпляры B, а выходы B - в выходы A , оба в полиномиальное время. Рассмотрим TM, сконструированный следующим образом:
- Выполните M (R) на входной ленте, а затем сбросьте головку ленты
- Выполните M (B) на входной ленте, а затем сбросьте головка ленты
- Выполнить M (R ') на входной ленте, а затем сбросить головку ленты
Каждый из этих шагов занимает полиномиальное время, поэтому весь процесс занимает полиномиальное время. Поскольку недетерминированные машины Тьюринга закрываются при конкатенации (путем замены halt_accept в LHS начальным состоянием RHS), вычисление может быть выполнено одной недетерминированной машиной Тьюринга, объединяющей эти этапы. Таким образом, A может быть определена недетерминированной машиной Тьюринга за полиномиальное время - критерий включения в NP.