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

Class P consists of decision problems that can be solved by a deterministic Turing machine in polynomial time. These are considered tractable problems where the time complexity is bounded by a polynomial function of the input size, such as O(n^k). In contrast, class NP (Nondeterministic Polynomial time) consists of decision problems for which a given solution can be verified by a deterministic Turing machine in polynomial time. While every problem in P is also in NP, it is currently unknown if P equals NP. A key distinction is that P focuses on the efficiency of finding a solution, whereas NP focuses on the efficiency of verifying a potential solution provided by a nondeterministic process.

A polynomial run time algorithm is an algorithm whose execution time is bounded by a polynomial expression of the input size n. Formally, an algorithm has polynomial time complexity if its running time T(n) is O(n^k) for some constant k > 0. These algorithms are categorized as efficient or tractable because their growth rate remains manageable as the input size increases significantly.

Key characteristics include:

• Scalability: Unlike exponential time algorithms (e.g., O(2^n)), which become computationally infeasible for even moderate input sizes, polynomial algorithms scale gracefully.
• Examples: Common examples include sorting algorithms like Merge Sort (O(n log n)) and searching algorithms like Binary Search (O(log n)).
• Complexity Classes: Polynomial time is the defining criterion for the class P. If an algorithm's complexity is O(n^k), it is considered to be in the class P, serving as the benchmark for practical computational feasibility in computer science.