／var／logmarcus chiu

Decision Problems - Optimization Problems

Created on · Last Modified on

Decision Problems and Optimization Problems

  • both are types of a computational problem
  • decision problem is a problem that asks if a statement is true or false. The output of a decision problem is a single yes/no answer.
  • optimization problem is a problem that asks to find the best solution from all feasible solutions. The output of an optimization problem is a solution that minimizes or maximizes an objective function

Example Comparison

Decision Problem

corresponding

Optimization Problem

input:

  • directed graph 𝐺=(𝑉,𝐸)
  • weight function 𝑤:𝐸→ℝ
  • 𝑠 ∈ 𝑉
  • 𝑡 ∈ 𝑉
  • 𝑥 ∈ ℝ

output:

  • 1 if ∃ a path s→t with cost ≤ 𝑥
  • 0 otherwise

corresponding

input:

  • directed graph 𝐺=(𝑉,𝐸)
  • weight function 𝑤:𝐸→ℝ
  • 𝑠 ∈ 𝑉
  • 𝑡 ∈ 𝑉

output:

  • shortest path