Welcome to Math Overflow

Question

9

4

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

flag	asked Oct 31 at 10:52 gowers 3,019●2●31

	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... – Harrison Brown Nov 1 at 17:08
	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? – Harrison Brown Nov 1 at 17:18
	I think that is indeed what I meant (if I understand you correctly). As for my motivation, I just asked it out of curiosity. – gowers Nov 2 at 23:11
	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. – Gil Kalai Nov 6 at 13:17

Harrison Brown · Answer 1 · 2009-10-31 11:46:19Z UTC

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.

Steve Flammia · Answer 2 · 2009-10-31 14:53:57Z UTC

1

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.

answered Oct 31 at 14:53

Steve Flammia
894●2●16

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. – Harrison Brown Oct 31 at 15:10

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. – gowers Oct 31 at 15:16

1

@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. – Darsh Ranjan Oct 31 at 19:33

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. – gowers Nov 2 at 23:10

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? – Darsh Ranjan Nov 4 at 5:47

Rune · Answer 3 · 2009-11-01 13:45:04Z UTC

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.

Harrison Brown · Answer 4 · 2009-11-03 12:20:00Z UTC

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.

Gil Kalai · Answer 5 · 2009-11-06 19:14:13Z UTC

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

Steve Huntsman · Answer 6 · 2009-11-03 22:11:02Z UTC

"computation for the Ising model with coupling constants –1, 0, and 1 is NP-complete."

From "The Ising Model Is NP-Complete" by Barry Cipra, available at

http://docs.google.com/gview?a=v&q=cache:hyj83zFYNBkJ:www.cs.brown.edu/~sorin/lab/media/ising_model_np_complete.pdf+%22ising+model%22+%22np+complete%22&hl=en&gl=us&pid=bl&srcid=ADGEESiBwCWSQ7i_wvG1e8FARDbQb9LvGFvnIfmPKwhnT7zwTXzMPNw1HqZRmSyJwjn1-Uo_q4LEjWFbMogE0cp5AGoZYtRQKD4nLxxptPjtQ5ibq41a7lNSMhLXZ_Zb_T-948GXv_Kk&sig=AFQjCNGtov5zizJ2GZ2x_YbHiwqwcR-9Ig

Are there any interesting examples of random NP-complete problems?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

6 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.