For each of the following prove if its true or false 1. For subset-sum when the

Question

For each of the following prove if its true or false

1. For subset-sum when the number n is coded by n consecutive 1 (for example 6 is coded 111111) the problem is polynomial time solvable in the size of the input.

2. The following problem is NPC. Give a graph G a number k and a bound p, the question asks if there exists a subset UV (U subset V) of size k so that the number of edges between the vertices of U is at most b.

3. The problem that asks if a graph has both an Hamiltonian path and contains a clique of size k is NPC.

4. We are given a problem in which the number of candidates solutions is 2^2^n. Then the problem is decidable

Explanation / Answer

Answer:)

3. True

A graph with a clique of size k is NPC.

A graph with Hamilton path is NPC.

So, if a graph has both then the graph is definitely NPC.

4. False

2^2^n is a value not a yes or no answer, therefore, it is not decidable.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.