bio | website | gowers.wordpress.com |
---|---|---|
location | ||
age | ||
visits | member for | 4 years, 10 months |
seen | Mar 16 at 23:40 | |
stats | profile views | 30,301 |
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 |