<p>Consider the decision problem which decides whether a given binary input <span class="math-container">$x$</span> of length <span class="math-container">$n$</span> is a non-palindrome.</p>
<p>There is a pretty standard communication complexity proof that a single tape TM requires at least <span class="math-container">$\Omega(n^2)$</span> time to solve this problem.</p>
<p>On the other hand, we can also solve this problem using a nondeterministic algorithm with a <span class="math-container">$\log(n)$</span> length witness <span class="math-container">$i$</span>: the algorithm accepts whenever the <span class="math-container">$i$</span>th bit from the start of <span class="math-container">$x$</span> differs from the <span class="math-container">$i$</span>th bit from the end of <span class="math-container">$x$</span>. Identifying the <span class="math-container">$i$</span>th bit from the start or end of a length <span class="math-container">$n$</span> bitstring can be accomplished in <span class="math-container">$O(n \log n)$</span> time on a single tape TM.</p>

CC BY-SA 3.0
2017-01-26T01:42:46.097Z
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
CC BY-SA 4.0
2017-01-25T05:21:35.333Z
2021-05-10T01:37:57.470Z
2021-05-10T01:37:57.470Z
Mikhail Rudoy
<p>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}$.</p>

<p>If one then asks the question, <em>"Is it easier to verify a witness than to find one?"</em> 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.</p>

<p>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.</p>

<p>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.</p>

<p>Is there some natural problem that achieves a similar (apparent) speedup in verification versus finding, in which the witness has <em>logarithmic</em> length?</p>

CC BY-SA 3.0
2017-01-25T15:27:05.827Z
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
CC BY-SA 3.0
2017-01-26T01:48:49.830Z
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
CC BY-SA 4.0
2023-06-20T09:44:49.180Z
The above link is broken, I suppose it is [this](https://www.cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf) one. (doi: https://doi.org/10.1137/10080703X)
Janmar
<cc.complexity-theory>
Example of logarithmic length witness being easier to verify than find
Dave Doty
# Example of logarithmic length witness being easier to verify than find

(Asked by: username_0 on 2017-01-25)

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?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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).  
> **username_2**: 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.)  
> **username_3**: The above link is broken, I suppose it is [this](https://www.cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf) one. (doi: https://doi.org/10.1137/10080703X)  

---

## 1 answers

### Answer by username_4 on 2017-01-25. Score: 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.

> **Comments:**
> **username_2**: 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.  

---

