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. 
Relation between witness and problem statement
complexity theory;np complete
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.The first part of your intuition is sorta in the right direction, but the second part is wrong.If the witness size is smaller than $\lg n$, then you can enumerate all witnesses efficiently: it takes $2^{\lg n}$ time to enumerate all witnesses, and $2^{\lg n} = n$, which is polynomial.  In general, if the witness size is $\le c \cdot \lg n$ for some constant $c$, then you can enumerate all witnesses in $O(n^c)$ time, which is polynomial.This means that you can solve the decision problem efficiently: just search all possible witnesses and see if any is valid.  I'm assuming that when you say the solution to a search problem, that is defined to be the witness that proves the answer is YES.However, if the witness size is bigger than $n - \log n$, there's no reason to expect it would be easy to solve the underlying search problem.Perhaps you are thinking that the witness can't be any longer than $n$ bits long.  That's wrong.  Witnesses could be much larger than that, potentially, depending on the problem.