1
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Think about the definition of NP-complete. ​ ​ $\endgroup$
    – user12859
    Commented Aug 22, 2016 at 9:06
  • $\begingroup$ Q2. The definition states that for an NPC Problem p, all problems can be reduced into it in Polynomial time. So, the blowup on the size of problem would thus be only polynomial (correct me if i am wrong)? But, if that is the case then for any NPC problem (in theory) could be transformed into say Knapsack Problem (or something similar) and we can get a good approximation using an FPTAS Algorithm and convert the approximation back to the Orignial Problem. Hence, every NPC problem is in FPTAS. Which includes Strong NPC. But, strong NPC have FPTAS iff P=NP. Hence, P=NP ?! what am i missing. $\endgroup$
    – TheoryQuest1
    Commented Aug 22, 2016 at 9:26
  • $\begingroup$ There's 2 independent points here: ​ ​ ​ It's not "all problems" that "can be reduced into it in Polynomial time." ​ Unless we were just talking about approximation problems or specify otherwise, reductions do not need to be approximation-preserving. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Aug 22, 2016 at 9:32
  • 1
    $\begingroup$ ("all NP problems can be reduced into it in Polynomial time" is the definition of NP-hard, not NPC.) ​ Let A be subset sum and let B be circuit-SAT, where the value of an assignment is [if it satisfies the circuit then the circuit's size else zero]. ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Aug 22, 2016 at 10:02
  • 1
    $\begingroup$ Nice picture I made. $\endgroup$
    – adrianN
    Commented Aug 22, 2016 at 10:05

1 Answer 1

Reset to default
3
$\begingroup$

  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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ yes. I agree. So of course, there is a reduction in both directions, and there is a polynomial increase/decrease in problem size in each case. The part i am struggling is, say we have a good approximation for A, we can tranform B to A, approximate it, and get the approximation back for B (just like in case of complete solutions). I know, as stated that reductions are not necessarily 'approximation preserving'. But, i am trying to understand why (with help of a nice example), where inapproximation results are known. $\endgroup$
    – TheoryQuest1
    Commented Aug 22, 2016 at 10:31
  • 2
    $\begingroup$ @TheoryQuest1 Well, that's a completely different thing and it should be asked as a new question. $\endgroup$
    – David Richerby
    Commented Aug 22, 2016 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.