bio | website | gowers.wordpress.com |
---|---|---|
location | ||
age | ||
visits | member for | 4 years, 6 months |
seen | Mar 16 at 23:40 | |
stats | profile views | 29,461 |
Mathematics professor at Cambridge
Nov 18 |
comment |
Can infinity shorten proofs a lot?
I'm not sure I count induction either. It seems to me that one is not relying on infinity in a serious way to sum the first million cubes: one is saying, "If it's valid for 1 then it's valid for 2, and if it's valid for 2 then it's valid for 3, and ... and if it's valid for 999999 then it's valid for 1000000." That is a ridiculously long proof, but induction allows one to shorten it by giving a rule for when it's OK to put in the "..." (A more formal way of making the point is that the axiom of infinity isn't part of first-order Peano arithmetic.) |
Nov 17 |
awarded | Critic |
Nov 17 |
awarded | Supporter |
Nov 17 |
comment |
Can infinity shorten proofs a lot?
You can get the inequality quite easily I think. The log of n! is the sum of log m from 1 to n, which is at least the integral from 1 to n of log x, which is nlogn-n. Done. |
Nov 17 |
awarded | Nice Question |
Nov 17 |
awarded | Nice Question |
Nov 17 |
awarded | Student |
Nov 17 |
awarded | Teacher |
Nov 16 |
comment |
Can infinity shorten proofs a lot?
That's a good example, but I think it may already form part of the presentation (when they talk about infinite sets and the work of Cantor). I'll check though. |
Nov 16 |
comment |
Can infinity shorten proofs a lot?
Ultimately what's wanted is a very nice demonstration for the non-mathematician of why infinity is useful even if all you care about is finitary results. |
Nov 16 |
asked | Can infinity shorten proofs a lot? |
Nov 3 |
answered | Memorizing theorems |
Nov 2 |
comment |
Are there any interesting examples of random NP-complete problems?
Hmm, I'm wondering now if there's a boring answer, which is to take a problem that is hard on average and randomly restrict it in some natural way to a small class of instances. If that works, then maybe the question is interesting only in particular cases and not as a general question. |
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 |