22. Name some of the NP problems.
(a) Travelling salesman problem
(b) Hamiltonian Circuit problem.
23. What is the TSP problem?
“A salesman starting in a certain city, wants the visit every capital
city in a country, returning to the city where he started. In what order
should be visit the capital cities so as to minimize the total distance
travelled?” This is the TSP.
24. Mention a remarkable characteristic of all NP Problems.
All NP problems are reducible to one another.
25. Is P = NP?
No one has proved or disproved that P = NP.
244
Theory of Automata, Formal Languages and Computation