Timeline for Bounds for constructing $n!$ with additions, subtractions, and multiplications starting from $1$
Current License: CC BY-SA 3.0
39 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Feb 9, 2015 at 15:53 | comment | added | joro | @EmilJeřábek From complexity point of view, is computing multiple of factorial as powerful as computing factorial? IIRC sub-exponential SAT solver might cause troubles. | |
| S Feb 4, 2015 at 8:26 | history | bounty ended | joro | ||
| S Feb 4, 2015 at 8:26 | history | notice removed | joro | ||
| Feb 3, 2015 at 17:09 | comment | added | joro | @EmilJeřábek OK, thanks. Experimentally multiples appear better for me. | |
| Feb 3, 2015 at 16:22 | comment | added | Emil Jeřábek | Bürgisser math-www.uni-paderborn.de/agpb/work/6dich.pdf gives a refinement of the cited result of [BCSS97]: $\mathrm P_{\mathbb C}\ne\mathrm{NP}_{\mathbb C}$ already follows if $t(n!)$ is not polylogarithmically bounded, multiples of $n!$ are not needed here. | |
| Feb 3, 2015 at 16:03 | history | edited | joro | CC BY-SA 3.0 |
Added bounds for t(a n!) for nonzero a.
|
| Feb 3, 2015 at 10:17 | answer | added | joro | timeline score: 0 | |
| Jan 31, 2015 at 19:54 | answer | added | Michael Stoll | timeline score: 4 | |
| Jan 31, 2015 at 6:55 | answer | added | Noam D. Elkies | timeline score: 12 | |
| Jan 30, 2015 at 19:13 | answer | added | Turbo | timeline score: 5 | |
| Jan 28, 2015 at 17:44 | comment | added | user40023 | @GerhardPaseman OK, now I see that arithmetic formulas measure a different type of complexity respect to that in the question. | |
| Jan 28, 2015 at 16:58 | comment | added | Gerhard Paseman | In the Gnang et. al. paper cited by Fry, the complexity used there is similar to the term complexity using a certain algebraic method of computation. The BCSS model (if I recall correctly) does not use term-complexity, but instead allows subterms to be reused without cost, offering a measure which in general is much smaller than that in the Gnang paper. Thus Gnang's lower bounds do not apply. As an example, $t(2^{2^n})$ is close to $n$ (using one plus and no minus), which is smaller than Gnang's measure of order $O(2^n)$. Gerhard "Ask Me About Small Computing" Paseman, 2015.01.28 | |
| Jan 28, 2015 at 11:39 | comment | added | joro | @Fry I haven't seen the original paper, but my interpretation based on Lipton's blog (check Emil's link): Start from 1 and construct a set of number S. You can use any number from S, e.g: (1+1)*2. Your link doesn't allow 2 in this example. | |
| Jan 28, 2015 at 11:34 | comment | added | user40023 | @joro Please, explain. In your question I read "the minimum number of additions, subtractions, and multiplications needed to construct n, starting from 1". On the other hand, if one can start from arbitrary numbers, then just start from $n!$ and the problem is trivial: $0$ operations are required. Clearly you means something else but I do not understand. | |
| Jan 28, 2015 at 11:17 | comment | added | joro | @Fry The problem with only 1 is different from the question. It allows arbitrary numbers not only 1. | |
| Jan 28, 2015 at 10:23 | comment | added | user40023 | @joro In Gnang, Radziwill, Sanna - Counting arithmetic formulas (arxiv.org/abs/1406.1704) the authors proved (Theorem 1.4) that for almost all positive integers $n$ the number of 1's, additions and multiplications (no subtractions) needed to write an arithmetic formula evaluating to $n$ is greater than $C \log n$, for some constant $C > 0$. Therefore, if the factorial $n!$ has nothing special (which I doubt is the case) it requires at least $C n \log n$ arithmetic operations to be computed. | |
| S Jan 28, 2015 at 7:58 | history | bounty started | joro | ||
| S Jan 28, 2015 at 7:58 | history | notice added | joro | Draw attention | |
| Jan 28, 2015 at 7:56 | history | edited | joro | CC BY-SA 3.0 |
Bounds, not just lower
|
| Jan 27, 2015 at 21:23 | answer | added | Gerhard Paseman | timeline score: 4 | |
| Jan 27, 2015 at 14:07 | history | edited | joro | CC BY-SA 3.0 |
Comment from Gerhard "Wants To See Better Bounds" Paseman
|
| Jan 26, 2015 at 22:30 | comment | added | Gerhard Paseman | I'd like to add that a similar sounding problem mathoverflow.net/a/75792/3206 using additions and multiplications has easy lower and upper bounds of O(log n). The computation model for this problem is different from the above problem, as "repeated subterms" do not add to the complexity of the computation, to state the matter (from memory) roughly. Gerhard "Wants To See Better Bounds" Paseman, 2015.01.26 | |
| Jan 26, 2015 at 13:14 | history | edited | joro | CC BY-SA 3.0 |
Added bound
|
| Jan 25, 2015 at 14:10 | comment | added | joro | @EmilJeřábek I see, missed that, the algorithm is practical. Is it within reach to show that implementation on current hardware can't efficiently compute factorial? From experience basic operations on numbers taking tens of gigabytes of RAM are not fast and probably close to the bound for factorial? | |
| Jan 25, 2015 at 13:15 | comment | added | Emil Jeřábek | Search for "There is one missing, but critical point." | |
| Jan 25, 2015 at 12:19 | comment | added | joro | @EmilJeřábek Factorial modulo n is completely different problem for me and possibly might be speeded by factoring not sure. In Lipton's blog I don't see modulo n, in which formula it is? | |
| Jan 25, 2015 at 12:03 | comment | added | Emil Jeřábek | I think you missed the point of the reduction. You evaluate the circuit modulo something of polynomial length, so all intermediate results are small. | |
| Jan 25, 2015 at 9:17 | comment | added | joro | @EmilJeřábek I edited addressing space complexity of factorial. I doubt Lipton's factoring is of any practical importance even if an oracle computes the factorial, since it is impossible to store $2^{1000}!$ on all computers on earth. | |
| Jan 25, 2015 at 9:16 | history | edited | joro | CC BY-SA 3.0 |
Added space complexity
|
| Jan 24, 2015 at 15:07 | comment | added | joro | @EmilJeřábek OK, I am interested what number theorists say about this open problem. | |
| Jan 24, 2015 at 15:05 | comment | added | Emil Jeřábek | But back to complexity: see rjlipton.wordpress.com/2009/02/23/factoring-and-factorials for a well-known connection of the problem to the complexity of factoring. | |
| Jan 24, 2015 at 15:03 | comment | added | joro | @EmilJeřábek OK, kept your tag :-) Similar sequences are on OEIS. | |
| Jan 24, 2015 at 15:03 | history | edited | joro |
Added tag
|
|
| Jan 24, 2015 at 15:01 | comment | added | Emil Jeřábek | Your question is what is the arithmetic circuit complexity of factorial, which is a complexity problem, no matter what point of view you take to approach the problem. Put the nt tag back if you think the problem has anything to do with number theory apart from the fact that it involves numbers, but don't remove the complexity tag. | |
| Jan 24, 2015 at 14:49 | comment | added | joro | @EmilJeřábek Thanks, but I am interested from number theory point of view, not from complexity point of view. Don't like starting a "tag war" and would appreciate the numbertheory tag. | |
| Jan 24, 2015 at 14:44 | comment | added | Emil Jeřábek | This question would be much more likely to receive an expert answer at cstheory. However, unless something changed recently (unlikely), no nontrivial unconditional lower bounds on the arithmetic circuit complexity of $n!$ are known. | |
| Jan 24, 2015 at 14:37 | history | edited | Emil Jeřábek |
edited tags
|
|
| Jan 24, 2015 at 11:51 | history | asked | joro | CC BY-SA 3.0 |