Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!snorkelwacker!ai-lab!life!misha From: misha@ai.mit.edu (Mike Bolotski) Newsgroups: comp.lang.misc Subject: Re: Aggressive optimization Message-ID: Date: 8 Nov 90 00:17:50 GMT References: <2133:Nov607:16:1090@kramden.acf.nyu.edu> <5079@lanl.gov> <7659:Nov620:58:5990@kramden.acf.nyu.edu> Sender: news@ai.mit.edu Organization: MIT Artificial Intelligence Laboratory Lines: 22 In-reply-to: brnstnd@kramden.acf.nyu.edu's message of 6 Nov 90 20:58:59 GMT In article <7659:Nov620:58:5990@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > pointers (arrays) are pre-indexed appropriately. Could one of you CS > types please illustrate to Jim that finding optimal addition chains in a > general computation is equivalent to solving the halting problem? Bzzt. But thanks for playing, Dan. Optimal addition is NP. Halting problem is undecidable (ever). You can argue practicality, but not theory. -- Mike -- Mike Bolotski Artificial Intelligence Laboratory, MIT misha@ai.mit.edu Cambridge, MA