1
$\begingroup$

An optimisation problem requires minimising some function $f(x)$, where $x$ is a vector of integers. What is the corresponding decision version of the problem?

Improve this question
$\endgroup$
1
  • $\begingroup$ what are the steps of creating decision versions? $\endgroup$ Commented Aug 22, 2012 at 15:25

1 Answer 1

Reset to default
4
$\begingroup$

"Given $f(x)$, what is $\min(f(x))$?" becomes "Given $f(x)$, and $k$, decide if there is an $x$ such that $f(x)< k$?"

Improve this answer
$\endgroup$
2
  • $\begingroup$ I see from the edit @blk that a decision must be a yes or no answer question? $\endgroup$ Commented Aug 22, 2012 at 15:32
  • 2
    $\begingroup$ Indeed. Your question is very basic. Please consult some introductory books on computability or complexity theory. $\endgroup$ Commented Aug 22, 2012 at 15:42