26
$\begingroup$

Here's an example of the kind of thing I mean. Let's consider a random instance of 3-SAT, where you choose enough clauses for the formula to be almost certainly unsatisfiable, but not too many more than that. So now you have a smallish random formula that is unsatisfiable.

Given that formula, you can then ask, for any subset of its clauses, whether that subset gives you a satisfiable formula. That is a random (because it depends on the original random collection of clauses) problem in NP. It also looks as though it ought to be pretty hard. But proving that it is usually NP-complete also seems to be hard, because you don't have the usual freedom to simulate.

So my question is whether there are any results known that say that some randomized problem is NP-complete. (One can invent silly artificial examples like having a randomized part that has no effect on the problem -- hence the word "interesting" in the question.)

Improve this question
$\endgroup$
5
  • $\begingroup$ Can I ask what motivated the question? I think there's some confusion about the "right" way to state the problem, and having some motivation might help... $\endgroup$
    – Harrison Brown
    Commented Nov 1, 2009 at 17:08
  • $\begingroup$ Actually, here's a second attempt at trying to phrase what I think you're asking (for 3SAT) more formally. Please let me know if it's wrong. Let S be a "dense random collection" of 3SAT instances (I think this can be made reasonably precise). Then is there (w/h/p) a poly-time Turing reduction from every language in NP to 3SAT whose image in contained in S? $\endgroup$
    – Harrison Brown
    Commented Nov 1, 2009 at 17:18
  • $\begingroup$ I think that is indeed what I meant (if I understand you correctly). As for my motivation, I just asked it out of curiosity. $\endgroup$
    – gowers
    Commented Nov 2, 2009 at 23:11
  • 1
    $\begingroup$ Isnt it related to Levin's average case complexity issues? I vaguely remember that there were examples which are hard in average case but the examples were not as great as for NP completeness in worse case. $\endgroup$
    – Gil Kalai
    Commented Nov 6, 2009 at 13:17
  • $\begingroup$ I just came across this old paper of Steve Cook: cs.toronto.edu/~sacook/homepage/JACMpvsnp.ps It doesn't say anything directly too useful to the current discussion, but it shows that such questions have been around for a while. $\endgroup$
    – user13370
    Commented Mar 2, 2011 at 21:33

6 Answers 6

Reset to default
28
$\begingroup$

Important update (Oct. 6, 2010): I'm pleased to say that I gave the "random 3SAT" problem in the OP to Allan Sly, and he came up with a simple NP-hardness proof. I've posted the proof to my blog with Allan's kind permission.

Sorry that I'm extraordinarily late to this discussion!

Regarding Tim's specific question: if we stick enough clauses in our instance that every 3SAT instance (satisfiable or not) occurs as a subformula with high probability, then certainly the resulting problem will be NP-hard. Indeed, it would suffice to have a large enough set of clauses that we can always find a subformula that can serve as the output of one of the standard reductions. On the other hand, I don't know of any techniques for proving NP-hardness that are tailored to the setting Tim has in mind -- it's a terrific question!

Since I can't answer the question he asked, let me talk for a while about a question he didn't ask (but that I, and apparently some of the commenters, initially thought he did). Namely, what's known about the general issue of whether there are NP-complete problems that one can show are NP-hard on average (under some natural distribution over instances)?

(1) The short answer is, it's been one of the great unsolved problems of theoretical computer science for the last 35 years! If there were an NP-complete problem that you could prove was as hard on average as it was on the worst case, that would be a huge step toward constructing a cryptosystem that was NP-hard to break, which is one the holy grails of cryptography.

(2) On the other hand, if you're willing go above NP-complete, we know that certain #P-complete problems (like the Permanent over large finite fields) have worst-case/average-case equivalence. That is to say, it's exactly as hard to compute the permanent of a uniform random matrix as it is to compute the permanent of any matrix, and this can be proven via an explicit (randomized) reduction.

(3) Likewise, if you're willing to go below NP-complete, then there are cryptographic problems, such as shortest lattice vector (mentioned by Rune) and discrete logarithm, that are known to have worst-case/average-case equivalence. Indeed, this property is directly related to why such problems are useful for cryptography in the first place! But alas, it's also related to why they're not believed to be NP-complete. Which brings me to...

(4) We do have some negative results, which suggest that worst-case/average-case equivalence for an NP-complete problem will require very new ideas if it's possible at all. (Harrison was alluding to these results, but he overstated the case a little.) In particular, Feigenbaum and Fortnow showed that, if there's an NP-complete problem that's worst-case/average-case equivalent under randomized, nonadaptive reductions, then the polynomial hierarchy collapses. (Their result was later strengthened by Bogdanov and Trevisan.) There are analogous negative results about basing crytographic one-way functions on an NP-complete problem: for example, Akavia, Goldreich, Goldwasser, and Moshkovitz (erratum). At present, though, none of these results rule out the possibility of a problem being NP-complete on average under the most general kind of reductions: namely, randomized adaptive reductions (where you can decide what to feed the oracle based on its answers to the previous queries).

(5) Everything I said above implicitly assumed that, when we say we want an average-case NP-complete problem, we mean with a distribution over instances that's efficiently samplable. (For example, 3SAT with randomly generated clauses would satisfy that condition, as would almost anything else that arises naturally.) If you allow any distribution at all, then there's a "cheating" way to get average-case NP-completeness. This is Levin's universal distribution U, where each instance x occurs with probability proportional to $2^{-K(x)}$, K(x) being the Kolmogorov complexity of x. In particular, for any fixed polynomial-time Turing machine M, the lexicographically-first instance on which M fails will have a short description (I just gave it), and will therefore occur in U with large probability!

(6) If you're willing to fix a polynomial-time algorithm M, then there's a beautiful result of Gutfreund, Shaltiel, and Ta-Shma that gives an efficiently-samplable distribution over NP-complete problem instances that's hard for M, assuming $NP \nsubseteq BPP$. The basic idea here is simple and surprising: you feed M its own code as input, and ask it to find you an instance on which it itself fails! If it succeeds, then M itself acts as your sampler of hard instances, while if it fails, then the instance you just gave it was the hard instance you wanted!

(7) Finally, what about "natural" distributions, like the uniform distribution over all 3SAT instances with n clauses and m~4.3n variables? For those, alas, we generally don't have any formal hardness results.

Improve this answer
$\endgroup$
2
$\begingroup$

I'm not one hundred percent clear if this is what you mean, and even if it is I don't see an obvious way to make it actually work, but it might be of interest anyway.

The Rado graph is "the infinite random graph," and it's known to contain induced copies of every finite graph. (Actually I think that characterizes it -- certainly having countably many vertices and containing induced copies of every countable graph does.) So if you pick a large random graph, with probability 1 it'll contain an induced copy of every small enough graph. Unfortunately "large enough" means "exponential in the size of the random graph," so this isn't actually useful.

I don't know if you can do better than exponential for specific classes of graphs (and I sort of doubt it for any class that's interesting), although if you take a subgraph rather than an induced subgraph it might be easier. There's a famous conjecture of Erdos that says that Ramsey numbers of bounded-degree graphs are linear, but that's considerably stronger than what's needed...

ETA: After giving it some more thought, an n-vertex graph with bounded average degree is a subgraph of a random graph with, say, cn (for some large c depending on the average degree) vertices w/h/p. So in particular, planar graphs are subgraphs of slightly larger random graphs, and 3-colorability is known to be NP-complete even for planar graphs. But I suspect that the important thing is induced subgraphs, which (again) seems much trickier.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Re the Rado graph: "countable and contains induced copies of every countable graph" does not uniquely characterize the Rado graph R. For example, R together with a single isolated vertex has those same properties, but is not isomorphic to R because R is connected (with diameter 2, in fact). The property you need is countable and "for any finite graph G and any vertex v of G, any embedding of G − v as an induced subgraph of R can be extended to an embedding of G into R." $\endgroup$
    – aorq
    Commented Nov 1, 2009 at 23:48
  • 1
    $\begingroup$ You're right, of course. I was working from memory and not thinking too hard about that kind of thing (mostly because it doesn't have direct relevance to the problem). $\endgroup$
    – Harrison Brown
    Commented Nov 2, 2009 at 2:24
2
$\begingroup$

Are you asking about the existence of problems that are hard on average? It is known that the existence of hard on average problems implies P ≠ NP.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Steve, I think this is slightly different, although it's a little confusing; I think what Tim is asking is essentially whether one can embed NP-complete problems into slightly larger random instances. $\endgroup$
    – Harrison Brown
    Commented Oct 31, 2009 at 15:10
  • 1
    $\begingroup$ It's a little bit difficult to say exactly what I mean, which is why I tried to illustrate with an example. What I want is an interesting class of functions in NP such that if you choose a random one then with high probability it is NP-complete. I'm not 100% clear in my mind what counts as interesting though. But Harrison is right -- I am not asking about problems that are hard on average. $\endgroup$
    – gowers
    Commented Oct 31, 2009 at 15:16
  • 1
    $\begingroup$ @gowers - I don't know what you mean by that. A particular instance of a problem can never be NP-complete (or have any complexity class); only a class of problems (or more formally, a "language") can have such properties. So I don't understand "high probability that it is NP-complete"... I think there may be an interesting problem here, but I'm not sure what it is. $\endgroup$
    – Darsh Ranjan
    Commented Oct 31, 2009 at 19:33
  • 1
    $\begingroup$ I'm not asking for an instance of a problem to be NP complete. Let me go back to my example: I choose a random set X of clauses; I define SAT_X to be the problem, "Given Y subset X, are the clauses in Y simultaneously satisfiable?" So that is a problem (as opposed to a problem instance) that depends on X. If X is a random set of clauses that only just fails to be satisfiable, then it seems to me that SAT_X could, with high probability, be NP-complete, but I have no idea how to prove it because it looks hard to simulate a Turing machine if you don't have access to all clauses. $\endgroup$
    – gowers
    Commented Nov 2, 2009 at 23:10
  • $\begingroup$ Okay, I had misinterpreted your question. But I still think there's a problem: SAT_X has only a finite number of instances (one for each subset of X), right? A finite problem space can't be NP-complete. Am I still misinterpreting it? $\endgroup$
    – Darsh Ranjan
    Commented Nov 4, 2009 at 5:47
2
$\begingroup$

A candidate for the most natural average-case complete problem is given in

Andreas Blass and Yuri Gurevich Matrix Transformation is Complete for the Average Case SIAM J. on Computing 24:1, 1995, 3—29.

http://research.microsoft.com/en-us/um/people/gurevich/Opera/97.pdf

Improve this answer
$\endgroup$
1
$\begingroup$

Perhaps you could look at lattice-based problems? Some of them have the interesting feature that the average instance reduces to the worst instance. That is, the average-case hardness is the same as the worse-case hardness.

In particular, this is why they're popular in crypto, since all you have to assume is that the problem is hard in the worst case, as opposed to factoring or discrete log which we assume to be hard on average.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Hmm, I'm wondering now if there's a boring answer, which is to take a problem that is hard on average and randomly restrict it in some natural way to a small class of instances. If that works, then maybe the question is interesting only in particular cases and not as a general question. $\endgroup$
    – gowers
    Commented Nov 2, 2009 at 23:14
1
$\begingroup$

Oh, I just realized something else -- I think you're asking about a slightly weaker version of random self-reducibility for NP-complete problems. (I.e., an NP-complete problem that was randomly self-reducible should satisfy what you're asking about.) But it's known that if there exists an NP-complete problem that is randomly self-reducible, then the polynomial hierarchy collapses to the third level. (As I understand it, this is a consequence of the fact that BPP is contained in the second level of the hierarchy.) But this means that "[taking] a problem that is hard on average and randomly restrict it in some natural way to a small class of instances" would probably not work for k-SAT.

But random reductions to promise problems are known to be able to preserve most of the information contained in the original decision problem. So I think that in part the answer depends on what kinds of problems you're allowing... UNIQUE-SAT is very close to NP-complete -- though not quite there -- but it's a promise problem.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .