Re: Any NP optimization problems that don't reduce to decision problems?

tchow_at_lsa.umich.edu
Date: 10/01/04 

Date: 01 Oct 2004 02:37:03 GMT

In article <415326f3$0$566$b45e6eb0@senator-bedfellow.mit.edu>, I wrote:
>Is there an example of an optimization problem X such that
>1. there is a natural "decision version" D of X that is in NP, but
>2. it is not known that "P = NP implies X is polytime solvable"?

I got only one response to my article, which didn't settle my question.
In the meantime I've done a bit of thinking on my own.

Let's be a little more precise about what we mean by an "optimization
problem." To any instance I, there is associated a set S (possibly empty)
of feasible solutions. There is a cost function c, defined on (at least)
on S, and taking values in (say) the positive integers. The problem is
to find, given an instance I, a solution of minimum cost (or else to
determine that there is no feasible solution).

By a "natural decision version," let's mean the problem that takes as
input the instance I plus a positive integer n, and asks if there exists
a feasible solution s such that c(s) <= n.

Stated this way, the answer to my question is "yes." For example, take
the halting problem. An instance is a Turing machine, and S is either
the singleton set {h} where h is the number of steps it takes to halt,
or S is empty if the machine doesn't halt. Take the cost function to
be c(h) = 2^h. Then the decision version is asking if the machine halts
in at most log n steps, which can be tested in time polynomial in log n
and the size of the machine. But of course, the halting problem is
undecidable.

We could add the proviso that the optimization problem is decidable.
However, the size of the solutions could still grow too fast. So, some
further conditions need to be added. I was hoping for a clean answer
to my question, but maybe there isn't one. 

-- 
Tim Chow       tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences