The question on cstheory What is NP restricted to linear size witnesses? asks about the class NP restricted to linear size $O(n)$ witnesses, butAre there natural NP-complete problems in which (yes) instances  of size $n$ require witnesses of size greater than $n$?Clearly we can build artificial problems like:$L = \{ 1^nw \mid w \text{ encodes a satisfiable formula and } |w|=n \}$$L = \{ \varphi \mid \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$After a quick look at G&J, every natural NPC problem seems to have witnesses (strictly) smaller than $n$.Is there a reason/explanation for it ?
Natural NP-complete problems with large witnesses
cc.complexity theory;np;proof complexity