Mathematical Preliminaries: Types of Problem

Decision Problems

Decision problem are those that require a yes or no, or true or false answer. These are fundamental in computer science, particularly in the theory of computation and complexity theory.
An example of a decision problem would be deciding whether or not a number is prime.
Decision problems form the basis of the class NP in the P vs NP problem, which is a major unsolved problem in computer science.

Optimization problem involves finding the best solution from all feasible solutions. This may include finding the ‘minimum’ or ‘maximum’ solution according to the problem context.
Optimization problems are commonly represented by objective functions and constraints. The objective function is the function to be optimized, while constraints represent the set of restrictions or boundaries within which the solutions must occur.
Examples of optimization problems include the Travelling Salesman problem and Knapsack problem.

Search problems require finding a solution or a series of solutions that meet certain criteria from within a possible set of solutions.
Search problems can often be solved using algorithms such as iterative deepening, A* search, depth-first search, and breadth-first search.
These problems are common in fields like artificial intelligence, operations research, database theory, and algorithm design.

Counting problems involve determining the number of elements that satisfy certain conditions within a set.
These problems can often involve combinatorics, including combinations, permutations, binomial coefficients and exponential generating functions.
These are very important in probability theory, graph theory, and statistical mechanics.

Existence problems entail determining whether a solution to a specified problem exists or not.
This type of problem does not necessarily require finding the solution but rather proving if a solution can or cannot be attained.
They are often integral in theorem proving, logic, and mathematics research.