bio | website | gowers.wordpress.com |
---|---|---|

location | ||

age | ||

visits | member for | 5 years, 2 months |

seen | Mar 16 at 23:40 | |

stats | profile views | 31,039 |

Mathematics professor at Cambridge

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