An easy observation is that if a problem $A$ is decidable by a polynomial-time nondeterministic program using $O(\log n)$ nondeterministic bits (i.e., all witnesses are logarithmic in length), then $A \in \mathsf{P}$.If one then asks the question, Is it easier to verify a witness than to find one? for such problems, and one considers all polynomial running times equivalent, then the answer is no, since one can find such witnesses in polynomial time by searching through all potential witnesses.But what if we consider fine-grained distinctions between polynomial running times? I'm wondering if there is a concrete example of a natural problem in $\mathsf{P}$ that has logarithmic-length witnesses that are easier to verify than to find, where easier means a smaller polynomial running time.For example, known algorithms for perfect matching in graphs take polynomial time, but more than $O(n)$ time on a graph with $n$ nodes. But given a set of $n/2$ pairs of nodes (a witness), it is easy to verify in time $O(n)$ that it is a matching. However, the matching itself requires at $\Omega(n)$ bits to encode.Is there some natural problem that achieves a similar (apparent) speedup in verification versus finding, in which the witness has logarithmic length?
Example of logarithmic length witness being easier to verify than find
cc.complexity theory