# Size of the certificate as a property of the problem

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.

• "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. Mar 4 at 18:18