P vs. NP Classes
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@iitj.ac.in
Formerly at department of Computer Science and Engineering
MBM Engineering College, Jodhpur

Thursday 13th November, 2025

kr chowdhary

TOC

1/ 1

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Complexity of computation
Adding two n-digit numbers: n + 1 steps usually. But if we look
at minor steps then 5n + 1 steps( n additions of digits, n additions of
carry, n comparisons if sum of two digits is greater than 10, n steps
to print lower digit, n steps to save carry). The last step is for carry
save from last sum.
Even further smaller steps are taken, it comes out to be an + b,
where a, b are constants, not dependent on n. Thus time complexity
of add, is θ (n).
Multiplication: To multiply x and y , one approach if add x to 0, y
times. If both numbers are n digit long, then θ (n.10n ).
Other method is θ (n2 ) complexity. The best known algorithm for
multiplication is θ (n1.1 ).
Factoring: of n digit number. Some times not well defined, as
1001 = 77 × 13 or 91 × 11. To factor Z we need to divide it by range
2 to Z − 1. If |Z | = n, complexity is 10n . No solution like, θ (n) or
θ (nc ), where c is constant, is available.

kr chowdhary

TOC

2/ 1

Complexity terms

T(n): Time complexity of standard Turing Machine. Function T (n)
is called time-constructible if there exists a time-bound Deterministic
TM that with input makes |w | = n moves.
T(n): Nondeterministic Turing machine Time complexity.
S(n): Space complexity of standard Turing Machine. Function S(n)
is called space-constructible, if there exists a space-bound standard
TM, that for each input of length n, requires exactly S(n) space.
DTIME(T(n)): class of languages that have deterministic time
complexity of O(T (n)).
NTIME(T(n)): class of languages that have nondeterministic time
complexity of O(T (n)).

kr chowdhary

TOC

3/ 1

The class P
Let L ⊆ Σ∗ . L is polynomial if membership of w can be determined
in polynomial function of n, where |w | = n. Polynomial time is in
terms of number of transitions in TM. L is decidable in polynomial
time if standard std TM M can decide L in tcM ∈ O(nr ), where r is
natural number, not related to n. The family of L is Class-P.
A language accepted by multi-tape TM in time O(nr ) is accepted by
STD TM in time complexity O(n2r ), which is also polynomial. This
invariant shows the robustness of TM.
P : Class of membership problems for the languages in
[

DTIME (P(n)); where P(n) is polynomial in n.

P (n)

1 Acceptance of palindromes: Output is YES if w ∈ Σ∗ is palindrome,
else NO. Complexity Class=P.
2 Path problem in directed graphs: Input is G=(V,E). Output is YES
if there is a path from vi to vj in the graph, else NO. Complexity
class=P, as complexity = O(n2 ) due to Dijkstra’s algorithm.
3 Deriviability in CNF: Input: CNF G, w, output=Yes, if S ⇒∗ w else
No. Complexity: P= yes.
kr chowdhary

TOC

4/ 1

The Class NP
Definition: A language is in NP iff it is decided by some NDTM in
polynomial time. NDTM guesses the alternatives.
Polynomial solution for these are not known to exist.
in NDTM the solution is selected nondeterministically rather than
systematically examining all the possibilities. ∴ P ⊆ NP, because a
P problem is also NP.
NP : The class of membership problems for languages in
[

NTIME (P(n))

P (n )

Examples:
1. SATISFIABILITY problem: Input Boolean expression u in CNF,
Output = YES if there is an assignment that satisfies u else
NO.Complexity: In P - Unknown, in NP - YES.
2. Hamiltonian path problem: Input directed graph G, Output: YES
if there is a single cycle that visits all nodes, No other wise.
Complexity: P-unknown, NP- YES. Hamiltonian path problem is in
NP, but its solution can be verified in P.
3. Subset sum problem: Input: Set S, number k, output: Yes if there
is P ⊆ S, whose toatl is k, else No. Complexity: P - unknown, NP yes.
kr chowdhary
TOC
5/ 1

Primality test and Compositeness
PRIMES = {x|x is prime}, COMPOSITS = {y |y is Composite
number}, ∴, PRIMES = COMPOSITS, ∴, if COMPOSITS is NP
then PRIMES is Co − NP (Complement of NP).
COMPOSITNESS can be determined by NDTM by guessing
Nondterministically.
COMPOSITNESS is in NP but its solution can be verified in P time.
Fermat’s Little theorem for primality test: If p is prime and a is
integer, then:
ap ≡ a(mod p), i.e., ap − a is evenly divisible by p. This problem is
NP because exponential component ap .
Example: 211 − 2 is divisible by 11.
Sets of primes are in NP but not in NP-complete, similarly the
COMPOSITS. The language of PRIMES is NP ∩ Co − NP,and hence
of COMPOSITS also.
Because, if that is not the case then NP = Co − NP.

kr chowdhary

TOC

6/ 1

Primality test and Compositeness . . .
Theorem
COMPOSITS are NP

Proof.
1 Input on NDTM = p, |p| = n. Guess a factor f of at most n bits
(f ̸= 1, f ̸= p). This part is non-deterministic. The time taken by
any sequence of choice is O(n).
2 Divide p by f , check if remainder is 0. Accept if so. Part 2 is
deterministic O(n2 ) on STD 2-tape TM.

Definition: If there is a polynomial time algorithm for one
NP-problem, then all NP problems are solvable in P time, are called
NP-complete.
This is because, if A is NP-complete, then all NP-problems are
reducible to it. And, if A ∈ P, then all those NP are P.
Adv: 1. if one can be solved, then all rest are automatically solved,
2. One may choose only one of the most appropriate NP problem for
solution.
kr chowdhary

TOC

7/ 1

Complexity classes-Time
Class
DTIME(f(n))
P
NTIME(f(n))
NP
EXPTIME

Machine
DTM
DTM
NDTM
NDTM
DTM

Time constraint
f(n)
poly(n)
f(n)
poly(n)
2poly (n)

EXPTIME : The class of membership problems for this languages in
[

DTIME (2P (n) ).

P (n )

Satisfiability is NP-complete. A Boolean expression
φ = {x̄ ∧ y ) ∨ (x ∧ z̄) is satisfiable for x=0, y=1, z=0, as it evaluates
φ to 1 (TRUE).
SAT is languages of all satisfiable formulas, SAT = {< φ > |φ is
satisfiable Boolean formula }. Cook-Levin theorem links the
complexity of SAT problem to complexities of all problems in NP.
kr chowdhary

TOC

8/ 1

Polynomial reduction

Polynomial time reducibility: If problem A reduces to problem B,
then solution of B can be used to solve A.
1. Definition: A function f : Σ∗ → Σ∗ is polynomial time
computable if some polynomial TM M, which when started with
input w , halts with f (w ) on tape.
2. Definition: Language A is polynomial reducible to lang. B,
expressed as A ≤P B, if ∃ a polynomial function f such that
f : Σ∗ → Σ∗ for every w ∈ A ⇐⇒ f (w ) ∈ B.
3. To test whether w ∈ A, we use the reduction f to map w to f (w )
and then test whether f (w ) ∈ B?
4. If one language is polynomial time reducible to a language
already known to have polynomial time solution, we obtain a
polynomial solution to original.

kr chowdhary

TOC

9/ 1

Polynomial reduction

Theorem
If A ≤P B and B ∈ P, then A ∈ P.

Proof.
Let M be polynomial time algorithm deciding B, and f be
polynomial time reduction from A to B. We describe polynomial
time algorithm for M ′ for A as follows:
M ′ = Input w, step 1. compute f (w ) on TM R (reducer for f), step
2. Run M on input f (w ). ∴, M ′ is polynomial because each of
above steps are polynomial (Note: Composition of two polynomial
functions is polynomial).

kr chowdhary

TOC

10/ 1

NP-Complete and NP-Hard

Definition: NP-Complete: A language B is NP-complete if it
satisfies two-conditions: (1) B ∈ NP, (2) Every A ∈ NP is
polynomial time reducible to B, i.e.,
B ∈ NP ∧ ∀A : A ∈ NP ∧ A ≤P B ⇒ B ∈ NP-Complete.
A language Q is NP-hard if every L ∈ NP is polynomially reducible
to Q.
∀L : L ∈ NP ∧ L ≤P Q ⇒ Q ∈ NP − hard.
The NP-hard problem that is also NP is called NP-complete.
Co-NP is complement of NP, ∴, Co-NP is set of all the
complements of all the NP problems.

kr chowdhary

TOC

11/ 1

NP-Complete Theorem

Theorem
If B is NP-Complete and B ∈ P, then P = NP.

Proof.
If B is NP-Complete then every problem in NP is polynomially
reducible to B. Since B ∈ P, ∴, every NP problem is polynomially
reducible to to B, which is P. Hence, every NP is P, i.e. P = NP.
Once we get NP-Complete, other NP problems can be reduced to it.
However, establishing first NP-Complete problem is difficult.

kr chowdhary

TOC

12/ 1

NP-Complete Theorem

Theorem
If B ∈ NP-Complete and B ≤P C for C ∈ NP, then C ∈ NP-Complete.

Proof.
We must show that every A ∈ NP is polynomially reducible to C .
Because B is NP-Complete, ∴, every A ∈ NP is polynomially
reducible to B. (as per property of NP-Complete). And B in turn is
polynomially reducible to C (given).
Because the property of polynomial is closed under the composition,
We conclude that every A ∈ NP is polynomially reducible to C.
Therefore C is NP-Complete.

kr chowdhary

TOC

13/ 1

Cook-Levin Theorem
Theorem
SAT is NP-Complete.

Proof.
Proof Idea: It is easy to show that SAT is NP, the hard part is to
show that any language in NP is polynomially reducible to SAT.
∴, we construct a polynomial time reduction for every A ∈ NP to
SAT.
Reduction for a language A takes input w and produces Boolean
formula φ that simulates the NP machine for A on input w.
If machine accepts, φ has a satisfying assignment, that corresponds
to accepting computation, otherwise NO.
∴, w ∈ A iff φ is satisfiable.
NP-Complete problems: 3-SAT, Hamiltonian path problem,
subset construction problem.

kr chowdhary

TOC

14/ 1

Space - Complexity
S(n): The function S(n) is called space constructible if there exists
an S(n) space-binded Det. TM that for each input |w | = n requires
exactly S(n) space. ∴, S(n) = Space complexity of a Det. Turing
Machine.
DSPACE(S(n)): class of languages that have deterministic space
complexity of O(S(n)).
PSPACE: The class of membership problems for the languages
decidable in polynomial space on deterministic TM:
PSPACE =

[

DSPACE (nk )

k

class
DSPACE(f(n))
L
PSPACE
EXPSPACE
NSPACE(f(n))
NL
NEXPSPACE

machine
DTM
DTM
DTM
DTM
NDTM
NDTM
NDTM

kr chowdhary

TOC

Space constraint
f(n)
O(logn )
poly(n)
2poly (n)
f(n)
poly(n)
2poly (n)
15/ 1

Space - Complexity
DSPACE (f (n)) = {L|L is decidable by O(f(n)) space on DTM}.
NSPACE (f (n)) = {L|L is decidable by O(f(n)) space on NDTM}
Savitch’s Theorem: If a NDTM uses f (n) space, it can be
converted into a DTM that uses f 2 (n) space.
As per Savitch’s theorem: PSPACE = NSPACE ,
EXPSPACE = NEXPSPACE .
For NDTM, if f (n) is maximum number of tape-cells scan in any
branch of computation, then its complexity if f (n).
SAT which is NP − Complete in time, is linear space. (because is
reusable).
PSPACE = NSPACE , P ⊆ PSPACE . NP ⊆ NSPACE ,
∴, NP ⊆ PSPACE .
∴, P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME .

kr chowdhary

TOC

16/ 1

Bibliography

Chowdhary, K.R. (2025). Decidability, Undecidability, and
Unsolvability. In: Theory of Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_12

kr chowdhary

TOC

17/ 1