🚀 go-pugleaf

In article <By2v5F.DCM.2@cs.cmu.edu> jmount+@CS.CMU.EDU (John Mount) writes:
>Assume an enumeration of all Turing machines.  Suppose we want to
>solve SAT.  Let ALG be the Turing machine that simulates one step of
>machine i every 2^i steps (so it runs machine 1 every other step, 2
>every 4th , 4 every 8th).

Ah...  very cute.  I'm not sure why I hadn't seen or didn't remember
that construction.   Anyway, I hereby publically chastise myself for
not seeing this.

Now a question:  decision problems in NP are shown to be NP-complete
by many-to-one reductions, so the decision problems would all be
solvable by this technique.  However, some optimization problems use
Turing reductions, so you have to have an algorithm that always halts,
even for negative instances (this construction does not halt in these
cases).  Are there ways around this?  It seems that since verifying
prime factors is in both NP and co-NP, that's the saving grace for
factoring.  What about other problems?

-- 
Steve Tate srt@cs.duke.edu | The reason why mathematics enjoys special esteem,
Dept. of Computer Science  | above all other sciences, is that its laws are
Duke University     | absolutely certain and indisputable, while those of all
Durham, NC  27706   | other sciences are to some extent debatable. (Einstein)