Exemple de témoin de longueur logarithmique plus facile à vérifier qu'à trouver

Une observation simple est que si un problème est décidable par un programme non déterministe polynomial en utilisant O ( log n ) des bits non déterministes ( par exemple, tous les témoins sont logarithmiques de long), alors A ∈ P .$A$$O(\log n)$$A \in \mathsf{P}$

Si l'on pose ensuite la question: "Est-il plus facile de vérifier un témoin que d'en trouver un?" pour de tels problèmes, et on considère tous les temps de fonctionnement polynomiaux comme équivalents, alors la réponse est non, car on peut trouver de tels témoins en temps polynomial en cherchant parmi tous les témoins potentiels.

Mais que se passe-t-il si nous considérons des distinctions fines entre les temps de marche polynomiaux? Je me demande s'il existe un exemple concret d'un problème naturel dans qui a des témoins de longueur logarithmique qui sont plus faciles à vérifier qu'à trouver, où «plus facile» signifie un temps d'exécution polynomial plus court.$\mathsf{P}$

Par exemple, les algorithmes connus pour une correspondance parfaite dans les graphiques prennent un temps polynomial, mais plus de temps sur un graphique à n nœuds. Mais étant donné un ensemble de n / 2 paires de nœuds (témoin), il est facile de vérifier dans le temps O ( n ) qu'il s'agit d'une correspondance. Cependant, la correspondance elle-même nécessite au moins Ω ( n ) bits pour coder.$O(n)$$n$$n/2$$O(n)$$\Omega(n)$

Existe-t-il un problème naturel qui entraîne une accélération similaire (apparente) de la vérification par rapport à la constatation, dans lequel le témoin a une longueur logarithmique ?

$x$$n$

$O(n^2)$

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