Decision Problem

A decision problem asks whether there exists a solution to a given computational problem, with a yes or no answer. Decision problems form the basis for determining complexity classes like P and NP.

Java example - Subset sum problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// Returns true if subset with given sum exists
boolean hasSubsetSum(int[] set, int sum) {
  boolean[][] dp = new boolean[set.length+1][sum+1];
  
  for (int i = 0; i <= set.length; i++) {
    dp[i][0] = true;
  }
  
  for (int i = 1; i <= set.length; i++) {
    for (int j = 1; j <= sum; j++) {
      if (j < set[i-1]) {
        dp[i][j] = dp[i-1][j];
      } else {
        dp[i][j] = dp[i-1][j] || dp[i-1][j-set[i-1]];
      }
    }
  }

  return dp[set.length][sum];
}

C++ example - Hamiltonian path problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Returns true if Hamiltonian path exists
bool hasHamiltonianPath(vector<vector<int>> graph) {
  int n = graph.size();
  vector<int> path;

  return hamiltonianPath(graph, 0, path, n); 

}

bool hamiltonianPath(vector<vector<int>>& graph, int curr, 
                     vector<int>& path, int n) {
  // Backtracking algorithm
  // Returns true if found path
  return false; 
}

Python example - Clique problem:

1
2
3
4
5
6

# Returns true if clique of given size exists  
def hasClique(graph, k):
  
  # Backtracking algorithm
  return False

Decision problems only specify existence, not construction. Fundamental problems in complexity theory and algorithms.

A decision problem is a question that yields a yes-or-no answer. More formally 1 or 0. In computer science, these problems serve as the foundation for computational complexity theory. They are generally expressed through formal languages or mathematical constructs and aim to evaluate the computational feasibility of solving a given problem.

Example Code in Java

Here, we have a simple decision problem: “Is a given number even?”

1
2
3
4
5
6
7
8
9

public class DecisionProblem {
    public static boolean isEven(int n) {
        return n % 2 == 0;
    }
    public static void main(String[] args) {
        System.out.println("Is 4 even? " + isEven(4));
        System.out.println("Is 5 even? " + isEven(5));
    }
}

Example Code in C++

In C++, we use the modulo operator to check if a number is even.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <iostream>
using namespace std;

bool isEven(int n) {
    return n % 2 == 0;
}

int main() {
    cout << "Is 4 even? " << isEven(4) << endl;
    cout << "Is 5 even? " << isEven(5) << endl;
    return 0;
}

Example Code in Python

In Python, the logic remains the same, with the use of the % symbol to perform modulo.

1
2
3
4
5

def is_even(n):
    return n % 2 == 0

print("Is 4 even?", is_even(4))
print("Is 5 even?", is_even(5))

In all these examples, the code takes a number as input and returns a boolean value as output, representing whether the number is even. This mirrors the essence of a decision problem, providing a “yes” or “no” answer.