Return to Answer

Post Timeline

Commonmark migration

Source Link

edited Jun 16, 2020 at 10:30

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

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.

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.

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.

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.

Source Link

answered Sep 24, 2016 at 17:11

D.W. ♦

169.3k
23
236
520

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.

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.