tag:blogger.com,1999:blog-3722233.post7928080482644614795..comments2023-12-08T07:21:29.882-06:00Comments on Computational Complexity: A Metric Group ProductLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-3722233.post-89901109711259412022018-07-09T20:07:06.738-05:002018-07-09T20:07:06.738-05:00It seems that this problem has actually been solve...It seems that this problem has actually been solved! https://mathoverflow.net/questions/16214/is-there-an-associative-metric-on-the-non-negative-realsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42400222646620642142016-01-06T14:01:52.777-06:002016-01-06T14:01:52.777-06:00oh wait. I have misread it. It is existential inst...oh wait. I have misread it. It is existential instead of universal (i.e., "there exists x" rather than "for all x"). Cool. Initially I was really confused at how an Abelian Group with 0 as an identity and satisfy f(a,b) <= f(a,c) + f(c,b) can result in satisfying "for all x every other number has a distance from x that is unique". <br /><br />Everything makes sense now. <br /><br />Thanks for the interesting problem by the way. I'll work on it when I'm bored.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11314967949014370882016-01-06T11:04:15.332-06:002016-01-06T11:04:15.332-06:00Hi. Can you enlighten me regarding this sentence?
...Hi. Can you enlighten me regarding this sentence?<br /><br />>One really bizarre thing about this supposed function is that, what this metric does is essentially guarantee that, given some number x, every other number has a distance from x that is unique -- no other number is exactly that distance away!<br /><br />Say for example x is 10, both f(11,x) and f(9,x) would give the same value suppose f is the distance function d(a,b) = |a-b|. So can you elaborate on why the metric essentially guarantees that for any x, every other number has a distance from x that is unique? (apparently in this case 11 and 9 has a distance from 10 that is not unique)<br /><br />Thank you.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54036489557948512502015-06-26T16:33:36.657-05:002015-06-26T16:33:36.657-05:00Integers correspond to finite binary strings, wher...Integers correspond to finite binary strings, whereas the proposed metric uses the representation of real numbers as infinite binary stringsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39382892712337752102015-06-26T02:12:13.804-05:002015-06-26T02:12:13.804-05:00Please correct me if I am wrong; I have no math de...Please correct me if I am wrong; I have no math degree.<br /><br />Given that any binary format can be thought of as the integers in base 2 to utilize the XOR function (or any function that work strictly on a binary format) you would have to find a bijection from the reals to the integers.Anonymoushttps://www.blogger.com/profile/03934791315635029300noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11373705824965858252015-06-19T14:20:24.324-05:002015-06-19T14:20:24.324-05:00I think it was pointed out (somewhere) at some poi...I think it was pointed out (somewhere) at some point that the "xor" definition of d does work for the nonnegative integers. This extends to the set of rational numbers with denominators a power of 2. The nice thing about this set is that it's very similar to the nonnegative reals wrt addition and the usual order (which are mentioned in the metric axioms). The similarity is the sense that they satisfy a lot of the same first-order properties wrt these operations.<br /><br />So we have a model of these axioms which also looks an awful lot like the nonnegative reals from a first-order perspective. This suggests looking at an approach to proving the existence of such a metric/group-operation which goes through the compactness theorem of model theory. I am not very familiar with the area, but a friend of mine who is more familiar (but still not an expert) pieced together an argument that seems to work for this; it seems to be mostly standard model theory techniques when applying the compactness theorem. But the basic idea is to include enough statements to ensure that the model resulting from the compactness theorem contains a copy of the nonnegative reals, and then use the existence of the countable model to satisfy the conditions of the compactness theorem. It's possible also that some higher machinery (using Lowenheim-Skolem and the notion of categoricity) might also suffice to prove this; I don't know. But I am fairly convinced that such an object does exist. Consulting a model theorist would yield a more conclusive answer.Andrew Morganhttp://cs.wisc.edu/~amorgan/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64666081985028802462015-06-15T14:39:34.010-05:002015-06-15T14:39:34.010-05:00previous anonymous: f(a, b) = |a - b| doesn't ...previous anonymous: f(a, b) = |a - b| doesn't work since it is not associative. For instance, |1 - |2 - 3|| = 0 but ||1 - 2| - 3| = 2.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61711880948941117792015-06-15T13:55:00.128-05:002015-06-15T13:55:00.128-05:00Anonymous 1:21 -- no it doesn't, your f is not...Anonymous 1:21 -- no it doesn't, your f is not associative and so doesn't form a group.<br /><br />f(f(1,2), 3) = 2 but f(1, f(2, 3)) = 0.DaveMBhttps://www.blogger.com/profile/00779581893863396042noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12836688849755874282015-06-15T13:21:13.246-05:002015-06-15T13:21:13.246-05:00If f(a,b) = |a - b| then it satisfies both group...If f(a,b) = |a - b| then it satisfies both group axioms and metric axioms. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66791946397199877852015-06-14T20:14:53.845-05:002015-06-14T20:14:53.845-05:00Oops, sorry, that should be f(g^{-1}(1/3), g^{-1}(...Oops, sorry, that should be f(g^{-1}(1/3), g^{-1}(2/3)) = g^{-1}(.111111) = \infty.<br /><br />Also, if all that the squashing function has to satisfy is that it's strictly increasing, then hyperbolic tangent would also work.Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47910012488983328822015-06-13T17:57:54.672-05:002015-06-13T17:57:54.672-05:00The problem seems to be when the XOR "overflo...The problem seems to be when the XOR "overflows". Would this work if the XOR was always <= 1?<br /><br />What if you "smush" [0,Inf) down to [0,1), do the XOR, then expand back to [0,Inf)? E.g., let g(x) = tan^{-1}(x) / (pi/2), and<br /><br />f(a,b) = g^{-1}(g(a) XOR g(b))<br /><br />Most things seem to work, but I'm not sure about the triangle inequality. It may involve trig...<br /><br />Also, as in other peoples' counterexamples, f(g^{-1}(1/3), g^{-1}(2/3)) = f(.111111) = Inf, which is maybe a bit odd, but still OK. I guess f(Inv,Inv) = 0, which makes some sense.<br /><br />So I'm not sure if this works.Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16180189202840160542015-06-12T15:21:18.325-05:002015-06-12T15:21:18.325-05:00I actually like your counter example better, becau...I actually like your counter example better, because it is simpler and uses associativity directly. Itmanhttps://www.blogger.com/profile/06504303746901639466noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64732240135623694552015-06-12T14:44:36.336-05:002015-06-12T14:44:36.336-05:00Oh, sorry! I just found out that someone had alrea...Oh, sorry! I just found out that someone had already pointed out exactly the same counter example!Shahabhttps://www.blogger.com/profile/15635159089551928063noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58542161579322272932015-06-12T14:42:32.029-05:002015-06-12T14:42:32.029-05:00Similarly, and more simply, f(f(1/3,2/3),1)=0 whil...Similarly, and more simply, f(f(1/3,2/3),1)=0 while f(1/3,f(2/3,1))=2 according to the definition of f.Shahabhttps://www.blogger.com/profile/15635159089551928063noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25578028751533863642015-06-12T12:56:28.578-05:002015-06-12T12:56:28.578-05:00I meant the first expression yields 3 and the seco...I meant the first expression yields 3 and the second case 2.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18630518528899172102015-06-12T12:33:02.494-05:002015-06-12T12:33:02.494-05:00I talked with Dylan about the comments and the XOR...I talked with Dylan about the comments and the XOR functions doesn't work. Consider f(f(1/3,5/3),f(2/3,1/3)) vs f(f(1/3,f(5/3,2/3)),1/3). With XOR the first case outputs 2 and the second case outputs 1. At this time we don't know whether there is any function that is both a group and a metric over the non-negative reals.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75046720021883785422015-06-11T17:01:22.814-05:002015-06-11T17:01:22.814-05:00Actually a correction on non-uniqueness of represe...Actually a correction on non-uniqueness of representation. It may be problematic.<br /><br />One can always consider a canonical one. In this representation, digit i is equal to (x << i) & 1.<br /><br />Each number has one such representation. It doesn't give number that end on 0111.... clearly. If you XOR numbers and don't get a number ending on 01111 .... we are obviously fine<br /><br />Let's check one corner case when you may get the infinite sequence 01111:<br /><br />(.0101... XOR a) + (.1010... XOR a) compare with .1111111111 (equal to 1)<br /><br />as you can see the left part will be also .111111111 in this case. So, the triangle inequality holds.<br /><br />The other corner case is (a <= 1):<br />(.0101... XOR .1010...) + (.0101 XOR a) compare with a.<br /><br />The left part will be at least 1, so, again, the inequality holds.<br /><br />When I consider a corner case, I consider two specific numbers. However, without a loss of generality, it can be replaced with any pair where the second number is obtained by bit negation of the first number.Itmanhttps://www.blogger.com/profile/06504303746901639466noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20243282799064480232015-06-11T15:31:01.217-05:002015-06-11T15:31:01.217-05:00How do you deal with 0.1111.... (binary)? Is it th...How do you deal with 0.1111.... (binary)? Is it the same as 1?<br />What is the result of 0.111.... ^ 1(binary)?<br />How do you compare the result of (1/3 ^ 2/3) ^ 1 and 1/3 ^ (2/3 ^ 1) (decimal)?Anonymoushttps://www.blogger.com/profile/17022058893901417305noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61314102625888164522015-06-11T15:23:01.285-05:002015-06-11T15:23:01.285-05:00Real numbers can have more than one binary expansi...Real numbers can have more than one binary expansion (eg 1.00... is also 0.111...) so you should fix a canonical expansion (this also gives rose to an infinite family of functions f)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17650974221628838292015-06-11T12:49:30.927-05:002015-06-11T12:49:30.927-05:00Fixed the typo. Thanks.Fixed the typo. Thanks.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20264763557628706602015-06-11T12:27:34.360-05:002015-06-11T12:27:34.360-05:00You mean a function from (R times R) to R, of cour...You mean a function from (R times R) to R, of course.<br /><br />The next question is whether there are any other examples...DaveMBhttps://www.blogger.com/profile/00779581893863396042noreply@blogger.com