Decision Problem and Optimization Problem

From: Deokhwan Kim (deokhwankim_at_hotmail.com)
Date: 11/10/04 

Date: 10 Nov 2004 04:37:24 -0800

Two questions occurred to me when I studied materials related to
Church-Turing thesis.

A book say ALL problems are classfied into decision problems or
optimization problems. Is it right? If so, how can we prove it?

And an optimization problem can be solved by binary searching between
a lower bound and a upper bound, if we can solve the corresponding
decision problem. But is it ALWAYS possible to know the boundaries?

Thanks.

Relevant Pages

  • Re: Decision Problem and Optimization Problem
    ... Often you can convert these into decision problems ("is the nth digit ... > a lower bound and a upper bound, if we can solve the corresponding ... some optimization problems have unbounded solution spaces. ...
    (comp.theory)
  • Re: Decision Problem and Optimization Problem
    ... > Deokhwan Kim wrote: ... Are there any problems that can't be converted into decision problems? ... >> a lower bound and a upper bound, if we can solve the corresponding ... > some optimization problems have unbounded solution spaces. ...
    (comp.theory)
  • Re: NP-hardness
    ... Anyway I want the sample proof for NP-hardness proof ... of optimization problems which are NP hard not NP complete even if it ... NP hard problems, NP-complete problems, and problems in NP are not ... Optimization problems can be converted into decision problems by asking ...
    (sci.math)