Timeline for The definition of computational complexity or complexity measure of computing reals
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17, 2014 at 1:24 | comment | added | XL _At_Here_There | There are so many interesting voters having downvoted and closed the question. But I have thought about it for a long time and still think it is not a simple question. What makes me puzzled is that so many persons have misunderstood it. | |
| Nov 4, 2014 at 12:16 | comment | added | XL _At_Here_There | Seemingly, variant definitions of computational complexity of reals and reals function are not equivalent, they are all defined from the researchers' own views. | |
| Nov 3, 2014 at 8:01 | vote | accept | XL _At_Here_There | ||
| Nov 2, 2014 at 1:15 | comment | added | XL _At_Here_There | @EmilJeřábek, or more concretely, computational complexity in Chapter 7 of Weihrauch's book Computable Analysis can be compared with or link to computational complexity in the book by Blum,Smale or classic computational complexity? This is I want to know. | |
| Nov 2, 2014 at 1:09 | comment | added | XL _At_Here_There | @EmilJeřábek, if I think you have misunderstood what I say in the comment at you. the classic computational complexity is about ,say, language or defined in term of language. definition of complexity in approximation is defined in the term of approximation like $\leq \epsilon$, How could the results or problem of the classic computational complexity like $P = NP$ be link to definition of complexity in approximation? I mean translation of interpretation of each other, it has no thing to do with Kolmogorov complexity. | |
| Oct 31, 2014 at 11:16 | comment | added | Emil Jeřábek | I can't make heads or tails of what you are saying. In terms of Kolmogorov complexity, computation of approximations and computation of bits have the same complexity up to an additive constant. | |
| Oct 31, 2014 at 1:30 | comment | added | XL _At_Here_There | @EmilJeřábek, I wonder how to link definition of complexity in approximation to the classic computational complexity. | |
| Oct 31, 2014 at 1:18 | comment | added | XL _At_Here_There | [cont]For example, we know algebraic irrational number can computed by different representations like it's continued fraction or formula in term of modular function, only when we prove all different representations are irrelevant to computational complexity or other complexity measure,can we define the computational complexity or other complexity as the complexity of the algorithm, otherwise we have different complexity of the same computing algorithm for same computed number. That is irrational. | |
| Oct 31, 2014 at 1:03 | comment | added | XL _At_Here_There | The definition is relevant to Kolmogorov complexity,since the precondition of the definition requires that the length of the program or the description of the Turing Machine is finite. If we don't require such a precondition,every number is computable. so, we have to have some requirements on the length of the finite program or $TM$, since there are variant length of programs or algorithms to compute the same number .Comparing this with the approximation definition, we know we have to have requirements on the length of the approximation algorithm or length of representation [to be cont] | |
| Oct 30, 2014 at 17:21 | comment | added | Emil Jeřábek | To add to Timothy Chow’s comment: I believe that for typical numbers known to be efficiently approximable (e.g., numbers expressible using elementary functions and polynomial roots), we expect bits of the number can be computed in asymptotically the same time bound, as stretches of 1’s can’t get overwhelmingly long. The problem is that apart from a handful of simple cases, we don’t know how to prove that. So in a sense, the distinction doesn’t affect much algorithmic complexity per se, but rather the difficulty of analyzing the algorithms, which may be one reason to avoid XL’s definition. | |
| Oct 30, 2014 at 15:25 | comment | added | Timothy Chow | Yes. Many people's first instinct is to use XL's definition, but it has rather nasty properties. For example, even to show that $\pi$ is computable is difficult with XL's definition, because you have to prove a computable bound on the length of a stretch of 1's, and that requires some nontrivial diophantine analysis. In contrast, approximating $\pi$ to within $\epsilon$ is a much easier problem. So that is the definition that is usually used, and there are many results about that; Weihrauch's book is a fine reference. However, if XL really wants $i$ bits, then much less is known. | |
| Oct 30, 2014 at 8:31 | history | edited | Bjørn Kjos-Hanssen | CC BY-SA 3.0 |
deleted 7 characters in body
|
| Oct 30, 2014 at 8:23 | history | answered | Bjørn Kjos-Hanssen | CC BY-SA 3.0 |