Timeline for Are there any interesting examples of random NP-complete problems?
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 4, 2009 at 5:47 | comment | added | Darsh Ranjan | 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? | |
| Nov 2, 2009 at 23:10 | comment | added | gowers | 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. | |
| Oct 31, 2009 at 19:33 | comment | added | Darsh Ranjan | @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. | |
| Oct 31, 2009 at 15:16 | comment | added | gowers | 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. | |
| Oct 31, 2009 at 15:10 | comment | added | Harrison Brown | 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. | |
| Oct 31, 2009 at 14:53 | history | answered | Steve Flammia | CC BY-SA 2.5 |