Relation between witness and problem statement

Question

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.

Answer 1

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.

1. 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".

2. 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.

Answer 2

Consider a problem named 3SAT_NORM which is a version of 3SAT restricted to instances wherein the number of literals used is equal to the number of clauses. For 3SAT_NORM, every input of $n$ clauses requires the witness to give $n$ values for the satisfying assignment. Thus, you can't simply limit the size of the witness and relate the difficulty of the new problem -- the witness size is a function of the instance size.

But, you could conceive of a different witness than the usual one for 3SAT_NORM. You could take a convention where if the witness to 3SAT_NORM only defines some subset of the literals, then the other ones are automatically assumed by convention to be given an assignment of "true".

Now, suddenly, we can limit the size of the witness and make observations about the relationship -- in particular, restricting our witness to be smaller is the same as restricting 3SAT_NORM to include only formula where satisfying assignments are guaranteed to have a lot of "true" values.

What I'm trying to get at is the witness is a property of a solution to the problem, not a property of the problem itself. SAT and subset sum seem to have "natural" witnesses, but there still could be other witnesses and some problems may have witnesses that are less natural. Some witnesses can be restricted in size, and others can't.

With this in mind, there is still one major observation we can take in mind. If we limit witnesses to size $f(n)$ then there are only $2^{f(n)}$ possible witnesses so for small functions $f$ we can simply evaluate each possible witness to see if it works. In other words, by looking only at small enough witnesses, the problem is easy. This means if witnesses to inputs of size $n$ are guaranteed to be $log(n)$ in size, then the original problem can be solved in pseudo-polynomial time, and if the witnesses are guaranteed to be constant size then the original problem can be solved in polynomial time.