![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoySo I went and talked to Lagarias. Basically he told me two things:
1. I should start writing up our work immediately.
2. I should go look up the connection to P-vs-NP for Blum-Shub-Smale machines.
As for the latter, I'm not so certain that there really is such a connection? What Lagarias described was a bit different - straight line computations - which, well, are computations, so once you make a number you can use it again freely. Allows you to make much larger numbers - more like 2^2^n instead of 3^(n/3). To that, he said, well, it's some sort of complexity measure of some sort of computation, so you should at least note that. :P In any case, well, I suppose I should actually go look it up.
As for the former - well, he also gave me an additional reason to write it up quickly: He's going on sabbatical soon, and no, he's not going to be willing to look at it then. So I've written up a... not really an actual draft, more like a sketch. Lots of stuff is omitted; notation is used inconsistently (is A_k defined with a strict or nonstrict inequality? Does N include 0 or not?); I haven't included any actual references, just "Selfridge showed such-and-such", "Rawsthorne showed such-and-such", "Arias conjectured such-and-such"; but I think it should be good enough for a "give me the basic ideas" document.
No, I'm not going to post it on the web or anything. Like I said... it's really sketchy. Note, for instance, that Josh told me Glenn and Rohrlich said they'd take a look at what we had - but I don't think we're really under any time constraint when it comes to showing it to them. So may as well actually flesh it out a bit first.
But hey! I have something written! That's progress!
(Yeah, I couldn't make the "small intersection" idea work. I'll have to send Josh my thoughts on it, see if he can make any more sense of it...)
-Harry
1. I should start writing up our work immediately.
2. I should go look up the connection to P-vs-NP for Blum-Shub-Smale machines.
As for the latter, I'm not so certain that there really is such a connection? What Lagarias described was a bit different - straight line computations - which, well, are computations, so once you make a number you can use it again freely. Allows you to make much larger numbers - more like 2^2^n instead of 3^(n/3). To that, he said, well, it's some sort of complexity measure of some sort of computation, so you should at least note that. :P In any case, well, I suppose I should actually go look it up.
As for the former - well, he also gave me an additional reason to write it up quickly: He's going on sabbatical soon, and no, he's not going to be willing to look at it then. So I've written up a... not really an actual draft, more like a sketch. Lots of stuff is omitted; notation is used inconsistently (is A_k defined with a strict or nonstrict inequality? Does N include 0 or not?); I haven't included any actual references, just "Selfridge showed such-and-such", "Rawsthorne showed such-and-such", "Arias conjectured such-and-such"; but I think it should be good enough for a "give me the basic ideas" document.
No, I'm not going to post it on the web or anything. Like I said... it's really sketchy. Note, for instance, that Josh told me Glenn and Rohrlich said they'd take a look at what we had - but I don't think we're really under any time constraint when it comes to showing it to them. So may as well actually flesh it out a bit first.
But hey! I have something written! That's progress!
(Yeah, I couldn't make the "small intersection" idea work. I'll have to send Josh my thoughts on it, see if he can make any more sense of it...)
-Harry
no subject
Date: 2012-03-12 07:59 pm (UTC)Really the interesting question about of Blum et al about the other type of Complexity does not pass to our complexity.
Really this other complexity is very interesting but much more difficult to compute to get "nice conjectures".
The idea of these authors of how to factorize numbers if his complexity is "good" for n! is really very interesting.
To entertain I have put to read the entries on complexity using your integer complexity tags.
I wonder if these comments out of time are also received.
Juan
no subject
Date: 2012-03-13 06:08 pm (UTC)L. Blum, F. Cucker, M. Shub, S. Smale, "Complexity and Real Computation",
Springer, New York, 1998.
The interesting part is Chapter 7:
"Algebraic Settings for the problem P != NP"
They denote by tau(n) his "complexity". Then pose the problem (p. 126):
Is there a constant c such that
tau(k!) <= (log k)^c for all k in Z^+ ?
And explain how a positive answer implies that we may factorize natural
numbers in polynomial time.
This appear to be very interesting.
However, unfortunately this does not extends to "our" complexity. \:-<