16,379 reputation
bio website gowers.wordpress.com
visits member for 5 years, 10 months
seen May 22 at 10:59
Mathematics professor at Cambridge

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