15

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?

Dave Doty
  • 681
  • 6
  • 13
  • 3
    Consider the problem of computing whether an $n$-bit input string is not equal to the all zeros string. It takes $\Theta(n)$ time to do this, but a $\log n$ size witness (pointing to a $1$) makes this much easier (on a random-access machine). – Robin Kothari Jan 25 '17 at 15:27
  • The question is especially interesting if we consider problems with at least linear verification time on a random access machine. Section 4 of the paper https://web.stanford.edu/~rrwill/improved-algs-lbs2.pdf gives some interesting consequences of having a universal improvement over exhaustive search even with $O(\log n) $ nondeterminism. (Section 5 even proves some unconditional lower bounds.) – Ryan Williams Jan 26 '17 at 01:48
  • The above link is broken, I suppose it is this one. (doi: https://doi.org/10.1137/10080703X) – Janmar Jun 20 '23 at 09:44

1 Answers1

16

Consider the decision problem which decides whether a given binary input $x$ of length $n$ is a non-palindrome.

There is a pretty standard communication complexity proof that a single tape TM requires at least $\Omega(n^2)$ time to solve this problem.

On the other hand, we can also solve this problem using a nondeterministic algorithm with a $\log(n)$ length witness $i$: the algorithm accepts whenever the $i$th bit from the start of $x$ differs from the $i$th bit from the end of $x$. Identifying the $i$th bit from the start or end of a length $n$ bitstring can be accomplished in $O(n \log n)$ time on a single tape TM.

Turbo
  • 12,812
  • 1
  • 19
  • 68
Mikhail Rudoy
  • 2,768
  • 13
  • 24
  • 3
    Nice, you're basically "lifting" the difference between nondeterministic and deterministic communication complexity (for equality of two strings) to a separation of nondeterministic and deterministic one-tape TMs. – Ryan Williams Jan 26 '17 at 01:42