TOC UNIT-5

Author:Tagore
Co-Author:Nanaji
1. Collect and write short notes on P and NP-Complete problems

A.

1. P (Polynomial Time):
o Problems that can be solved by an algorithm in polynomial
time (i.e., their running time grows at most polynomially with the
input size).
o Examples of polynomial algorithms include constant-
time (O(1)), linear-time (O(n)), and quadratic-time (O(n^2))
algorithms.
o These problems are considered “efficient” because their
execution time remains reasonable even for large inputs.
2. NP-Complete:
o A subset of NP problems that are especially hard.
o A problem p is NP-complete if every other problem in NP can
be reduced to p in polynomial time.
o In other words, if we can solve an NP-complete problem
efficiently, we can solve all NP problems efficiently.
o The classic example of an NP-complete problem is the Boolean
satisfiability problem (SAT).
o Other NP-complete problems include the vertex cover problem,
the 3-coloring problem, and the subset sum problem.

2.What is a post-correspondence problem? Explain with an example

A.

1. Post Correspondence Problem (PCP):

o The Post Correspondence Problem is an undecidable problem
introduced by Emil Leon Post in 1946.
o It is simpler than the famous Halting Problem.
o In PCP, we have a set of dominos (tiles), each with a numerator
and a denominator.
o The goal is to arrange these dominos in a sequence such that the
concatenation of the numerators matches the concatenation of
the denominators.
2. Example:
o Consider two lists of dominos:
▪ List A: { 1, 10111, 10 }
 ▪List B: { 111, 10, 0 }
o We want to find a sequence of dominos such that the
concatenated strings from the numerators match the
concatenated strings from the denominators.
o Let’s analyze the solution step by step:
1. Start with the second tile (2):
▪ Numerator: 10111
▪ Denominator: 10
2. Add the first tile ( 2, 1):
▪ Numerator: 101111
▪ Denominator: 10111
3. Add the third tile (2, 1, 3):
▪ Numerator: 10111110
▪ Denominator: 101111110
4. Final solution: 2, 1, 1, 3
▪ Numerator: 101111110
▪ Denominator: 101111110
o As you can see, the strings match, so this sequence solves the
PCP for these lists.
3. Undecidability of PCP:
o The PCP is undecidable, meaning there is no algorithm that can
determine whether any given Post Correspondence System has a
solution or not.

3. What is the Halting Problem of the Turing Machine? Is it decidable or not?

Explain
A.
1. Halting Problem:
o The Halting Problem is a fundamental concept in the field
of computability theory.
o It revolves around the question: Given a program (or algorithm),
will it ever halt (terminate) when run on a specific input, or will it
run indefinitely
o In other words, can we design an algorithm that can predict
whether a given program will halt or not?
2. Undecidability:
o Alan Turing proved that the Halting Problem is undecidable.
o What does this mean? No algorithm exists that can correctly
determine whether any arbitrary program will halt or not for all
possible program-input pairs.
o Even though we can run a program and observe its behavior, there
is no general algorithm that can predict this behavior in advance.
3. Proof by Contradiction:
 o Let’s assume that we have a magical machine called HM (Halt
Machine) that, given a program P and an input I, can tell us
whether P will always halt on input I or not.
o Now, consider feeding HM with its own description (i.e., HM itself)
and an input I.
o If HM says that HM halts on input I, then it should halt. But what if
it doesn’t halt? That’s a contradiction!
o Similarly, if HM says that HM doesn’t halt on input I, then it should
not halt. But what if it does halt? Another contradiction!
o Therefore, we conclude that no such magical machine HM can
exist

4. Explain about Universal Turing machine

A.
1. Definition:
o A UTM is a Turing machine that can simulate any other Turing
machine.
o It is capable of computing any computable sequence.
o The key insight is that we can encode the description of a Turing
machine using a finite-length binary string. This string represents
information about the state space, alphabet, and transition
function of the TM.
2. How It Works:
o Imagine a UTM as a “meta” Turing machine that takes two inputs:
▪ The description of another Turing machine (encoded as a
binary string).
▪ An input for that Turing machine.
o The UTM simulates the behavior of the specified Turing machine
using its own transition rules.
o It processes the input according to the simulated machine’s rules
and produces the same output as the simulated machine would.
o In essence, the UTM acts as a universal emulator for all possible
Turing machines.
3. Significance:
o The UTM concept is foundational in computer science and theory
of computation.
o It demonstrates that there exists a single machine capable of
performing any computation that can be described
algorithmically.
o The UTM is a theoretical construct, but it underpins the idea of
modern computers and their ability to execute diverse programs

5. Explain about Chomsky Hierarchy of languages?

A.
The Chomsky hierarchy is a fundamental concept in formal language theory,
computer science, and linguistics. It classifies formal grammars into four
distinct types, each capable of generating increasingly complex languages.

1. Regular (Type-3) Grammars:

o These grammars generate regular languages.
o Recognizing automaton: Finite-state automaton (either right
regular or left regular).
o Production rules: Simple rules with the form A → αB or A → α,
where A and B are non-terminals, and α is a string of terminals
and/or non-terminals.
o Example: Regular expressions and regular languages.
2. Context-Free (Type-2) Grammars:
o These grammars generate context-free languages.
o Recognizing automaton: Non-deterministic pushdown
automaton.
o Production rules: Of the form A → α, where A is a non-terminal,
and α is a string of terminals and/or non-terminals.
o Example: Programming languages’ syntax, XML, and context-free
languages.
3. Context-Sensitive (Type-1) Grammars:
o These grammars generate context-sensitive languages.
o Recognizing automaton: Linear-bounded non-deterministic
Turing machine.
o Production rules: More flexible than context-free grammars,
allowing context-dependent transformations.
o Example: Natural languages, certain compiler optimizations, and
context-sensitive languages.
4. Recursively Enumerable (Type-0) Grammars:
o These grammars generate recursively enumerable languages.
o Recognizing automaton: Turing machine (possibly non-
terminating).
o Production rules: No restrictions; can encode any computable
function.
o Example: All computable languages, including both decidable and
undecidable problems.

6. Write short notes on the following

 i) Post-correspondence problem
ii) Halting problem

A.

1. Post Correspondence Problem (PCP):

o The Post Correspondence Problem is an undecidable problem
introduced by Emil Leon Post in 1946.
o It is simpler than the famous Halting Problem.
o In PCP, we have a set of dominos (tiles), each with a numerator
and a denominator.
o The goal is to arrange these dominos in a sequence such that the
concatenation of the numerators matches the concatenation of
the denominators.

Halting Problem:

• The halting problem deals with determining, from a description of an

arbitrary computer program and an input, whether the program will
eventually halt or run forever.
• Key points:
o The problem is undecidable; no general algorithm can solve it for
all program–input pairs.
o Turing machines are often used to formalize the problem.
o The essence of Turing’s proof is that any algorithm attempting to
solve this problem can be made to produce contradictory output.
• Universal Halting Problem: Determines whether a given program halts
for every input.

7. a)Solve the post-correspondence problem for the data given in the following table.
A B
1 1 111
2 10111 10
3 10 0
A.
o Consider two lists of dominos:
▪ List A: { 1, 10111, 10 }
▪ List B: { 111, 10, 0 }
o We want to find a sequence of dominos such that the
concatenated strings from the numerators match the
concatenated strings from the denominators.
o Let’s analyze the solution step by step:
1. Start with the second tile (2):
▪ Numerator: 10111
▪ Denominator: 10
 2. Add the first tile ( 2, 1):
▪ Numerator: 101111
▪ Denominator: 10111
3. Add the third tile (2, 1, 3):
▪ Numerator: 10111110
▪ Denominator: 101111110
4. Final solution: 2, 1, 1, 3
▪ Numerator: 101111110
▪ Denominator: 101111110
o As you can see, the strings match, so this sequence solves the
PCP for these lists.

b) Write briefly about Decidability and undecidability problems

A.

1. Decidability:
o A problem is considered decidable if there exists an algorithm
that can always produce the correct answer (either “yes” or “no”)
for any given input.
o In other words, a decidable problem can be solved by a Turing
machine that halts on every input, providing a definitive answer.
o Examples of decidable problems include:
▪ Checking whether two regular languages are equivalent
(using set difference operations).
▪ Determining membership of a context-free language (using
dynamic programming algorithms).
▪ Verifying the emptiness of a context-free language by
examining its production rules.
2. Undecidability:
o Undecidable problems are those for which no algorithm can
provide a correct answer in finite time.
o While some problems may be partially decidable (or semi-
decidable), they will never be fully decidable.
o An undecidable problem may lead a Turing machine into an
infinite loop without ever providing an answer.
o Intuitively, these problems challenge our understanding of
computation and reveal inherent limitations.
o Examples of undecidable problems include:
▪ The halting problem, where determining whether a program
halts for a given input is impossible to solve algorithmically.
▪ Fermat’s Last Theorem, which states that no three positive
integers can satisfy the equation: (a^n + b^n = c^n) for any
(n > 2). Proving this theorem is undecidable
8. What are P and NP class of Languages? What is NP-Complete and give examples?

A.
1. P (Polynomial Time):
o The class P consists of decision problems that can be solved by
a deterministic Turing machine in polynomial time.
o In other words, if a problem is in P, there exists an efficient
algorithm that can solve it in a reasonable amount of time.
o Examples of problems in P:
▪ Checking whether a given number is prime.
▪ Sorting an array of elements.
▪ Finding the shortest path in a graph using Dijkstra’s
algorithm.
2. NP (Nondeterministic Polynomial Time):
o The class NP contains decision problems for which a non-
deterministic Turing machine can verify a solution in polynomial
time.
o While finding the solution itself might be hard, verifying a
proposed solution is relatively easy.
o Examples of problems in NP:
▪ The Traveling Salesman Problem: Given a list of cities and
distances between them, find the shortest route that visits
each city exactly once and returns to the starting city.
▪ The Satisfiability Problem (SAT): Given a Boolean formula,
determine if there exists an assignment of truth values to
variables that makes the formula true.
3. NP-Complete:
o A problem is NP-complete if it satisfies two properties:
▪ It is in NP (i.e., solutions can be verified quickly).
▪ Every problem in NP can be reduced to it in polynomial
time.
o If any NP-complete problem can be solved in polynomial time,
then all problems in NP can be solved efficiently.
o Examples of NP-complete problems:
▪ Hamiltonian Cycle: Given an undirected graph, find a cycle
that visits every vertex exactly once.
▪ Vertex Cover: Given a graph, find the smallest set of
vertices such that every edge is incident to at least one
vertex in the set.
▪ 3-Satisfiability (3-SAT): Given a Boolean formula in
conjunctive normal form (CNF), determine if there exists an
assignment of truth values to variables that satisfies all
clauses.

9. How to determine whether a problem is NP-Hard or P? Illustrate with an

example.
A.
1. P (Polynomial Time):
o Problems in the class P are those that can be solved efficiently by
a deterministic Turing machine in polynomial time.
o If an algorithm exists that solves a problem in P, it means the
problem can be efficiently solved.
o Examples of P problems include sorting, searching, and matrix
multiplication.
2. NP-Hard:
o A problem is considered NP-Hard if it is at least as hard as the
hardest problems in NP (non-deterministic polynomial time).
o In other words, solving an NP-Hard problem would allow us to
solve any problem in NP using a polynomial-time reduction.
o NP-Hard problems may not necessarily be in NP themselves.
o Examples of NP-Hard problems include the Traveling Salesman
Problem (TSP), Subset Sum, and the Turing Halting Problem.
3. Illustrative Example: Traveling Salesman Problem (TSP):
o Problem Statement:
▪ Given a set of cities and distances between them, find the
shortest route that visits each city exactly once and returns
to the starting city.
o Complexity:
▪ TSP is in NP because given a proposed solution (a tour), we
can verify in polynomial time whether it satisfies the
constraints (visiting each city once and returning to the
starting city).
▪ TSP is also NP-Hard because any NP problem can be
reduced to TSP in polynomial time.
o Reduction:
▪ Suppose we have an NP problem (let’s call it Problem Q).
▪ We construct an instance of TSP using Problem Q as
follows:
▪ Each city in TSP corresponds to an instance of
Problem Q.
▪ The distance between cities represents the
relationship between instances of Problem Q.
▪ If Problem Q has a solution, we set the distance to 1;
otherwise, we set it to a large value.
▪ Solving TSP for this constructed instance is equivalent to
solving Problem Q.
o Conclusion:
▪ Since TSP is both in NP and NP-Hard, it is NP-Complete.