3
$\begingroup$

In practice, it seems that many NP-hard problems "usually" lead to easy instances, in the sense that a commercial solver can handle them reasonably. A few past questions on this topic (see here and here) have been answered by saying they are not well-posed

Here's a shot at a asking a question which might have a non-trivial answer:

Suppose $P \neq NP$ (or assume something stronger like ETH). For each $n$, let $S_n$ be a set of 3SAT instances of size $n$. Additionally, suppose the the number of positive instances and negative instances in $S_n$ is equal. What is the maximum growth rate $|S_n|$ can have while the language $\bigcup_n S_n$ is still polynomial time decidable.

Is this version of the question also trivial? If not, what work has been done on it?

Another question: What other ways of formalizing easy/hard instances are available, and what progress has been made on analyzing them?

$\endgroup$
4
  • 1
    $\begingroup$ By fixing the first couple of clauses (just the first, if you allow the same variable twice in a clause), you can create a SAT instance that is unsatisfiable, independent of the remainder of the formula. So, if we define $S_n$ to contain half the instances of this type and the other half arbitrary positive instances, the language is decidable in linear time. (or maybe even constant, depending on the input model) This means $|S_n|$ can be as large as either a constant fraction of the total number of instances or the number of positive instances (whichever is smaller). $\endgroup$
    – Discrete lizard
    Commented Jan 8 at 21:54
  • 1
    $\begingroup$ So, depending on what you mean by "growth rate", this does not look like a very interesting formalization. The problem, at first glance, seems to be that this size depends too much on the somewhat arbitrary boundaries of the problem (for instance, you can define "non-trivial SAT" as the problem without the "easy" false cases, but then of course someone might come up with another construction...) Is there a way to fix this? That is a good question. $\endgroup$
    – Discrete lizard
    Commented Jan 8 at 21:59
  • $\begingroup$ Assuming ETH is true, any superpolynomial function would suffice. I expect if it is still polynomial time decidable for any superpolynomially quickly growing sequence of sets $|S_n|$, ETH is false. $\endgroup$
    – rus9384
    Commented Jan 9 at 7:59
  • $\begingroup$ See also The SAT Phase Transition by Gent and Walsh (presented at the 11th European Conference on Artificial Intelligence). $\endgroup$
    – Pål GD
    Commented Jan 9 at 10:10

1 Answer 1

3
$\begingroup$

Unfortunately, I don't think this way of formalizing the problem is going to lead to much insight.

The practical experience you are referring to has to be a consequence of something about the distribution of instances seen in practice: that "not-too-hard" instances are common in practice, in the settings where commercial solvers often work. I don't know how to formalize that, as it seems dependent in non-trivial ways on those particular application settings.

For your specific problem, under reasonable assumptions, the maximum growth rate is basically polynomial. If $|S_n|$ grows polynomially quickly, then the promise problem can be solved in polynomial time, in non-uniform models of complexity (e.g., P/poly).

Conversely, we can generate sets $|S_n|$ that grow a bit faster than polynomial, and where heuristically we do not expect any way to solve it in polynomial time. Consider the problem of breaking cryptography, and specifically, recovering the key to a block cipher given a few random known-plaintext pairs. Concretely, each positive instance is obtained by randomly picking a key $k$ and random values $x_1,\dots,x_m$, letting $y_i=E_k(x_i)$, and then creating a 3SAT formula $\varphi(t)$ that evaluates to true if $E_t(x_i)=y_i$ for all $i$, i.e., if $t$ is a key that encrypts each $x_i$ to $y_i$. (This can be done by applying the Tseitin transform to the boolean circuit that tests if $t$ is the desired key.) Each negative instance is obtained by picking random values $x_1,\dots,x_m,y_1,\dots,y_m$, and creating a 3SAT formula $\varphi(t)$ that evaluates to true if $E_t(x_i)=y_i$ for all $i$. We know that all the positive instances are satisfiable. Heuristically, the negative instances are all unsatisfiable. Moreover, under standard cryptographic assumptions (that the block cipher $E$ is secure), no polynomial-time algorithm can distinguish between positive vs negative instances with non-negligible advantage. (Roughly speaking, no polynomial-time algorithm can do better than random guessing.) Therefore, if you define $S_n$ by sampling some super-polynomial number of positive instances and some super-polynomial number of negative instances, no polynomial-time algorithm will decide this promise problem with good probability (any such algorithm could be turned into an attack on the block cipher that is faster than exhaustive keysearch).

In other words, $|S_n|$ only needs to grow slightly faster than polynomial, and the problem can already be hard.

This argument relies on the assumption that we have blockciphers where there is no attack faster than exhaustive keysearch. That is not proven; it is a conjecture. But based on our experience with cryptography so far, it seems like a pretty plausible guess. In any case, it means that for a solver to do well on all problem subclasses where $|S_n|$ grows even slightly faster than superpolynomial, would represent a major advance in attacking block ciphers. So we shouldn't reasonably expect existing solvers to achieve such a level of performance.

$\endgroup$
2
  • 2
    $\begingroup$ Great answer! It seems my attempt has joined the graveyard of the others. Do you know of any formalizations of instance easiness/hardness that do lead to interesting problems? $\endgroup$ Commented Jan 8 at 22:21
  • 2
    $\begingroup$ @DavisYoshida, no, but I am not an expert on this topic. I understand there is a line of research in the SAT community trying to find plausible explanations/formalizations. I think it started with random k-SAT, but that probably isn't a fantastic model; and then others tried to find better models. Unfortunately I am not well acquainted with the research in that direction. $\endgroup$
    – D.W.
    Commented Jan 9 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.