Timeline for Database of integer edge lengths that can form tetrahedrons
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 2, 2017 at 6:02 | comment | added | Peter Heinig | , which is a polynomial of total degree 6.) One can still dream of some completely different algorithm which (0) is provably correct, and (1) decides in merely $O(a)$ steps whether the given $v$ is 'tetrahedral'. I doubt that there is such an algorithm, but do not know how to prove that. | |
| Oct 2, 2017 at 6:02 | comment | added | Peter Heinig | [...] if one ignores the specific structure of the Cayley-Menger-determinant $d$, and if one calculates $d$ via some variant of Gaussian elimination, then while the latter of couse 'runs' in 'constant time' (as this is a $5\times 5$ determinant), the running-time nevertheless becomes 'bicubic in the number of digits of the input $v$', i.e. becomes proportional to $a^6$. (To see why, one might e.g. simply look at the fully expanded explicit form of the Cayley-Menger determinant to be found on p. 164 of [Wirth-Dreiding]. | |
| Oct 2, 2017 at 6:01 | comment | added | Peter Heinig | [..] the number of 'steps' it will take a human being to perform all $\approx10^2$ determinant calculations needed to check j.c.'s and Stefan Kohl's findings. Also: one can still dream of the existence of a faster, as-yet-unknown algorithm which would (0) be provably correct and (1) make it possible to decide, given a vector $v\in \omega^6$, in time linear in the total number of decimal digits in $v$ whether $v$ is tetrahedral. If $a$ denotes the number of all decimal digits in $v$, and [...] | |
| Oct 2, 2017 at 5:32 | comment | added | Peter Heinig | @IgorRivin: thanks for pointing out. I was (quite consciously though) using the term 'complexity' not in its technical sense. Explicitly: in a sense I was using 'complexity' wrongly. (Because here there isn't any any infinite formal language relevant to the problem, *at least not on the face of it. If one varies the definition of the 'language', though, there might be. But it seems better no to get into this (until I'm sure that there is a point to it). I was using 'complexity' in the ordinary sense of, roughly [..] | |
| Oct 1, 2017 at 21:28 | comment | added | Igor Rivin | @PeterHeinig Complexity? This is a $4\times4$ symmetric matrix. Otherwise, no one computes determinants in practice using the $O(n!)$ algorithm (though for $4\times 4$ that is probably not so bad). | |
| Oct 1, 2017 at 20:20 | comment | added | Peter Heinig | [..] language. Exact arithmetic might make it unproblematic though. My understanding is that determinant calculations are problematic if they are of the form (floating-point-entries)$\mapsto$(floating-point result), but if input is integer matrix, exactly/virtually/formally represented on machine, then numerics are not really a difficulty of the present problem. In summary, the warning about determinants is valuable in practice (many a contributor may blissfully trust the first determinant-routine they used), but numerics is not really an issue here (while complexity is). | |
| Oct 1, 2017 at 20:17 | comment | added | Peter Heinig | The comment about the numerical difficulties of computing determinants is very relevant and valuable, at least for those who would simply use whatever determinant-routine that is at hand. 'The' reason for the instability are, needless to say, the $n!$ alternating summands if Leibniz's formula is used, and also if Gaussian elimination is used it remains problematic. Basic things to point out: even for problems where only a 'boolean truth-value' of the form 'is-the-determinant-positive' is required, this remains problematic. One should be careful to know what algorithm is used by what [...] | |
| Oct 1, 2017 at 18:57 | history | answered | Joseph Malkevitch | CC BY-SA 3.0 |