JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech IV COMPUTATIONAL COMPLEXITY Previous Question Paper (July/August - 2022 - R18)

A Polynomial time algorithm is one whose running time is bounded by a polynomial function of the input size n. Specifically, an algorithm runs in polynomial time if there exists a constant k such that the number of operations is O(n^k).

The justification for using polynomial time as the standard definition of tractability, known as the Cobham-Edmonds thesis, is based on several key factors:

1. Closure under composition: If an algorithm calls a polynomial-time subroutine a polynomial number of times, the resulting algorithm remains polynomial. This allows for modular algorithm design.
2. Model Independence: Polynomial time is robust across most reasonable models of computation. An algorithm that is polynomial on a multi-tape Turing machine remains polynomial on a single-tape machine or a random-access machine (RAM).
3. Practical Efficiency: While high-degree polynomials (e.g., n¹⁰⁰) are technically inefficient, they are rare in practice. Most naturally occurring polynomial-time algorithms have small exponents, making them feasible for large inputs, whereas exponential-time algorithms quickly become intractable as n grows linearly.

The P versus NP problem asks whether every decision problem whose solution can be verified in polynomial time (NP) can also be solved in polynomial time (P). In essence, it asks if P = NP.

This problem is considered one of the hardest in computer science for the following reasons:

1. Verification vs. Search: It is easy to check if a provided certificate (solution) is correct for an NP problem, but finding that certificate from scratch appears to require an exhaustive search through an exponential number of possibilities.
2. NP-Completeness: The existence of NP-complete problems, such as the Boolean Satisfiability Problem (SAT), acts as a bridge. If any single NP-complete problem is proven to be in P, then P = NP. Despite decades of effort, no polynomial-time algorithm has been found for any NP-complete problem.
3. Relativization: It has been proven that there exist "oracles" where P = NP and others where P ≠ NP. This demonstrates that standard diagonalization techniques, which solved many problems in computability theory, are insufficient to resolve this question, requiring entirely new mathematical insights into the structure of complexity classes.