Are there any known upper/lower bounds on the size of a witness of some np-complete/hard problem, or more precisely the relation between the problem size and the witness size. For example, I'm interested in subset sum, set cover, SAT, hamiltonian cycles. If there is something known for other problems, I'd also be interested. To be a bit more clear, I'll explain what I mean in detail for two of those problems.

Imagine you have a subset sum problem. The list of all integers (the statement) is probably bigger than the actual set of numbers that are part of the witness. What is the smallest/biggest size a the witness subset, s.t. that the problem is still hard?

In the case of SAT I am interested in the relation between the number of distinct literals and the size of the formula. That is how much bigger does or can a formula be in comparison to the total number of literals.