Przykład logarytmicznej długości świadka jest łatwiejszy do zweryfikowania niż znalezienia

Łatwe spostrzeżenie, że, jeżeli problem jest rozstrzygalne przez wielomian czasu niedeterministycznych programu przy O ( log n ) niedeterministycznych bitów (czyli wszystkie świadków logarytmiczna długości), a następnie ∈ P .$A$$O(\log n)$$A \in \mathsf{P}$

Jeśli ktoś zadaje pytanie: „Czy łatwiej jest zweryfikować świadka niż go znaleźć?” dla takich problemów, i uważa się, że wszystkie czasy wielomianu są równoważne, wówczas odpowiedź brzmi „nie”, ponieważ można znaleźć takich świadków w czasie wielomianowym, przeszukując wszystkich potencjalnych świadków.

Ale co, jeśli weźmiemy pod uwagę drobnoziarniste rozróżnienie między wielomianowymi czasami działania? Zastanawiam się, czy istnieje konkretny przykład naturalnego problemu w który ma świadków o długości logarytmicznej, które łatwiej jest zweryfikować niż znaleźć, gdzie „łatwiej” oznacza krótszy czas działania wielomianu.$\mathsf{P}$

Na przykład znane algorytmy do idealnego dopasowania na wykresach zajmują czas wielomianowy, ale więcej niż czas na wykresie z n węzłami. Ale biorąc pod uwagę zestaw n / 2 par węzłów (świadka), łatwo jest sprawdzić w czasie O ( n ) , czy jest on zgodny. Jednak samo dopasowanie wymaga kodowania Ω ( n ) bitów.$O(n)$$n$$n/2$$O(n)$$\Omega(n)$

Czy istnieje jakiś naturalny problem, który powoduje podobne (pozorne) przyspieszenie weryfikacji w porównaniu ze znalezieniem, w którym świadek ma długość logarytmiczną ?

$x$$n$

$O(n^2)$

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