Talk:Addition-chain exponentiation
Add topic | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
Example
[edit]Someone should add an example. -- 151.198.133.102
There may be an example (if it's the same thing) at Talk:Exponentiation by squaring. -- Toby Bartels 19:59, 7 Aug 2004 (UTC)
NP-hardness of addition chains
[edit]The paper "Computing sequences with addition chains" by P. Downey, B. Leong and R. Sethi, SIAM JOC, v.10, n.3, 1981 proves that finding a shortest addition sequence (i.e. an addition chain containing a given set of integers) is NP-hard. The paper clearly states that it is an open problem whether finding a shortest addition chain for an integer is NP-complete. Despite this clear statement the paper is often misrepresented. Is there a new result showing the NP-completeness of finding addition chains or is this article misquoting the paper above too? 85.2.29.86 21:24, 9 August 2007 (UTC)
- You're right, it is indeed a misquote. The Gordon et al. survey states that "Downey et al. [10] showed that the problem of finding the shortest addition sequence is NP-complete," which I misread as "addition chain". I'll hunt around for more references and then fix the article(s). —Steven G. Johnson 22:16, 9 August 2007 (UTC)
- I fixed it after nearly 2 years and made a concise wording shortest / minimal / optimal, hopefully. Regards, Achim1999 (talk) 15:00, 9 July 2009 (UTC)
Merger proposal
[edit]Is there anything in this article that could not be covered at Addition chain? Deltahedron (talk) 20:10, 25 July 2012 (UTC)