Exemplo de testemunha de comprimento logarítmico mais fácil de verificar do que encontrar

Uma observação fácil é que, se um problema é determinável por um programa não-determinístico de tempo polinomial usando S ( log n ) bits de nondeterministic (isto é, todas as testemunhas são logarítmicas em comprimento), em seguida, uma ∈ P .$A$$O(\log n)$$A \in \mathsf{P}$

Se alguém fizer a pergunta: "É mais fácil verificar uma testemunha do que encontrar uma?" para esses problemas e se considerar todos os tempos de execução polinomiais equivalentes, a resposta é não, pois é possível encontrar essas testemunhas em tempo polinomial pesquisando todas as possíveis testemunhas.

Mas e se considerarmos distinções refinadas entre tempos de execução polinomiais? Gostaria de saber se existe um exemplo concreto de um problema natural em que tenha testemunhas de comprimento logarítmico mais fáceis de verificar do que encontrar, onde "mais fácil" significa um tempo de execução polinomial menor.$\mathsf{P}$

Por exemplo, algoritmos conhecidos para a correspondência perfeita nos gráficos levam tempo polinomial, mas mais do que em um gráfico com n nós. Porém, dado um conjunto de n / 2 pares de nós (uma testemunha), é fácil verificar no tempo O ( n ) que é uma correspondência. No entanto, a correspondência em si requer codificação em Ω ( n ) bits.$O(n)$$n$$n/2$$O(n)$$\Omega(n)$

Existe algum problema natural que atinge uma aceleração semelhante (aparente) na verificação versus descoberta, em que a testemunha tem comprimento logarítmico ?

$x$$n$

$O(n^2)$

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