Natural NP-complete problems with "large" witnesses The question on cstheory "What is NP restricted to linear size witnesses?" asks about the class NP restricted to linear size $O(n)$ witnesses, but


  Are 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&amp;J, every natural NPC problem seems to have witnesses (strictly) smaller than $n$.


  Is there a "reason/explanation" for it ?
How about the edge coloring number in a dense graph (aka Chromatic index)? You are given the adjacency matrix of an $n$ vertex graph ($n^2$ bit input), but the natural witness describing the coloring has size $n^2\log n$. Of course, there might be shorter proofs for class 1 graphs in Vizing's theorem.

See also this possibly related question