np complete

Question 0

Traveling salesman Decision problem

Answer 0

Name: Traveling salesman decision problem

Instance: a set of n cities and integer distance d(i,j) between each pair of cities i, j and a target integer k

Question: is there a permutation P of 1 to n such that d(p1,p2) to d(dn,d1) <= k

Question 1

Hamiltonian Cycle

Answer 1

name Hamiltonian cycle
instance: a graph G
Question : does G contain a cycle that visits each vertex exactly once?

Question 2

clique problem

Answer 2

name: clique problem
instance: a graph G and a target integer k
Question: does G contain a clique of size k
(edge between all vertices)

Question 3

Graph coloring problem

Answer 3

Name: Graph coloring problem

Instance: a graph G and a target integer k

Question: can one of k colors be attached to each vertex of G so that adjacent vertices always have different colors