World's most popular travel blog for travel bloggers.

Query regarding the structure of Graph over All (known/unknown) NPC Problems?

, ,
Problem Detail:

Let us consider the set of all NPComplete problems. Since every problem in the set is Reducible to/from at least one known NPComplete problem, lets create a directed Graph with the following conventions:

1. If a problem B is Reducible from Problem A, create an edge from A to B. We assume an oracle who knows all possible reductions who creates the edges.

Here are a few questions regarding the Graph.

Q1. Is the graph strongly connected (i.e. every problem in the Graph is reachable from or reducible from every other problem for every instance?

Guess: I presume the answer is yes.

Q2. For any two problems (say A, B), no matter what the distance b/w them is, there is guaranteed at most Polynomial Blowup in problem size when we reduce, from A to B?

Guess: Unsure. For any problem P, if we reduce from one of its neighboring problem, there is polynomial increase or decrease in space. But, not sure if it holds if the problems are arbitrarily large distance apart. The definition of NPC, needs one single reduction in Polynomial time, but space analogue of reduction for All NPC Problem pairs seems out of reach.

1. The definition of NP-complete is that the problem is in NP and every problem in NP (including every other NP-complete problem) is reducible to that problem. So the graph you describe is not only strongly connected: it is a complete graph.

2. By the above, the distance between any two problems is 1. But, even if you follow a longer path of $k$ reductions, where the $i$th has polynomial blow-up $p_i$, the total blow-up for an input of size $n$ is $p_k(p_{k-1}(\cdots p_1(n)\cdots))$, which is still a polynomial.