15,439 reputation
1188143
bio website gowers.wordpress.com
location
age
visits member for 4 years, 10 months
seen Mar 16 at 23:40
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
31
asked Are there any interesting examples of random NP-complete problems?
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.
Oct
29
answered Bound on cardinality of a union
Oct
25
answered Minkowski sum of small connected sets
Oct
23
answered What are some reasonable-sounding statements that are independent of ZFC?
Oct
21
asked Can anyone give me a good example of two interestingly different ordinary cohomology theories?
Oct
21
answered Do good math jokes exist?
Oct
20
answered Isomorphisms of Banach Spaces
Oct
20
answered Motivating the Laplace transform definition