Explain the difference among decision problem, counting problem and

search problem with examples

ANS:
A decision problem is a computational problem where the answer for every instance is either yes or
no. An example of a decision problem is primality testing:
"Given a positive integer n, determine if n is prime."
A decision problem is typically represented as the set of all instances for which the answer is yes.
For example, primality testing can be represented as the infinite set
L = {2, 3, 5, 7, 11, ...}
In a search problem, the answers can be arbitrary strings. For example, factoring is a search problem
where the instances are (string representations of) positive integers and the solutions are (string
representations of) collections of primes.
A search problem is represented as a relation consisting of all the instance-solution pairs, called
a search relation. For example, factoring can be represented as the relation
R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}
which consist of all pairs of numbers (n, p), where p is a nontrivial prime factor of n.
A counting problem asks for the number of solutions to a given search problem. For example, a
counting problem associated with factoring is
"Given a positive integer n, count the number of nontrivial prime factors of n."
A counting problem can be represented by a function f from {0, 1}* to the nonnegative
integers. For a search relation R, the counting problem associated to R is the function
fR(x) = |{y: R(x, y) }|.

4. Define any THREE of the following terms and give

examples/explanations of each: a. Intractable problem b. NP-complete
Problems c. Travelling Salesman Problem (TSP) d. Hamiltonian Path
Problem e. Approximation algorithm

a. Intractable problems: From a computational complexity stance, intractable problems are

problems for which there exist no efficient algorithms to solve them.

Most intractable problems have an algorithm – the same algorithm – that provides a solution, and
that algorithm is the brute-force search. This algorithm, however, does not provide an efficient
solution and is, therefore, not feasible for computation with anything more than the smallest input.
The reason there is no efficient algorithms for these problems is that these problems are all in a
category which I like to refer to as “slightly less than random.” They are so close to random, in fact,
that they do not as yet allow for any meaningful algorithm other than that of brute-force. If any
problem were truly random, there would not be even the possibility of any such algorithm.

EXAMPLE #1: Factoring a number into primes. It is the security provided by the lack of any efficient
algorithm to solve this problem that allows RSA and public key encryption to be so widely accepted
and successful.

EXAMPLE #2: SAT, the satisfiability problem to test whether a given Boolean formula is satisfiable.
All sets of input must be tried systematically (brute-force) until a satisfying case is discovered.

b. NP-complete problem: Any of a class of computational problems for which no efficient

solution algorithm has been found. Many significant computer-science problems belong to
this class—e.g., the traveling salesman problem, satisfiability problems, and graph-covering
problems.

So-called easy, or tractable, problems can be solved by computer algorithms that run in
polynomial time; i.e., for a problem of size n, the time or number of steps needed to find the
solution is a polynomial function of n. Algorithms for solving hard, or intractable, problems, on
the other hand, require times that are exponential functions of the problem size n. Polynomial-
time algorithms are considered to be efficient, while exponential-time algorithms are
considered inefficient, because the execution times of the latter grow much more rapidly as the
problem size increases. A problem is called NP (nondeterministic polynomial) if its solution can
be guessed and verified in polynomial time; nondeterministic means that no particular rule is
followed to make the guess. If a problem is NP and all other NP problems are polynomial-time
reducible to it, the problem is NP-complete. Thus, finding an efficient algorithm for any NP-
complete problem implies that an efficient algorithm can be found for all such problems, since
any problem belonging to this class can be recast into any other member of the class. It is not
known whether any polynomial-time algorithms will ever be found for NP-complete problems,
and determining whether these problems are tractable or intractable remains one of the most
important questions in theoretical computer science. When an NP-complete problem must be
solved, one approach is to use a polynomial algorithm to approximate the solution; the answer
thus obtained will not necessarily be optimal but will be reasonably close.

c. The travelling salesman problem: (also called the traveling salesperson problem or TSP)
asks the following question: "Given a list of cities and the distances between each pair of
cities, what is the shortest possible route that visits each city exactly once and returns to the
origin city?". It is an NP-hard problem in combinatorial optimization, important in
theoretical computer science and operations research.

The travelling purchaser problem and the vehicle routing problem are both generalizations of
TSP.

Description:
As a graph problem:
Symmetric TSP with four cities

TSP can be modelled as an undirected weighted graph, such that cities are the graph's vertices,
paths are the graph's edges, and a path's distance is the edge's weight. It is a minimization problem
starting and finishing at a specified vertex after having visited each other vertex exactly once. Often,
the model is a complete graph (i.e., each pair of vertices is connected by an edge). If no path exists
between two cities, adding a sufficiently long edge will complete the graph without affecting the
optimal tour.
Asymmetric and symmetric

In the symmetric TSP, the distance between two cities is the same in each opposite direction,
forming an undirected graph. This symmetry halves the number of possible solutions. In
the asymmetric TSP, paths may not exist in both directions or the distances might be different,
forming a directed graph. Traffic collisions, one-way streets, and airfares for cities with different
departure and arrival fees are examples of how this symmetry could break down.
Related problems:

An equivalent formulation in terms of graph theory is: Given a complete weighted graph (where the
vertices would represent the cities, the edges would represent the roads, and the weights would be
the cost or distance of that road), find a Hamiltonian cycle with the least weight.

The requirement of returning to the starting city does not change the computational complexity of
the problem, see Hamiltonian path problem.

Another related problem is the Bottleneck traveling salesman problem (bottleneck TSP): Find a
Hamiltonian cycle in a weighted graph with the minimal weight of the weightiest edge. For example,
avoiding narrow streets with big buses. The problem is of considerable practical importance, apart
from evident transportation and logistics areas. A classic example is in printed
circuit manufacturing: scheduling of a route of the drill machine to drill holes in a PCB. In robotic
machining or drilling applications, the "cities" are parts to machine or holes (of different sizes) to
drill, and the "cost of travel" includes time for retooling the robot (single machine job sequencing
problem).

The generalized travelling salesman problem, also known as the "travelling politician problem",
deals with "states" that have (one or more) "cities" and the salesman has to visit exactly one "city"
from each "state". One application is encountered in ordering a solution to the cutting stock
problem in order to minimize knife changes. Another is concerned with drilling
in semiconductor manufacturing, see e.g., U.S. Patent 7,054,798. Noon and Bean demonstrated that
the generalized travelling salesman problem can be transformed into a standard travelling
salesman problem with the same number of cities, but a modified distance matrix.

The sequential ordering problem deals with the problem of visiting a set of cities where precedence
relations between the cities exist.

A common interview question at Google is how to route data among data processing nodes; routes
vary by time to transfer the data, but nodes also differ by their computing power and storage,
compounding the problem of where to send data.

The travelling purchaser problem deals with a purchaser who is charged with purchasing a set of
products. He can purchase these products in several cities, but at different prices and not all cities
offer the same products. The objective is to find a route between a subset of the cities, which
minimizes total cost (travel cost + purchasing cost) and which enables the purchase of all required
products.

d. Hamiltonian path problem: In the mathematical field of graph theory the Hamiltonian
path problem and the Hamiltonian cycle problem are problems of determining whether
a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly
once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both
problems are NP-complete.

Hamiltonian Path is a path in a directed or undirected graph that visits each vertex exactly once.
The problem to check whether a graph (directed or undirected) contains a Hamiltonian Path is NP-
complete, so is the problem of finding all the Hamiltonian Paths in a graph. Following images
explains the idea behind Hamiltonian Path more clearly.
Graph shown in Fig.1 does not contain any Hamiltonian Path. Graph shown in Fig. 2 contains two
Hamiltonian Paths which are highlighted in Fig. 3 and Fig. 4
Following are some ways of checking whether a graph contains a Hamiltonian Path or not.

A Hamiltonian Path in a graph having N vertices is nothing but a permutation of the vertices of the
graph [v1, v2, v3, ......vN-1, vN] , such that there is an edge between vi and vi+1 where 1 ≤ i ≤ N-1. So
it can be checked for all permutations of the vertices whether any of them represents a Hamiltonian
Path or not. For example, for the graph given in Fig. 2 there are 4 vertices, which means total 24
possible permutations, out of which only following represents a Hamiltonian Path.
0-1-2-3
3-2-1-0
0-1-3-2
2-3-1-0

e. Approximation algorithm: An approximation algorithm is a way of dealing with NP-

completeness for an optimization problem. The goal of the approximation algorithm is to
come close as much as possible to the optimal solution in polynomial time.

Some examples of Approximation algorithm:

Here, we will discuss some examples of the Approximation Algorithm as follows.

The Vertex Cover Problem: In the vertex cover problem, the optimization problem is to select a
minimum number of vertices that should cover all the edges in a graph.

Travelling Salesman Problem: In the Travelling Salesman Problem, the optimization problem is
that the salesman has to take a route that has a minimum cost.

The Set Covering Problem: This is an optimization problem that models many problems that
require resources to be allocated. Here, a logarithmic approximation ratio is used.

The Subset Sum Problem: In the Subset sum problem, the optimization problem is to find a subset
of {x1,×2,×3…xn} whose sum is as large as possible but not larger than target value t.