# Types of Problems and Computational Complexity

Types of problems in computational theory define the group of the problem which are categorized based on their computational complexity.

## Types of Problems: Polynomial and Non-Polynomial Problems

- Basically, problems are classified as
*tractable*or*non-tractable*. If the running time algorithm falls in O(P(n)), where P(n) is the polynomial in n then the problem is said to be tractable. Most real-world problems are tractable. - They are also said to be
*polynomial problems*. For example, finding factorial (O(n)), adding two arrays (O(n)), matrix multiplication (O(n^{3})), insertion sort (O(n^{2})), merge sort (O(nlogn)), binary search (O(logn)) etc. are example of polynomial problems. - Certain problems may not be solvable or their solution cannot be found in polynomial time, such problems are called
*non-tractable*or non*-polynomial*problems. - Even if we can find the solution to such problems, it does not have much practical importance due to the time taken by the algorithm.
- Problems like the Hamiltonian cycle, travelling salesman problem, tower of Hanoi etc. cannot be solved in polynomial time and hence they are non-tractable problems.
- The running time of non-tractable problems grows very quickly with an increase in problem size.

## Problem Classification

We can classify the problem in one of the following categories :

1. The problem which cannot be even defined in a proper way.

2. The problem which can be defined but cannot be solved.

3. The problem which can be solved theoretically, but computationally they are not feasible. The algorithm takes a very long time to solve such problems, and the time is practically not acceptable. For example, cracking a password of 256 characters by brute force method may take years.

Problem is called

intractableorinfeasibleif it takes too long time to be solved. A solution of such problems has no practical application

4. Problems which can be solved theoretically and practically in a reasonable amount of time. For such problems, there exists a deterministic Turing machine that can solve the problem in O (p(n)) time, where p(n) is polynomial in *n*, and *n* is a problem size.

If the problem is solvable in polynomial time, it is called

tractable. Such problems are denoted by P problems.

5. The problem is not known whether it is n P or not in P. Such problems fall somewhere in between class 3 and 4.

## Definitions

The problem is said to be

decision problemif they produce output “Yes” or “No” for given input. An algorithm which solves the decision problem is calleddecision algorithm.

An optimization

problemaims for the best solution from the set of all feasible solutions. An algorithm which solves optimization problem is calledoptimization algorithms.

The optimization algorithm seeks to find the best profit or least cost solution. Decision problems are simpler than optimization problems.

**Computational complexity:** Computational problems have infinite instances. Each instance in the set contains the solution. Typically, the solution to the problem in computational complexity is Boolean i.e. ‘Yes’ or ‘No’.

The computational problem can be

function problemtoo. Solution to such problem differs on each execution even for the same input. So such problems are more complex than decision problems.

Complexity classesare set of problems of related complexity, like P problems, NP problems, Decision problems, Optimization problems etc. The complexity of any problem in given class falls in certain range

Problems which takes practically unacceptable time i.e. very long time to be solved are called

intractable problems.

If the running time of the algorithm is bounded to O(p(n)), where p(n) is some polynomial in

n, wherenrepresents the size of the problem, we say that the problem haspolynomial time complexity.

SatisfiabilityProblem is to check the correctness of assignment. Satisfiability problem finds out whether for given input an expression is true for that assignment

Reducibility :Let P_{1}and P_{2}are two problems and there exists some deterministic algorithm A for P_{1}such that P_{1}can be solved in polynomial time using A. If the same algorithm can solve the problem P_{2}then we can say that P_{2}is reducible to P_{1}.

Youtube Channel: https://shorturl.at/inryW