A Textbook of Data Structures and Algorithms, Volume 3

22P and NP Class of Problems

22.1. Introduction

A galaxy of computational problems exists in various disciplines, and researchers and scientists in general have striven hard or are still striving hard to solve these problems on a computer, by discovering or toiling hard to discover efficient algorithms for their solutions. Many of these problems have even offered them opportunities to discover an array of algorithms, one surpassing the other, in terms of efficiency or implementation.

There is a big class of problems that have been solved using algorithms having polynomial time complexity. For example, the time complexity T(n) of the best-known algorithms for the problems of finding the max/min element in a list or matrix multiplication or finding the first positive element in a list, to quote a well-known few, report polynomial time complexity. Such algorithms report T(n) = O(f(n)) or T(n) = Ω(f(n)) or T(n) = Θ(f(n)), where f(n) is a polynomial of a small degree and O(f(n)), Ω(f(n)) and Θ(f(n)) denote the upper bound, lower bound and both upper and lower bound, respectively, for T(n). The definitions and details pertaining to O(f(n)), Ω(f(n)) and Θ(f(n)) can be found in Chapter 2, Volume 1. Thus, the best-known algorithm to find the max/min element in a list reports Θ(n), the high school method of matrix multiplication reports O(n³) and the best case complexity for finding the first positive element in a list of real numbers reports Ω(1).

Such a class of problems is theoretically ...