Wikipedia:Reference desk/Archives/Mathematics/2011 December 16

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 16

P vs NP and Automated Theorem Proving

Hi, I've read that if P = NP this would make mathematical theorems open to automated theorem programming in a way that would "change" mathematics. However, I've been thinking about that and was wondering how accurate that really was. First, for the algorithm to be NP it would have to search for proofs that are at most f(n) bits, where n is the input size of the theorem. I've heard it phrased that it would be able to find proofs of reasonable length, which fits with the whole f(n) thing, except n and f(n) would be the size of formal proofs. Obviously, definitions in mathematics are layered upon others tracing all the way back to ZFC (the same for theorems), so wouldn't one expect that n would be a lot larger than the the size of the informal statement, thus making this far more impractical? Would the expansion into formal proofs raise the expected degree of f? In other words, informally speaking, if k is the size of an informal statement and g(k) is the equivalent formal one; how does g grow? Related to all of this, since mathematicians can synthesize many layers of formal mathematics into a succinct definition by intuition, wouldn't it be reasonable to expect that many theorems with extremely large formal proofs have reasonable length informal ones? And if we aren't using human intuition, we wouldn't know how to construct a formal system incorporating these new informal concepts? In short, wouldn't it be reasonable to expect that a large chunk of interesting mathematics being done wouldn't be of a "reasonable size" if it were converted into formal statements (how would you be able to decide how large f(n) should be relative n if all of your intuition is with informal proofs?) Finally, when you compound all of this with the possibility that if P = NP that the algorithm might run in O(x ** 4), or bigger, doesn't the idea of machines doing a significant portion of mathematics (if P = NP) become unrealistic? Or did I overlook something obvious? Thank you for any thoughts or answers:-) Phoenixia1177 (talk) 08:56, 16 December 2011 (UTC)

For my last point: it's not just that x ** 4 is fairly slow, but if moving from infomral to formal simply doubles length, then we are looking at 16 x ** 4 time. If it should square it, then we would be looking at x ** 8 time, which is horrible. If the NP = P solution ran in x ** 5, then this gets even worse. And so on. Sorry if that was obvious; also sorry if I sound like I'm ranting and not being clear :-) Phoenixia1177 (talk) 10:52, 16 December 2011 (UTC)

There's certainly no guarantee that some as-yet-unknown polynomial-time solution to an NP-complete problem would necessarily trivialize the finding of mathematical proofs, I agree with you there.

There's something called Cobham's thesis that asserts that the class P is the same as the class of problems with feasible solutions. Taken literally, Cobham's thesis is obviously false, just can't be taken remotely seriously. I assume it's not meant to be taken that literally, and that it's more a sort of observation that problems that arise naturally in practice tend to follow this rule. If that's true, and if the finding of proofs is considered a problem that arises naturally in practice, then one might expect that an automated-theorem-proving system that worked at least much of the time, could be found. --Trovatore (talk) 09:35, 16 December 2011 (UTC)

That makes sense. But, suppose that we had a decent solution for some NP problem, how would the moving from informal to formal proofs effect the speed of that? Wouldn't the inputs grow, and couldn't this imapct the performance so that even a practical 3sat solution might become an impractical proog finder? Even more importantly, how would you gauge what would be an unreasonable upper bounds on proof length if you are dealing with formal proofs? If the algorithm didn't use any type of test cases, it would be impractical to do the algorithm incrasing proof length each time, the same goes for starting out with an extremely large number. I guess, ultimately, even if NP problems are in P and practical, it seems like automated proof finding would remain impractical due to size increases and limits on proof size. Or, is there some nice correspondance between formal statement size and informal statement size (I have no idea, but it seems odd that there would be.) Phoenixia1177 (talk) 10:52, 16 December 2011 (UTC)

Is Gödel's incompleteness theorem really so dire?

Some people insist that Gödel's theorem spells death for a potential theory of everything, but is it really so bad? As far as I can tell, all Gödel's theorem proves is that the Gödel sentence cannot be proven in any axiomatic system, but the Gödel sentence is a pretty stupid sentence - basically just "this statement cannot be proven". To be quite frank, so what if an axiomatic system can't prove that statement? If a theory of everything could prove any statement in physics except for the Gödel sentence, I would be satisfied. Am I missing something? Is it possible in theory for there to be a theory of everything which could prove any statement except the Gödel sentence, or are there more dire consequences of the theorem (or other barriers in the search for a TOE)? Widener (talk) 12:42, 16 December 2011 (UTC)

Gödels theorem says that unprovable sentences exist. The proof of Gödels theorem gives a specific example. You seem to assume that it is the only example. Provability may be a very exclusive property for a sentence. Nonprovability is the rule rather than the exception. Bo Jacoby (talk) 13:28, 16 December 2011 (UTC).

I understand, but is that actually true? Widener (talk) 14:03, 16 December 2011 (UTC)

Yes, that is true. Goedel's theorem is that any (sufficiently complex) set of consistent axioms leads to a system with unprovable statements. So even if you accept what you call "the Goedel sentence" as a new axiom, there will still be other unprovable statements. So nonprovability is unavoidable; even if you disregard certain statements that you think are "pretty stupid sentences". You probably know this, but see continuum hypothesis for an example of a nonprovable statement (in ZFC) which is not stupid at all. Staecker (talk) 16:47, 16 December 2011 (UTC)

Any axiomatic system which contains the Gödel sentence as an axiom is clearly inconsistent. All Gödel's theorem demonstrates is that the Gödel sentence is unprovable; the nonprovability of the continuum hypothesis is not a consequence of Gödel's theorem. So if you don't count the Gödel sentence, you cannot use his theorem to dismiss the otherwise-completeness of any axiomatic system of theory of everything. Widener (talk) 22:10, 16 December 2011 (UTC)

I think you're wrong about that- though I'm not an expert so somebody else should chime in. The Goedel sentence can be used as an axiom without violating any consistency. The statement "this statement is not provable from the other axioms" can be assumed to be true and added into any existing set of axioms and still be consistent. As for "the nonprovability of the continuum hypothesis is not a consequence of Gödel's theorem", you're right about that- I was just giving this as an example of a nonprovable statement that's not trivially self-referential. Staecker (talk) 03:19, 17 December 2011 (UTC)

Can you give an outline of the argument that reaches the conclusion that "Gödel's theorem spells death for a potential theory of everything" - or give a link to a source that explains how one thing leads to the other ? I am not sure I see how that argument might be constructed. Gandalf61 (talk) 13:52, 16 December 2011 (UTC)

Well, it is given in the article theory of everything. Widener (talk) 14:01, 16 December 2011 (UTC)

Oh, I see. Well, the most that Gödel's theorem might tell us in this context is that we can never formally prove that a candidate TOE is actually a TOE i.e. is complete. But a physicist's benchmark is experiment, not formal proof. So when they say "theory of everything" they really mean "theory that explains the results we have observed in all the experiments we have done so far without needing to be fine tuned by picking arbitrary values for too many parameters". I don't think Gödel's theorem rules out that goal. Gandalf61 (talk) 14:20, 16 December 2011 (UTC)

Even more fundamental than that: I understand theory of everything in a physics context to mean something like "theory that explains all fundamental interactions". It doesn't necessarily need to lead to an effective method of predicting what all those interactions add up to, in a mathematical sense.

To put it another (perhaps more aggressive and provocative) way, "theory of everything" really means "theory of everything physical". But mathematics transcends physics, and therefore does not need to be explained by the theory in order for it to be a theory of everything. --Trovatore (talk) 19:37, 16 December 2011 (UTC)

I'm interested in this topic as well, so I thought I'd chime in with what I think is a tolerable summary of everything so far. I assume Staecker is right about being able to add the Goedel statement to the axioms. I would say that a theoretical physicist's benchmark is mathematics, but not to the extent of abstract completeness that would interest a mathematician. The article theory of everything seems to suggest as much - they can agree the incompleteness theorem has implications for a TOE, but doesn't put it out of business, at least not unequivocally so. The biggest question that still remains, I think, is whether Goedel's theorem itself relates to statements other than self-referential ones. There is a list of statements undecidable in ZFC, but these all seem to be abstract. The question is, would there be any that touch a raw nerve in our consciousness? I for one have no personal connection to questions about levels of infinity, but if there were a statement about prime numbers, such as "There are infinitely many primes whose digits add up to 5" which could not be proven one way or the other, I would find that disconcerting. Do any mathematicians have an opinion on whether these statements are all provably true or false, or is that still an open question? IBE (talk) 04:36, 17 December 2011 (UTC)

NB I know the OP's question was really about the TOE, but this would be one of the strongest mathematical ways of answering it. If incompleteness starts to get into the number system, it will run riot through mathematics, and potentially have implications for anything that can be computed. IBE (talk) 05:23, 17 December 2011 (UTC)

As far as we know, the Riemann Hypothesis, Twin Prime Conjecture and P = NP might all be unprovable in ZFC. Unfortunately, since these are all statements of number theory (I believe RH can be reformulated arithmetically, although I'm not sure), proving them undecidable would require constructing non-standard models, and we don't have good ways to do that.--121.74.123.159 (talk) 06:12, 17 December 2011 (UTC)

"...proving them undecidable would require constructing non-standard models" - is there a reason/good reference to explain this in a way a layperson/ordinary graduate could understand? IBE (talk) 06:48, 17 December 2011 (UTC)

These are all statements of arithmetic; they depend only on the natural numbers and the operations plus and times. So in the standard model of arithmetic (the naturals), they have a truth value---either true or false. Creating or destroying subsets of the naturals won't affect them, since they don't talk about subsets of the naturals, only the naturals themselves. To build another model with a different truth value (which is how we show that sentences are independent) would require changing the naturals themselves, which means building nonstandard naturals.--121.74.123.159 (talk) 07:07, 17 December 2011 (UTC)

There is a polynomial in several variables with integer coefficients p so that there is no proof whether, or not, it has an integer valued root. To show this, the solution to Hilbert's Tenth Problem is that there is no algorithm that can decide this for all such p; we can construct a Turing Machine that given p will try all possible proofs of "it has an integer root" and "it does not have an integer root." and stop only if one of the proofs work. If there is a proof for every such p, then this machine must halt for all inputs; however, this would make the tenth problem decidable, thus, some such p must exist for which there is no proof. Clearly, this is not some self referential statement (for whatever that p might be) nor is the actual statement overly artificial (though the statement that some such p exists may be) By the way, what did you mean by, "If incompleteness starts to get into the number system, it will run riot through mathematics, and potentially have implications for anything that can be computed." Incompleteness is already in the number system and computation. Phoenixia1177 (talk) 09:41, 17 December 2011 (UTC)

I was exaggerating a little there. Usually, from what I have seen at any rate, when someone finds a proof of something incomplete in maths, it goes further, and seems to run through the structure of it like gristle (this was from something by Douglas Hofstadter). Perhaps it does in this case, and we haven't found particular polynomials with the property you suggested. At any rate, if you could prove that the twin primes conjecture cannot be proven or disproven within ZFC, I would be expecting this to have a huge knock-on effect. Your example is very strong, and of just the sort I am interested in (thanks for reminding me, as I had forgotten all about it), but less compelling than an explicit example of such a polynomial. IBE (talk) 11:36, 17 December 2011 (UTC)

There is also a generalization of the Collatz Conjecture that is undecidable, this can, again, be converted into a check for proof type of thing that shows that there is some unprovable sentence about a Collatz like function; this sentence would be even more natural than the one about p above. Phoenixia1177 (talk) 09:46, 17 December 2011 (UTC)

As for the original question: Godel's Theorem does not imply that no set of rules exist which encode all physical interactions, though it could imply that there is some possible physical system that the rules cannot decide the outcome of. However, I think most people would consider being able to write down the laws to be providing a TOE, I don't think they would require that the theory also be complete. On a side note, a few things: there are other objections to TOEs; since we could add Godel sentences in as axioms to any incomplete TOE, it is true that there would always be a stronger system, but I think the general idea is that if the theory can account for all of the fundamental interactions, then it is a TOE. Phoenixia1177 (talk) 09:56, 17 December 2011 (UTC)

Something that would be very interesting indeed would be if it were possible to make an actual physical oracle machine] for Turing machine halting. Quantum computing doesn't go anywhere near that, it doesn't look like it can even approach NP problems in P time, but it has shown that the physical world can do some quite strange things. 10:27, 17 December 2011 (UTC)

It may be possible that there is some physical constant that we can measure that is a noncomputable real number; for example, define a binary number b of the form 0.b1b2b3... where bn is 1 iff the nth turing machine halts. However, I don't think it likely we could determine if some constant is this since we could never accurately measure the entire sequence; and any theory that implied that it was such, would only be true to within experimental verification, thus, not 100% guaranteed. Moreover, unless physics is built layer upon layer infinitely, or there is some continuous aspect of it, I doubt that there is any constant that requires infinite precision; so, even if a theory provably yields such a number, I doubt that reality actually yields such a measurement (I would guess that there is some very large number so that we could truncate everything to that many decimals and never be able to physically tell the difference between that and the original system. I think this be could strengthened to saying that telling the difference would be physically impossible, not just for our means. Though the truncated theory would, probably, not be as mathematically nice.) On a side note, there may be other ways of constructing an oracle, or some hitherto unconsidered notion of computable, from physics, but I'm not sure how. In any case, it will still have undecidables; no system is able to decide its own version of the halting problem. So, short answer: probably not; might not even make sense; even if, probably wouldn't be able to prove it; and it wouldn't rule out undecidables in toto. Phoenixia1177 (talk) 10:43, 17 December 2011 (UTC)

I can imagine just putting in the axioms and asking if the Collatz conjecture is true and it coming back with 'yes, I have discovered a truly marvellous proof of this, but the margins of this universe are too small to contain it' ;-) Dmcq (talk) 11:28, 17 December 2011 (UTC)

You've hit upon something that always makes me feel a little weird inside, that the majority of theorems have proofs too big to express even if you used the entire universe as your chalkboard. Heck, even the majority of theorems are too big. Even more sickening, no matter how much we layer our definitions to shrink sentences down to fewer and fewer symbols, we will eventually run out of space in which to write our definitions...ewww:-) I get the same shiver when I think about how all computers are really just finite state machines (this is supposing that we don't have some wacky way of building on to it using the expansion of the universe...) Sorry for the rant:-) Phoenixia1177 (talk) 09:52, 21 December 2011 (UTC)

By the way, we would have an awesome universe if some physics experiment actually cranked that out:-) Phoenixia1177 (talk) 09:54, 21 December 2011 (UTC)

TAOCP Vol 4A page 5

Unsure whether to ask this on maths or IT, decided here better...

In TAOCP Vol 4A there is some stuff about pairs of latin squares. The Euler-Paker method uses "traversals", of which there are 808 in the instance mentioned. I don't undestand what a traversal is. Can anyone elucidate please? -- SGBailey (talk) 14:02, 16 December 2011 (UTC)

A traversal of a latin square is a set of entries, one in each row and column and one of each symbol.←109.145.12.18 (talk) 16:47, 16 December 2011 (UTC)

I quote: "For example, one traversal is 0859734216, in Euler's notation, meaning that we choose the 0 in column 0, the 8 in column 1, ..., the 6 in column 9. Each traversal that includes k in L's leftmost column represents a legitimate way to place the ten k's into square M. The task of finding traversals is, in fact, rather easy, and the given matrix L turns out to have exactly 808 of them;". I understand 109's definition of traversal, but that is the matrix M that this exercise is attempting to determine. Still unsure what Knuth means here. -- SGBailey (talk) 19:26, 16 December 2011 (UTC)

Matrix M in that example is the "rank" or "suit" of the elements of matrix L. From the earlier card example, Matrix L is:

JAKQ

QKAJ

AJQK

KQJA

Then, Matrix M is:

DHSC

SCDH

CSHD

HDCS

Each position in M is an object that is also in the same position in M. So, the top left object in both of them is the JD. Going to the example you are looking at, L has a unique sequence of 0-9 in each row and, separately, a unique sequence of 0-9 in each column. The goal is to match up a unique set of 0-9 per column and per row in M. But, there's a catch. Each shared position, such as the top left position, is a number pair that cannot be repeated. For example, if the top-second from left position in M is a 1, the object at that position becomes 1,1 (a 1 from L and a 1 from M). That is not allowed in the example shown because the left-most position of the second row down has 1,1 (a 1 in L and a 1 in M). That limits the traversals that are valid for the top row of M. -- kainaw™ 21:09, 16 December 2011 (UTC)

Yes I understand all that, but what I don't understand is what is special about wnd where 0859734216 was magiced from. I'm sure there are more than about 80 different possible strings that could fit the top line of 'L', which is where this must go as we have already established that it is the top line that starts with 0. What you have been describing is "the problem", which is well and readily understood. I am having difficultly understanding "the solution". Take the earlier example.

 'L'  'M'
JAKQ D---
QKAJ S---
AJQK C---
KQJA H---

Now in the top line I can put [D][SH][SC][HC], which is DSCH or DHSC - ok, only two possibilities. Are you saying that in the 10*10 example we get limited to only ~80 possibilities rather than the several million my gut is telling me? -- SGBailey (talk) 08:21, 17 December 2011 (UTC)

Yes. The top row is limited to much smaller than your gut is telling you because you cannot repeat a pairing on a position. Using that smaller example of the cards, you cannot use [AC] on the top row aligned with the A because AC is already used on the first position of the third line down. You cannot use [KH] on the next position because it is on the bottom row already. If you think of it as a tree of possibilities where each node is a selection of one item and all the child nodes are selections that could come next, disallowing [AC] prunes a whole branch from the tree. A lot of possibilities are removed. If you ignored this whole pairing thing, the first line of the cards thing would allow for [D][CHS][CHS][CHS], which would be six possibilities instead of just two. -- kainaw™ 16:19, 20 December 2011 (UTC)

integrals

will anyone help me with changing order in double integrals?though i can solve few sums but i am not feeling it,please help refering to an example.59.165.108.89 (talk) 15:02, 16 December 2011 (UTC)

See Order of integration (calculus). Or give a problem you're stuck on. Qwfp (talk) 16:59, 16 December 2011 (UTC)

Exact trajectory of a point in a vector field

For any point in three-dimensional space a corresponding vector field exists such that its components are defined for $x$ as $ax-yz$, $y$ as $b(y-z)+xz$, and $z$ as $xy+cz$. Given an initial starting point $(x_{0},y_{0},z_{0})$, $a$, $b$, and $c$, what would the equations be that would give the exact position of the point at any time as it "flows" through the vector field? --Melab±1 ☎ 21:59, 16 December 2011 (UTC)

I fixed your math tag for you - you were missing the ">" at the end. This looks like a homework question. We have a policy of only helping with homework if you show us that you've at least tried to do it yourself first. How far have you got? --Tango (talk) 22:08, 16 December 2011 (UTC)

It is not a homework problem. --Melab±1 ☎ 00:00, 18 December 2011 (UTC)

The three differential equations: dx/dt=ax−yz, dy/dt=by−bz+xz, dz/dt=cz+xy, are non-linear due to the product terms xy, yz, and xz. The very special case (x,y,z)=(0,0,0) is obviously a solution. Slightly more general cases are: (x₀e^at, 0, 0) and (0, y₀e^bt, 0) and (0, 0, z₀e^ct). While the product terms are negligibly small, the linear approximations are: dx/dt=ax, dy/dt=by−bz, and dz/dt=cz. These equations can be written dX/dt=AX where X=(x,y,z) is the unknown vector and A is the known matrix ((a,0,0),(0,b,−b),(0,0,c)). It has the solution X=X₀e^At. Even if the product terms are not negligible the differential equations can be linearized by substituting (x,y,z) = (x₀,y₀,z₀) + (x',y',z'). But I do not know if the nonlinear equations have elementary exact solutions. Bo Jacoby (talk) 06:25, 18 December 2011 (UTC).

Can you explain how (x,y,z) = (x₀,y₀,z₀) + (x',y',z') linearizes the equations that I gave? I just don't see it. --Melab±1 ☎ 02:16, 19 December 2011 (UTC)

The idea is that even if yz is not small, y'z' is. dx/dt = ax−yz = a(x₀+x')−(y₀+y')(z₀+z') = ax₀+ax'−y₀z₀−y'z₀ −y₀z'−y'z'. So dx'/dt ≈ (ax₀−y₀z₀)+ax'−z₀y'−y₀z'. This approximate equation is linear. The same for the two other equations. Bo Jacoby (talk) 10:25, 19 December 2011 (UTC).

Can you think of any set of 3D non-linear equations that have an exact solution? --Melab±1 ☎ 02:22, 20 December 2011 (UTC)

And how would I calculate the derivative of y and z? --Melab±1 ☎ 02:23, 20 December 2011 (UTC)

Does anyone else have any input? --Melab±1 ☎ 00:19, 21 December 2011 (UTC)

dy'/dt and dz'/dt are calculated exactly like dx'/dt. Substitute y=y₀+y' in the equation for dy/dt. I am puzzled by your asking. Isn't it obvious? Bo Jacoby (talk) 19:31, 21 December 2011 (UTC).

The Twelve Days of Christmas

I wanted to link to this from another site, but the 2 is supposed to be on top of the sigma. Also, I wanted to link from the other site to something that just shows the mathematical formula and not the other stuff.Vchimpanzee · talk · contributions · 22:37, 16 December 2011 (UTC)

To put the 2 on top of the sigma, you need to put curly brackets around the 12 - i.e.

\sum_{j=1}^{12} + \sum_{i=1}^j.

That'll give you: $\sum _{j=1}^{12}+\sum _{i=1}^{j}$

As for the rest of your question, I don't understand what you mean. Do you mean you want to hotlink the image? Smurrayinchester 00:04, 17 December 2011 (UTC)

He obviously wanted $\sum _{j=1}^{12}\sum _{i=1}^{j}i$, which is 364, which is the total number of gifts in The Twelve Days of Christmas (song). [1] --Itinerant1 (talk) 09:23, 17 December 2011 (UTC)

What a nice application of binomial coefficients! $\sum _{j=1}^{12}\sum _{i=1}^{j}i=\sum _{j=1}^{12}\sum _{i=1}^{j}{\binom {i}{1}}=\sum _{j=1}^{12}{\binom {1+j}{1+1}}={\binom {2+12}{2+1}}=364.$ Bo Jacoby (talk) 16:18, 17 December 2011 (UTC).

Regarding linking the image, I wanted to link only the image, not all that goes with it. Thank you.Vchimpanzee · talk · contributions · 16:40, 17 December 2011 (UTC)

Try one of these: http://upload.wikimedia.org/wikipedia/en/math/d/2/8/d2811783303f111aadd797ea7efa4ed9.png or http://upload.wikimedia.org/wikipedia/en/math/9/9/1/991cdcbdfb1b6a32fe994ae843142600.png. I'm not sure how long those links will last- they might be temporary. Staecker (talk) 17:16, 17 December 2011 (UTC)

Thanks. We forgot one important detail so we need to do it again.Vchimpanzee · talk · contributions · 17:50, 17 December 2011 (UTC)

Wait, the first link works. That will do it. Thank you.Vchimpanzee · talk · contributions · 17:51, 17 December 2011 (UTC)

For future reference, all equations on wikipedia are PNG images. Depending on your browser/OS, you can typically right-click on the equation and either save the image to your hard drive or "copy image location" to get the address like the ones above. Staecker (talk) 19:48, 17 December 2011 (UTC)