Re: Aggressive optimization

Article View: comp.lang.misc

Article #1972

#1972

From: Mike Bolotski
Date: Thu, 08 Nov 1990 00:17

22 lines
1179 bytes

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

Technical Details

Message-ID: <MISHA.90Nov7191750@just-right.ai.mit.edu>

Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!snorkelwacker!ai-lab!life!misha

References: <2133:Nov607:16:1090@kramden.acf.nyu.edu> <5079@lanl.gov> <7659:Nov620:58:5990@kramden.acf.nyu.edu>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!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: <MISHA.90Nov7191750@just-right.ai.mit.edu>
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

Reply to Parent Message