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³)), insertion sort (O(n²)), 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 intractable or infeasible if 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 problem if they produce output “Yes” or “No” for given input. An algorithm which solves the decision problem is called decision algorithm.

An optimization problem aims for the best solution from the set of all feasible solutions. An algorithm which solves optimization problem is called optimization 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 problem too. Solution to such problem differs on each execution even for the same input. So such problems are more complex than decision problems.

Complexity classes are 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, where n represents the size of the problem, we say that the problem has polynomial time complexity.

Satisfiability Problem 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₁ and P₂ are two problems and there exists some deterministic algorithm A for P₁ such that P₁ can be solved in polynomial time using A. If the same algorithm can solve the problem P₂ then we can say that P₂ is reducible to P₁.

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