What is meant by polynomial time?

An algorithm is said to be polynomial time if its running time is upper bounded by the polynomial expression in the size of the input for the algorithm. The polynomial time is represented as $T\left(n\right) = O\left(n^k\right),$ where k is a positive constant and n is the complexity of input. In other words, if the time complexity to solve a specific problem can be represented by a polynomial function, then the problem is said to be polynomial-time.

The problems for which the deterministic polynomial-time algorithm exists belong to the complexity class (p) and it is central in the field of computational complexity theory. According to Cobham’s thesis, polynomial time is a synonym for “feasible”, “fast”, and “efficient”.

What is a polynomial time algorithm?

An algorithm where execution time is either provided by a polynomial in input size or limited by the polynomial is called a polynomial time algorithm. Tractable problems are problems that are solved by the polynomial-time algorithm. This algorithm is more efficient and the exponential-time algorithm is inefficient as the execution time increases based on the problem size.

Most algorithms on the array use array $size\left(n\right)$ as the input size. To find the maximum element in the array requires a single pass through the array. The time required to perform this requires $O\left(n\right) or linear time.$ The sorting algorithm requires $O(n \log n) or O\left(n^2\right)$ time. Bubble sort requires $O\left(n^2\right)$ time for both average and worst cases. Quicksort takes $O(n \log n)$ time in the average case and $O\left(n^2\right)$ in the worst case.

Example for polynomial time algorithm

Some of the examples of polynomial-time algorithms are,

• Selection sort sorting algorithm with n integers performs $A{n}^2$ operations for constant A. The run time complexity of the selection sort is $O\left(n^2\right).$

• Basic arithmetic operations like addition, multiplication, subtraction, comparisons, and division are done in polynomial time.

• Maximum matchings problem for a graph can be solved in polynomial time.

Selection sort complexity

Selection sort is an in-place comparison-based sorting algorithm. The selection sort algorithm is inefficient on large lists. Compared to other sorting algorithms, selection sort is not difficult to analyze, since none of the loops depend on the data in the array. Selecting the minimum element requires scanning n elements (using n-1 comparisons) and then swapping it with the first position. To find the next lowest element, the selection sort requires scanning the remaining n-1 elements (n represents the input size) and so on. The total number of comparisons is

$(n-1) + (n-2) +.....+ 1 = \sum _{i=1}^{n-1}i$

Using arithmetic progression,

$\underset{i=1}{\overset{n-1}{\sum i }} = \frac{(n-1)+1}{2}(n-1) = \frac{1}{2}n(n-1) =\frac{1}{2} (n^2-n)$

The selection sort is of complexity $O\left(n^2\right)$ in terms of number of comparisons. Each scan requires one swap for n-1 elements (the last element is already in its place). The time complexity of selection sort for the best, average, and worst case is $O\left(n^2\right)$. Thus, it is a polynomial time algorithm.

Computational complexity theory

In computer science, the computational complexity theory is the branch of the theory of computation that studies the cost or resources of computation required to solve a given computational problem. This theory analyses the difficulty of computational problems in terms of different computational resources.

Complexity classes

A complexity class is the set of all of the computational problems which can be solved using a certain amount of computational resources. The Polynomial-time concept leads to different complexity classes. The four major complexity classes include P, NP, NP-hard problem, and NP-complete. Other classes like RP, ZPP, BPP, and BQP also exist.

P

P represents a decision problem set that is solvable within polynomial time. P is the smallest class in terms of the time complexity of a deterministic machine. P is often taken to be the class of computational problems that are tractable or efficiently solvable. Intractable is defined as the problems which are solvable in theory and cannot be solved in practice. P contains natural problems and includes the decision versions of linear programming, calculating the greatest common divisor, and finding a maximum match. Example problems,

• Fractional knapsack
• MST
• Sorting

NP

The non-deterministic polynomial problem is the full form of NP. NP is the setoff decision problem solvable in polynomial time on a deterministic Turing machine. NP is a set of problems that can be verified by a deterministic Turing machine in polynomial time. All the problems in NP class have the same property and their solutions can be checked effectively. NP class contains many problems with best solutions such as,

• Hamiltonian path problem (a special case of traveling salesman problem).
• Boolean satisfiable problem.
• Vertex cover problem.

NP-hard problem

A problem is NP-hard if an algorithm that solves the problem can be translated to an algorithm that solves an NP problem. The problems are at least need to be hard as NP problems but they need to be more complex. NP problems can be solved within polynomial time. The examples of NP-hard problems are

• Traveling salesman problem
• Circuit-satisfiability problem
• Vertex cover and set cover problem

NP-complete

The short form of nondeterministic polynomial time complete is NP-complete. The term “nondeterministic” refers to the non-deterministic Turing machine (mathematical formalizing the brute-force search algorithm). In complexity theory, the NP-complete problems are the most difficult problems in NP. If the user could solve the NP-complete problem quickly, then they could use the algorithm to solve all NP problems quickly.

The algorithm for NP-complete problems requires time, which is superpolynomial in the input size. To solve an NP-compete problem for a non-trivial problem size, the approaches used in NP-complete are probabilistic, approximation, and heuristic. Some of the problems of NP-complete are,

• N-puzzle
• Knapsack problem
• Graph coloring
• Subset sum problem

NP-complete problem

NP-Complete problem (NPC) is present in both NP-hard and NP classes. NPC problems can be verified in polynomial time and NP problems can be reduced to NPC problems in polynomial time. When there is a problem in the polynomial-time algorithm, then all the problems under NP can be resolved in polynomial time and these problems are known as NP-complete.

Context and Applications

This topic is important for postgraduate and undergraduate courses, particularly for,

• Bachelors in computer science engineering.
• Associate of science in computer science.

Practice Problems

Question 1: Which of the following problem cannot be solvable in polynomial time.

1. Solution problem
2. Halting problem
3. Traveling salesman problem
4. None of the above

Answer: Option b is correct.

Explanation: Turing's halting problem cannot be solved by any computers. The solution of the halting problem cannot be found within the given polynomial time (regardless of time).

Question 2:  The 3-SAT and 2-SAT problems are ____

1. Both in p
2. Undecidable and NP-complete respectively
3. NP-complete and in P respectively
4. Both NP-complete

Answer: Option c is correct.

Explanation: The Boolean satisfiable problem (SAT) is a decision problem. Where the instance is written using ANS, NOT, OR, parentheses, and variables. 3-SAT and 3-SAT are the special cases of k-satisfiability and the clauses contain exactly k with 3 or 2 literals.

Question 3: ___ is the decision problem class which are solved using a non-deterministic algorithm.

1. P
2. NP
3. NP-hard
4. NP-complete

Answer: Option b is correct.

Explanation: The control mechanism of a non-deterministic Turing machine works like a non-deterministic finite automaton. In complexity theory, the NP is a problem that is solvable in polynomial time on a non-deterministic Turing machine.

Question 4: Let Z be an NP-complete problem and X and Y be two other problems not known to be in NP. X is polynomial time reducible to Z and Z is polynomial-time reducible to Y. Which one of the following statements is true?

1. Y is NP-complete
2. Y is NP-hard
3. X is NP-hard
4. X is NP-complete

Answer: Option b is correct.

Explanation: The true statement is "Y is NP-hard", as there is no NP-complete problem that is polynomial time Turing-reducible to X and NP-complete problem Z is polynomial time reducible to Y.

Question 5: what is NP?

1. No problem
2. Non-polynomial
3. Non-deterministic problem
4. Non-deterministic polynomial problem

Answer: Option d is correct.

Explanation: The full form of NP is a Non-deterministic polynomial problem. NP is a set of problems that can be verified by a deterministic Turing machine in polynomial time. All the problems in NP class have the same property and their solutions can be checked effectively.