Chapter 4

Push down automata

Push-Down Automata (PDA) is an abstract model of a machine – Finite State Automata. It has a
finite set of states. However, in addition, it has a pushdown stack. Moves of the PDA are as
follows:

1. An input symbol is read and the top symbol on the stack is read.
2. Based on both inputs, the machine enters a new state and writes zero or more symbols
onto the pushdown stack.
3. Acceptance of a string occurs if the stack is ever empty. (Alternatively, acceptance can
be if the PDA is in a final state. Both models can be shown to be equivalent.)

A pushdown automaton is a way to implement a CFG in the same way we design DFA for a
regular grammar. A DFA can remember a finite amount of information, but a PDA can
remember an infinite amount of information. A pushdown automaton is simply an NFA
augmented with an "external stack memory". The addition of stack is used to provide a last-in-
first-out memory management capability to Pushdown automata. Pushdown automata can store
an unbounded amount of information on the stack. It can access a limited amount of information
on the stack. A PDA can push an element onto the top of the stack and pop off an element from
the top of the stack. To read an element into the stack, the top elements must be popped off and
are lost. A PDA is more powerful than FA. Any language which can be acceptable by FA can
also be acceptable by PDA. PDA also accepts a class of language which even cannot be accepted
by FA. Thus PDA is much more superior to FA

Non-regular languages are not accepted by the Finite State machine. So we need another new
model to accept the non-regular languages. That language is called Pushdown Automata (PDA).
It has a stack which is used to remember the input.

 Inserting symbol into the stack is called Push operation

 Removing symbol from the stack is called Pop operation

1
 Pushdown Automata

Basically a pushdown automaton is - "Finite state machine" + "a stack". PDA can remember
infinite amount of information

PDA Components

Input tape: The input tape is divided in many cells or symbols. The input head is read-only and
may only move from left to right, one symbol at a time.

Finite control: The finite control has some pointer which points the current symbol which is to be
read.

Stack: The stack is a structure in which we can push and remove the items from one end only. It
has an infinite size. In PDA, the stack is used to store the items temporarily.

The stack head scans the top symbol of the stack. A stack does two operations -
Push - a new symbol is added at the top.
Pop - the top symbol is read and removed.
A PDA may or may not read an input symbol, but it has to read the top of the stack in every
transition.

2
Definition: PDA is a collection of the seven components

M = (Q, Σ, δ,┌, q0, Z0, F )

Q – finite set of states

Σ – input set

┌ - stack alphabet

q0 – starting state

Z0 - starting symbol in stack which is in ┌

F – set of final state

δ - mapping function

3
A transition function, where δ: Q x (Σ U {ε}) x Г –> finite subsets of Q x Г*
The following diagram shows a transition in a PDA from a state q to state q , labeled as a,b → c

Figure Transition in a PDA

This means at state q , if we encounter an input string ‘a’ and top symbol of the stack is ‘b’, then
we pop ‘b’, push ‘c’ on top of the stack and move to state q .

A pushdown automaton (PDA) is a finite automaton equipped with a stack-based memory. Each
transition is based on the current input symbol and the top of the stack, optionally pops the top of
the stack, and optionally pushes new symbols onto the stack. Initially, the stack holds a special
symbol Z0 that indicates the bottom of the stack.

Non-Deterministic Pushdown Automata (DPDA)

The non-deterministic pushdown automaton is very much similar to NFA. The CFG which
accepts deterministic PDA accepts non-deterministic PDAs as well. Similarly, there are some
CFGs which can be accepted only by NPDA and not by DPDA. Thus NPDA is more powerful
than DPDA.

Consider the various parts of δ: Q x (Σ U {ε}) x Г –> finite subsets of Q x Г* Q & Г on the LHS
means that at each step in a computation, a PDA must consider its’ current state & the symbol on
top of its’ stack. Σ U {ε} on the LHS means that at each step in a computation, a PDA may or
may not consider the current input symbol, i.e., it may have epsilon transitions. “Finite subsets”
on the RHS means that at each step in a computation, a PDA will have several options.

4
  Q on the RHS means that each option specifies a new state.
 Г* on the RHS means that each option specifies zero or more stack symbols that will
replace the top stack symbol, but in a specific sequence.

The arguments of δ are the current state of the control unit, the current input symbol, and the
current symbol on the top of the stack. The result is a set of pairs (q, x) where

 q = next state of the control unit

 x = string that is put on top of the stack in place of the single symbol there before.
The ‘stack’ is an additional component available as part of PDA. The ‘stack’ increases its
memory. With respect to{a nbn | n ≥1}, we can store a’s in the stack. When the symbol ‘b’ is
encountered, an ‘a’ from the stack can be removed. If the stack becomes empty on the
completion of processing a given string, then the PDA accepts the string.

Figure Model of Pushdown Automation

Suppose the set of transition rules of an NPDA contains

δ ε(q1,a,b)={(q2,cd),(q3, ε)

If at any time the control unit is in state q1, the input symbol read is a, and the symbol on top of
the stack is b, then one of two things can happen: (1) the control unit goes into state q2 and the
string cd replaces b on top of the stack, or (2) the control unit goes into state q3 with the symbol
b removed from the top of the stack. In our notation we assume that the insertion of a string into
a stack is done symbol by symbol, starting at the right end of the string.

5
 Deterministic push down automata

The Deterministic Pushdown Automata is a variation of pushdown automata that accepts the
deterministic context-free languages. A language L(A) is accepted by a deterministic pushdown
automata if and only if there is a single computation from the initial configuration until an
accepting one for all strings belonging to L(A). It is not as powerful as non-deterministic finite
automata. That's why it is less in use and used only where determinism is much easier to
implement. A PDA is said to be deterministic if its transition function δ(q,a,X) has at most one
member for

a Σ U {ε}

So, for a deterministic PDA, there is at most one transition possible in any combination of state,
input symbol and stack top.

Figure Deterministic PDA

Definition: A PDA M=(Q,Σ,Γ,δ,q0,z,F)M=(Q,Σ,Γ,δ,q0,z,F) is deterministic if for

1. δ(q,a,b)δ(q,a,b) contains at most one element

2. if δ(q,λ,b)δ(q,λ,b) is not empty, then δ(q,c,b)δ(q,c,b) must be empty.

6
Definition: LL is a deterministic context-free language (DCFL) if and only if there exists a
deterministic PDA MM such that L=L(M)L=L(M).

Figure Regular Language and PDA

Deterministic context free languages(DCFG)
A context-free language (CFL) is a language generated by some context-free grammar (CFG).
Different CF grammars can generate the same CF language, or conversely, a given CF language
can be generated by different CF grammars. The class of context-free languages generalizes the
class of regular languages, i.e., every regular language is a context-free language. The reverse of
this is not true, i.e., every context-free language is not necessarily regular.
Properties of CFL
The context free languages closed under some operation means after performing that particular
operation on those CFLs the resultant language is context free language. Properties are: Here L,
L1 and L2 are considered as CFL

 The context free languages are closed under union L = L1 U L2

 The context free languages are closed under concatenation L = L1 L2
 The context free languages are closed under kleen closure L1 = L1*
 The context free languages are not closed under intersection
 The context free languages are not closed under complement

7
Deterministic context-free languages are a proper subset of context-free languages. Context free
languages that can be accepted by Deterministic Push-Down Automata. DCFLs are always
unambiguous. Many programming languages can be described by means of DCFLs.

They are the subset of context-free grammars that can be derived from deterministic pushdown
automata, and they generate the deterministic context-free languages. DCFGs are
always unambiguous, and are an important subclass of unambiguous CFGs; there are non-
deterministic unambiguous CFGs, however. DCFGs are of great practical interest, as they can be
parsed in linear time and in fact a parser can be automatically generated from the grammar by
a parser generator. They are thus widely used throughout computer science. Various restricted
forms of DCFGs can be parsed by simpler, less resource-intensive parsers, and thus are often
used. These grammar classes are referred to by the type of parser that parses them, and important
examples are LALR, SLR, and LL

8
 Chapter 5
Turing machines
Tuning machine is an abstract machine developed by an English mathematician Alan Turing in
1936. The model of computation provides a theoretical foundation for modern computer. Turing
machine will have.

 A finite set of alphabets

 A finite set of states
 A linear tap which is potential infinite to both end

A Turing Machine is like a Pushdown Automaton. Both have a finite-state machine as a central
component, both have additional storage. A Pushdown Automaton uses a “stack” for storage
whereas a Turing Machine uses a “tape”, which is actually infinite in both the directions. The
tape consists of a series of “squares”, each of which can hold a single symbol. The “tape-head”,
or “read-write head”, can read a symbol from the tape, write a symbol to the tape and move one
square in either direction.

There are two kinds of Turing Machine available.

(a) Deterministic Turing Machine.

(b) Non-deterministic Turing Machine.
A Turing Machine does not read “input”, unlike the other automata. Instead, there are usually
symbols on the tape before the Turing Machine begins, the Turing Machine might read some. all,
or none of these symbols. The initial tape may, if desired, be thought of as “input”. “Acceptors”
produce only a binary (accept/reject) output. “Transducers” can produce more complicated
results. So far all our previous discussions were only with acceptors. A Turing Machine is a
“Transducer” It has the computing capability of general purpose computer. It has the following
features:

 External memory

 Unlimited memory capability

 It reads the input on input tape from left to right

 Its maintaining the difference between the input and output

9
Difference between the other automata and TM

 Unlimited input tape memory

 Unlimited external memory

 Finite control head can move on L to R and R to L

 It can differentiate the input and output by external symbol

 Output can write in the same input tape by external symbol

Turing Machine as Accepter: TM can be considered as Accepting

device.

 Its accepting the set of strings.

 It accepts the family of languages generated by the grammar type-

0 Operation of TM:

 Inputs can keep in the tape from left to right and empty cells are filled with blank
symbol
 Depending upon the transition function it will change from one state to another state
 After reading the input it will replace the input value by the external symbol and It
will move on left or right side based on transition function
 When it reaches the final state, TM will accept the input so its called accepter

Turing Decidable and Turing Acceptable

A TM accepts a language if it enters into a final state for any input string w. A language is
recursively enumerable (generated by Type-0 grammar) if it is accepted by a Turing machine. A
TM decides a language if it accepts it and enters into a rejecting state for any input not in the
language. A language is recursive if it is decided by a Turing machine. There may be some cases
where a TM does not stop. Such TM accepts the language, but it does not decide it.

A language is called Decidable or Recursive if there is a Turing machine which accepts and halts
on every input string w. Every decidable language is Turing-Acceptable.

10
 Undecidable problems
For an undecidable language, there is no Turing Machine which accepts the language and makes
a decision for every input string w (TM can make decision for some input string though). A
decision problem P is called “undecidable” if the language L of all yes instances to P is not
decidable. Undecidable languages are not recursive languages, but sometimes, they may be
recursively enumerable languages.

Example

 The halting problem of Turing machine

 The mortality problem
 The mortal matrix problem
 The Post correspondence problem, etc.

11
 Chapter 6
Computability

Recursive functions

A finite automaton can be seen as a program with only a finite amount of memory. A recursive
automaton is like a program which can use recursion (calling procedures recursively), but again
over a finite amount of memory in its variable space. Note that the recursion, which is typically
handled by using a stack, gives a limited form of infinite memory to the machine, which it can
use to accept certain non-regular languages. It turns out that the recursive definition of a
language defined using a context-free grammar precisely corresponds to recursion in a finite-
state recursive automaton.
Recursive Enumerable (RE) or Type -0 Languages

RE languages or type-0 languages are generated by type-0 grammars. An RE language can be accepted or
recognized by Turing machine which means it will enter into final state for the strings of language and may or may
not enter into rejecting state for the strings which are not part of the language. It means TM can loop forever for
the strings which are not a part of the language. RE languages are also called as Turing recognizable languages.

Recursive languages and recursive Enumerable languages

A language is recursively enumerable (r.e.) if it is the set of strings accepted by some TM. A
language is recursive if it is the set of strings accepted by some TM that halts on every input. For
example, any regular language is recursive.

Recursive Enumerable (RE) or Type -0 Language

RE languages or type-0 languages are generated by type-0 grammars. An RE language can be
accepted or recognized by Turing machine which means it will enter into final state for the
strings of language and may or may not enter into rejecting state for the strings which are not
part of the language. It means TM can loop forever for the strings which are not a part of the
language. RE languages are also called as Turing recognizable languages.

Recursive Language (REC)

A recursive language (subset of RE) can be decided by Turing machine which means it will
enter into final state for the strings of language and rejecting state for the strings which are not

12
 part of the language. e.g.; L= {anbncn|n>=1} is recursive because we can construct a turing
machine which will move to final state if the string is of the form anbncn else move to non-final
state. So the TM will always halt in this case. REC languages are also called as Turing
decidable languages. The relationship between RE and REC languages can be shown in Figure
Closure Properties of Recursive Languages
 Union: If L1 and If L2 are two recursive languages, their union L1𝖴L2 will also be
recursive because if TM halts for L1 and halts for L2, it will also halt for L1𝖴L2.

 Concatenation: If L1 and If L2 are two recursive languages, their concatenation L1.L2 will
also be recursive. For Example:
L1= {anbncn|n>=0}
L2= {dmemfm|m>=0}
L3= L1.L2
= {anbncndm emfm|m>=0 and n>=0} is also recursive.
 L1 says n no. of a’s followed by n no. of b’s followed by n no. of c’s. L2 says m no. of d’s
followed by m no. of e’s followed by m no. of f’s. Their concatenation first matches no. of
a’s, b’s and c’s and then matches no. of d’s, e’s and f’s. So it can be decided by TM.
 Kleene Closure: If L1is recursive, its kleene closure L1* will also be recursive. For
Example:
L1= {anbncn|n>=0}
L1*= { anbncn||n>=0}* is also recursive.
 Intersection and complement: If L1 and If L2 are two recursive languages, their
intersection L1 ∩ L2 will also be recursive. For Example:
L1= {anbncndm|n>=0 and m>=0}
L2= {anbncndn|n>=0 and m>=0}
L3=L1 ∩ L2
= { anbncndn |n>=0} will be recursive.
Recursive languages are accepted by TMs that always halt; i.e. languages are accepted by TMs.
These two families are closed under intersection and union. If a language is recursive, then so is
its complement; if both a language and its complement are r.e., then the language is recursive.
There is a connection with printer-TMs.
1. Recursive Languages:
Recursive languages, also known as decidable languages, are languages for which there exists a Turing machine
that halts on every input and correctly determines whether a given string belongs to the language or not.

13
 We refer to a language L as recursive if there exists a Turing machine T for it. In this case, the Turing machine
accepts every string in language L and rejects all strings that don't match the alphabet of L.
In other words, if string S is part of the alphabet of language L, then the Turing machine T will accept it otherwise
the Turing machine halts without ever reaching an accepting state.

Example:
The language L = {0^n1^n | n ≥ 0} is a recursive language. It consists of all strings with an equal number of 0s
followed by an equal number of 1s. This language can be recognized by a Turing machine that scans the input,
verifies the number of 0s and 1s, and accepts if they are equal.

2. Recursively Enumerable Languages:

Recursively enumerable languages, also known as partially decidable languages, are languages for which there
exists a Turing machine that halts and accepts every string in the language, but may either halt or loop indefinitely
for strings not in the language. In other words, there may not be a guarantee of rejection for strings not in the
language.

Here if there is a Turing machine T that accepts a language L, the language in which an enumeration procedure
exists is referred to as a recursively enumerable language. Note that some recursive languages are enumerable and
some enumerable languages are recursive.

Example:
The language L = {w#w | w is a string over {0, 1}*} is recursively enumerable. It consists of all strings of the form
w#w, where w is a string over the alphabet {0, 1}* and # is a separator symbol. This language can be recognized
by a Turing machine that scans the input and verifies if the string is of the form w#w. The TM can accept the string
if it matches the pattern, but it may loop indefinitely if the pattern is not present.

It's important to note that all recursive languages are recursively enumerable, as a Turing machine can simply
accept every string in the language and reject all others. However, there are recursively enumerable languages that
are not recursive, as they may not have a Turing machine that halts and rejects strings not in the language.

Recursive languages are considered to be a subset of recursively enumerable languages, representing a stricter
class of computable languages where both acceptance and rejection are guaranteed. Recursively enumerable
languages, on the other hand, encompass a broader class where acceptance is guaranteed, but rejection may not
always be determinable.
RECURSIVELY ENUMERABLE /
RECURSIVE / TURING DECIDABLE TURING RECOGNIZABLE
FACTOR LANGUAGES) LANGUAGES)
Examples Context-sensitive languages RE languages.
Halt-accept, Halt-Reject, Infinite Loop(No
States Halt-Accept, Halt-Reject halting)
Looping Finite loops Possibility of infinite loop
Accept/ Accept (Turing machine) = L, Reject (Turing Accept (Turing machine) = LReject
reject machine) = L, Loop (Turing machine) = φφ, (Turing machine) + Loop (Turing machine)

14
 RECURSIVELY ENUMERABLE /
RECURSIVE / TURING DECIDABLE TURING RECOGNIZABLE
FACTOR LANGUAGES) LANGUAGES)
φ = null φ = null = L’

15
 Chapter-7
Computational complexity
What Is Big O Notation?
Big O notation is a mathematical notation used in computer science to describe the upper bound or worst-case
scenario of the runtime complexity of an algorithm in terms of the input size. It provides a standardized and
concise way to express how the performance of an algorithm scales as the size of the input grows.

In simpler terms, Big O notation helps us understand how an algorithm's efficiency changes as the amount of
data it processes increases. It focuses on the dominant factor influencing an algorithm's runtime, ignoring
constant factors and lower-order terms. This makes it a powerful tool for comparing and analyzing algorithms
without getting bogged down in implementation details.

Big O Notation Is Important For:

1. Algorithm Efficiency Comparison: This allows us to compare the efficiency of different algorithms for
solving the same problem. We can quickly determine which one will perform better for large input sizes by
looking at the Big O notation of two algorithms.

2. Predicting Algorithm Behavior: Big O notation helps us predict how an algorithm will perform as the input
data grows. This is crucial for understanding algorithms' scalability and ensuring they can efficiently handle
larger datasets.

3. Optimizing Code: Understanding the Big O complexity of an algorithm is essential for optimizing code. By
identifying complex algorithms, developers can focus on improving those parts of the codebase to make their
software more efficient.

4. Resource Management: Big O notation is also relevant for resource management, especially in resource-
constrained environments such as embedded systems or server environments. It helps developers make
informed decisions about memory usage, processing power, and other resources.

5. Problem-Solving Approach: When solving complex problems, knowing the Big O complexity of different
algorithms can guide the selection of appropriate data structures and algorithms. This helps devise efficient
solutions to real-world problems.

POLYNOMIAL TIME REDUCTION AND NP-COMPLETE PROBLEMS

If P1 and P2 are two problems and P2 P, then we can decide whether P1 P by relating the
two problems P1 and P2. If there is an algorithm for obtaining an instance of P2 given any instance of P1, then
we can decide about the problem P1. Intuitively if this algorithm is a polynomial one, then the problem P1 can
be decided in polynomial time.

Definition: Let P1 and P2 be two problems. A reduction from P1 to P2 is an algorithm which converts an
instance of P1 to an instance of P2. If the time taken by the algorithm is a polynomial p(n), n being the length of
the input of P1, then the reduction is called a polynomial reduction P1 to P2.

16
Best, Average, Worst, Expected Complexity

In this table:

 Complexity Best Case Average Case Worst Case Expected Case

O(1) O(1) O(1) O(1) O(1)

O(log n) O(1) O(log n) O(log n) O(log n)

O(n) O(n) O(n) O(n) O(n)

O(n log n) - O(n log n) O(n log n) O(n log n)

O(n^2) - O(n^2) O(n^2) O(n^2)

O(2^n) - - O(2^n) O(2^n)

O(n!) - - O(n!) O(n!)

Best Case: Represents the minimum time or space required by the algorithm for any input. It's often an
optimistic scenario.

 Average Case: Represents the expected time or space required by the algorithm averaged over all possible
inputs. It provides a more realistic estimation of performance.

 Worst Case: Represents the maximum time or space required by the algorithm for any input. It's often a
pessimistic scenario.

17
There are two kinds of measures with Complexity Theory: (a) time and (b) space.

(i) Time Complexity: It is a measure of how long a computation takes to execute. As far as
Turing machine is concerned, this could be measured as the number of moves which are
required to perform a computation. In the case of a digital computer, this could be measured
as the number of machine cycles which are required for the computation.

(ii) Space Complexity: It is a measure of how much storage is required for a computation. In
the case of a Turing machine, the obvious measure is the number of tape squares used, for a
digital computer, the number of bytes used. It is to be noted that both these measures
functions of a single input parameter, viz., “size of the input”, which is defined in terms of
squares or bytes. For any given input size, different inputs require different amounts of space
and time. Thus it will be easier to discuss about the “average case” or for the “worst case”.

Class P vs class NP

The P versus NP problem is to determine whether every language accepted by some

nondeterministic algorithm in polynomial time is also accepted by some (deterministic)
algorithm in polynomial time. To define the problem precisely it is necessary to give a formal
model of a computer. The standard computer model in computability theory is the
Turing machine, introduced by Alan Turing in 1936. Although the model was introduced
before physical computers were built, it nevertheless continues to be accepted as the proper
computer model for the purpose of defining the notion of computable function.

Informally the class P is the class of decision problems solvable by some algorithm within a
number of steps bounded by some fixed polynomial in the length of the input. Turing was not
concerned with the efficiency of his machines, but rather his concern was whether they can
simulate arbitrary algorithms given sufficient time. However it turns out Turing machines can
generally simulate more efficient computer models (for example machines equipped with
many tapes or an unbounded random access memory) by at most squaring or cubing the
computation time. Thus P is a robust class, and has equivalent definitions over a large class of
computer models.

18
What are P and NP Problems?

P (polynomial time) refers to the class of problems that can be solved by an algorithm in
polynomial time. Problems in the P class can range from anything as simple as multiplication to
finding the largest number in a list. They are the relatively ‘easier’ set of problems.
NP (non-deterministic polynomial time) refers to the class of problems that can be solved in
polynomial time by a non-deterministic computer. This is essentially another way of saying “If I
have unlimited compute power (i.e. as many computers as I need), I am capable of solving any
problem in at most polynomial time”. More intuitively though, it refers to the class of problems
that currently, has no way of finding a quick (polynomial time) enough answer, BUT can be
quickly verified (in polynomial time) if one provides the solution to the problem. The term
verified here means that one is able to check that the solution provided is indeed correct.
Facts about P Problems

 P problems are set of problems which can be solved in polynomial time by deterministic
algorithms.
 The problem belongs to class P if it’s easy to find a solution for the problem.
 P Problems can be solved and verified in polynomial time.
 P problems are subset of NP problems.
 It is not known whether P=NP. However, many problems are known in NP with the
property that if they belong to P, then it can be proved that P=NP.
 All P problems are deterministic in nature.
 Example: Selection sort, linear search
Facts about NP-Class Problems

 NP problems are the problems which can be solved in non-deterministic polynomial time.
 The problem belongs to NP, if it’s easy to check a solution that may have been very
tedious to find.
 Solution to NP problems cannot be obtained in polynomial time, but if the solution is
given, it can be verified in polynomial time.
 If P≠NP, there are problems in NP that are neither in P nor in NP-Complete.
 NP problems are superset of P problems.

19
  All the NP problems are non-deterministic in nature.
 Example TSP, Knapsack problem.
What is the difference between P vs NP?
P = the set of problems that are solvable in polynomial time by a Deterministic Turing Machine.
NP = the set of decision problems (answer is either yes or no) that are solvable in
nondeterministic polynomial time i.e can be solved in polynomial time by a Nondeterministic
Turing Machine.

P PROBLEMS NP PROBLEMS
P problems are set of problems which can be solved in
polynomial time by deterministic algorithms. NP problems are the problems which can be solved in
non-deterministic polynomial time.
The problem belongs to NP, if it’s easy to check a solution
The problem belongs to class P if it’s easy to find a that may have been very tedious to find.
solution for the problem.
Solution to NP problems cannot be obtained in polynomial
P Problems can be solved and verified in polynomial time, but if the solution is given, it can be verified in
time. polynomial time.
P problems are subset of NP problems. NP problems are superset of P problems.
It is not known whether P=NP. However, many problems
are known in NP with the property that if they belong to
P, then it can be proved that P=NP. If P≠NP, there are problems in NP that are neither in P
nor in NP-Complete.
All the NP problems are non-deterministic in nature.
All P problems are deterministic in nature.

Selection sort, linear search TSP, Knapsack problem.

Polynomial time reduction and NP-complete problems

A decision problem is NP-hard if the time complexity on a deterministic machine is within a

polynomial factor of the complexity of any problem in NP. A problem is NP-complete if it is
NP-hard and in NP. Cook’s theorem proved SATISFIABILITY was NP-hard by using a
polynomial time reduction translating each problem in NP into an instance of SAT:

Polynomial-time reduction: We now take this intuition of reducing one problem to another
through the use of a subroutine call, and place it on more formal footing. NP-completeness: The
set of NP-complete problems are all problems in the complexity class NP, for which it is known

20
 that if anyone is solvable in polynomial time, then they all are, and conversely, if anyone is not
solvable in polynomial time, then none are. This is made mathematically formal using the notion
of polynomial time reductions.

The theory of NP-completeness is based on formal languages and Turing machines, and so we
will must work on a more abstract level than usual. For a given alphabet of symbols Σ =0, 1, &,
we can form an infinite set of strings or words by arranging them in any order: ‘&10’,
‘111111’,‘&&&’, and ‘&’. A subset of the set of strings over some alphabet is a formal
language. Formal language theory concerns the study of how powerful a machine you need to
recognize whether a string is from a particular language.

Cook’s Theorem

Cook’s Theorem proves that satisfiability is NP-complete by reducing all non-deterministic

Turing machines to SAT. Each Turing machine has access to a two-way infinite tape (read/write)
and a finite state control, which serves as the program.

Cook’s theorem is usually stated as:

Any problem in NP can be reduced in polynomial time by a deterministic Turing machine to

the problem of determining whether a formula in CNF is satisfiable (SAT).
However, the original statement of Cook’s theorem was presented in Cook’s paper entitled “The complexity of
theorem proving procedures as :
Theorem 1 If a set S of strings is accepted by some nondeterministic Turing machine within
polynomial time, then S is P-reducible to { DNF tautologies}.
The main idea of the proof of Theorem 1 was described as:

Suppose a nondeterministic Turing machine M accepts a set S of strings within time Q(n), where Q(n) is a
polynomial. Given an input w for M, we will construct a propositional formula A(w) in conjunctive normal form
(CNF) such that A(w) is satisfiable iff M accepts w. Thus :A(w) is easily put in disjunctive normal form (using De
Morgans laws), and :A(w) is a tautology if and only if w 62 S. Since the whole construction can be carried out in
time bounded by a polynomial in j w j (the length of w), the theorem will be proved.Here S refers to a set of all
instances of an NP problem that have solutions, and finding the tautology of :A(w) in DNF is transformed into
finding the satisfiability of A(w) in CN.

21
In general, Cook’s Theorem Can be described as

A program for a non-deterministic TM is:

1. Space on the tape for guessing a solution and certificate to permit verification.

2. A finite set of tape symbols

3. A finite set of states Θ for the machine, including the start state q0 and final states Zyes, Zno

4. A transition function, which takes the current machine state, and current tape symbol and
returns the new state, symbol, and head position. We know a problem is in NP if we have a
NDTM program to solve it in worst-case time p[n], where p is a polynomial and n is the size of
the input.

22