Self reductions

Question 1

polynomial turing reduction

Answer 1

We will say that L2 ≤tp L2 if given a black box solution A for L1, we can write a polynomial algorithm M that solves L2 using calling A a number of times.

Question 2

Self reduction

Answer 2

Given an algorithm A for validating a problem. We will show an algorithm B for solving the problem using A.

Question 3

Largest Clique self reduction

Answer 3

1. Use binary or exhaustive search for finding the number k (largest clique) possible.
2. For every node Vi, try taking it out and seeing if there still is the largest clique, if yes, then Vi isn’t in it and continue, if no then it is in the largest clique.

Question 4

3 Color self reduction

Answer 4

Add a triangle to the graph where the nodes simulate r,g,b. Now, for every node in the original graph. connect it to the r node in the triangle. If A now returns true then you need to check if it is blue or green by connecting it. If it is false than it is red, Do this for the entire graph.