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.
UPDATE: I assume the problem has a solution. So I am not interested in the decision version, but rather I assume there does exist a (positive) solution and I'm trying to find it.
For example, I give you a SAT problem and I tell you there is a solution, please find at least one. This should also be NP-complete. Now if the SAT Problem has 3 literals, it's easy to solve. If it has n/2 literals and n clauses, it's probably not easy. So my question is at what point it becomes easy and why.
In the case of subset sum. I give you a subset sum problem instance and ask you to find me one of the solutions, which I tell you exist. This is still hard to do, but is it also hard to do if I tell you that the/a solution will be a subset of number of size n/2 for a list of length n? Again, I'm interested in understanding at which sizes of the solution the problem becomes easy.
For hamiltonian cycles, I ask you to find a cycle of size $k$ in a graph of size $n$, for which $k$ is the problem hard and so on...
I looked at the analysis of Fixed Tractable Problems, but they seem to focus on parameters that are fixed to constants, which is not necessarily what I want to know I think.
My intuition would be that most (NP-hard) search problems become easy once the witness size is smaller than $log(n)$ or bigger than $n-log(n)$, but I don't know how to actually support this claim formally.
I hope my question is a bit clearer now.