Re: Complexity of optimal addition chains

Article View: comp.theory

Article #1948

#1948

From: "C. Papadimitriou"
Date: Thu, 24 Dec 1987 04:35

8 lines
899 bytes

Finding the best addition chain has been conjectured to be NP-complete.
As I recall, Ravi Sethi and co-authors have shown that finding the best
addition chain for several numbers (to be computed together) is NP-complete.

---CHP
[The reference is: Downey, Leong, and Sethi, "Computing sequences with
addtion chains," SIAM J. Computing, 10, 3 (August 1981) 638-646. ]

Technical Details

Message-ID: <8712242357.AA22233@jade.berkeley.edu>

Path: arc1-ca.pugleaf.net!utzoo!utgpu!water!watmath!clyde!rutgers!sdcsvax!ucbvax!SCORE.STANFORD.EDU!PAPA

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!water!watmath!clyde!rutgers!sdcsvax!ucbvax!SCORE.STANFORD.EDU!PAPA
From: PAPA@SCORE.STANFORD.EDU ("C. Papadimitriou")
Newsgroups: comp.theory
Subject: Re: Complexity of optimal addition chains
Message-ID: <8712242357.AA22233@jade.berkeley.edu>
Date: 24 Dec 87 04:35:03 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: TheoryNet List <THEORYNT%NDSUVM1.bitnet@jade.berkeley.edu>,
        "C. Papadimitriou" <PAPA@score.stanford.edu>
Distribution: inet
Organization: The ARPA Internet
Lines: 8