Пример логарифмической длины свидетеля, который легче проверить, чем найти

Легко наблюдение состоит в том, что если проблема разрешима недетерминированной программы полиномиальное время , используя O ( журнал N ) недетерминированных битов (то есть, все свидетели логарифмические в длину), то ∈ P .$A$$O(\log n)$$A \in \mathsf{P}$

Если тогда кто-то задает вопрос: «Легче ли проверить свидетеля, чем найти его?» для таких проблем, и каждый считает, что все полиномиальные времена выполнения эквивалентны, тогда ответ - нет, так как можно найти таких свидетелей за полиномиальное время, просматривая всех потенциальных свидетелей.

Но что, если мы рассмотрим мелкозернистые различия между временем полинома? Мне интересно, есть ли конкретный пример естественной проблемы в которой есть свидетели логарифмической длины, которые легче проверить, чем найти, где «проще» означает меньшее время полинома.$\mathsf{P}$

Например, известные алгоритмы идеального сопоставления в графах занимают полиномиальное время, но больше, чем времени на графе с n узлами. Но, учитывая набор из n / 2 пар узлов (свидетель), легко за время O ( n ) проверить, что это совпадение. Однако само сопоставление требует в Ω ( n ) битов для кодирования.$O(n)$$n$$n/2$$O(n)$$\Omega(n)$

Существует ли какая-то естественная проблема, которая обеспечивает аналогичное (кажущееся) ускорение проверки по сравнению с обнаружением, при котором свидетель имеет логарифмическую длину?

$x$$n$

$O(n^2)$

$\log(n)$$i$$i$$x$$i$$x$$i$$n$$O(n \log n)$