Недетерминистское многочленовое время алгоритма по сравнению с сертификатом / верификатором для показывать членство в NP

Question

В этой статье ( https://arxiv.org/pdf/1706.06708.pdf ) Авторы доказывают, что оптимально решая $ n \ times n \ times n $ Cube Rubik - это проблема NP-полной. В процессе они должны показать, что соответствующая проблема решений относится к NP (раздел 2.5 на стр. 6). Для этого они описывают алгоритм, который неотнетенственно решает куб в полиноме. Мне кажется, что это больше усилий, чем необходимо.

В частности, соответствующая проблема решений является следующая проблема: проблема куба Rubik имеет в качестве ввода перестановки $ T $ $ k $ . Цель состоит в том, чтобы решить, можно ли решить $ T $ в $ K $ или меньше движений. Так, вместо того, чтобы построить недетерминированное алгоритм раствора многочлена, они могут просто дать сертификат, что решение «да» является лишь списком максимально возможным $ K $ Перемещения и проверки Это проверка это многочлена.

Так что мои вопросы следующие. Два определения ниже фактически эквивалентны?

1. np - класс сложности проблемы принятия решений, которые разрешимы недетерминистской машиной Turing в полиноме.
2. np - это класс сложности проблемы принятия решений, для которых решение может быть подтверждено в многочленом времени (детерминистически)?

И если они эквивалентны, почему авторы связанной бумаги выбирают более сложный метод (или я ошибаюсь об этом предположении)?

---

Обратите внимание, что я размещаю этот вопрос на нескольких веб-сайтах Stockexchange, так как я не уверен, где он лучше подходит. Если здесь неуместно, я счастливо удалю его. Точно так же я свяжу на хорошее решение на другом сайте, если он отвечает там.

Answer 1

Сертификат, который вы предлагаете, может быть не полиномиальным в размере ввода.

Размер ввода проблемы задачи - $ O (n ^ 3 + \ log k) $ , в то время как ваш сертификат имеет размер $ \ Omega (k \ log n) $ .Это не полиномиальный, например, для $ k= 2 ^ n $ .

Ваш сертификат будет работать, если вы установите его, например, в пустой список всякий раз, когда $ k=omgega (\ frac {n ^ 2} {\ log n}) $ , и изменить верификатор, чтобы просто проверить, разрешит ли входная конфигурация куба для любого такого значения $ K $ (например, игнорируя сертификат). .