bio | website | gowers.wordpress.com |
---|---|---|
location | ||
age | ||
visits | member for | 5 years, 8 months |
seen | May 22 at 10:59 | |
stats | profile views | 32,462 |
Mathematics professor at Cambridge
Nov 2 |
comment |
Are there any interesting examples of random NP-complete problems?
I think that is indeed what I meant (if I understand you correctly). As for my motivation, I just asked it out of curiosity. |
Nov 2 |
comment |
Are there any interesting examples of random NP-complete problems?
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 |
comment |
Are there any interesting examples of random NP-complete problems?
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 29 |
comment |
Minkowski sum of small connected sets
As David Speyer points out, the Minkowski sum is a singleton in this case. My only reason for making this comment is to say that I came up with exactly the same "counterexample" myself at one point, and even started writing an answer based on it. But then I realized my mistake. |