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(n3)), insertion sort (O(n2)), 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.
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.
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 P1 and P2 are two problems and there exists some deterministic algorithm A for P1 such that P1 can be solved in polynomial time using A. If the same algorithm can solve the problem P2 then we can say that P2 is reducible to P1.
Youtube Channel: https://shorturl.at/inryW