4
$\begingroup$

Suppose I have a decision problem $\mathcal{L}\subseteq\Sigma^*$ and a verifier $V$ that recognizes $\mathcal{L}$, i.e. $L(V)=\mathcal{L}$. Let's arbitrarily choose some certificate $c(w)$ for $w \in \mathcal{L}$ such that $V$ accepts $(w,c)$. Let's consider the functions that bound the size of the certificate $|c(w)|$ based on the size of the input $|w|$. If $\mathcal{L} \in \mathsf{NP}$ then for some appropriate $V$ the function that bounds the size must be polynomial (supposing that we only include to the verifier only the information/bits that the verifier will use). Also if for some verifier the function that bounds the length is logarithmic and the verifier runs in polynomial time then $\mathcal{L}\in\mathsf{P}$. This got me thinking that maybe looking at the shortest witnesses of a specific problem could help us figure out its complexity.

For example if the shortest certificate of a problem (i.e. the smallest class of function that bounds the certificate of a verifier for that problem) is strictly bigger than polynomial then that problem cannot be in $\mathsf{P}$. Obviously I don't really care about analyzing the bounding functions, I would guess that this is close to impossible in almost every case. But still these sort of arguments seem interesting to me.

Is this whole direction useful at all? Is there some well known theory that analyzes this perspective? I was about to start playing around with these ideas but I figured I should ask here first so I can save myself some time.

$\endgroup$
1
  • 1
    $\begingroup$ "then that problem cannot be in $\mathsf P$". Or even in $\mathsf{NP}$. But practically you'd want average or longest certificate (among shortest certificates for all inputs of given size) length, because for every $n$ there is a SAT instance over $n$ variables that has $\mathcal O(1)$-long proofs or refutations. $\endgroup$
    – rus9384
    Mar 4 at 18:18

1 Answer 1

4
$\begingroup$

I would say you have made a good case that it is at least a little bit interesting, because imposing different bounds on the length of the witness, combined with different bounds on the running time of the verifier, yields different complexity classes.

A few nitpicky remarks:

  1. The length of witnesses depends on both the problem and the specific verifier chosen. So it doesn't make sense to talk about "the shortest witnesses for a problem", as the shortest witness also depends on which verifier you have chosen.

  2. There is no shortest witness. You can always make the witness one bit shorter if you are willing to double the computation time of the verifier (it can try both possibilities for the missing bit).

$\endgroup$
2
  • $\begingroup$ To be honest, I didn't really think about the complications of your second remark. I just felt that we would only pay attention to the asymptotic behavior of the functions that would bound the sizes but perhaps rigorously defining that would yield irrelevant or trivial results (e.g. it is not clear how one would deal with the example in your remark). As for remark 1, it is the basis of my idea, to consider the smallest upper bound function on the size of the certificate over all the verifiers (or at the subset that we know etc.). I think remark 1 points to the same problem as remark 2. $\endgroup$
    – Yuumita
    Mar 4 at 17:57
  • $\begingroup$ @Yuumita, cool, that makes sense to me and addresses my comments nicely! $\endgroup$
    – D.W.
    Mar 4 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.