The question is from my complexity-theory course.

Explain the concept of polynomial reduction between problems and explain how, and under what circumstances, lower bound and upper bound problems can be determined.

My attempt:

a problem $A$ can be polynomial reduced to $B$ if given an instance $a:A$ an istance $b:B$ can be built such that $a$ is true and $b$ is true.

A decision problem $P_1$ is Karp-reducible to a problem $P_2$ ( $P_1 \leq_m P_2) %$ if and only if exists an algorithm $R$ such that it transforms every instance $x \in I_{P_1}$ if and only if $y \in > I_{P_2}$. $R$ is the Karp-reduction from $P_1$ to $P_2$

One particular case of Karp-reducibility is the polynomial Karp-reducibility:

$P_1$ is polynomial Karp-reducible to $P_2$ ( $P_1 \leq^p_m P_2$) if and only if $P_1$ is Karp-reducible to $P_2$ and the reduction $R$ is an algorithm that runs in polynomial time.

In most cases the complexity of a solution given a particular problem isn't known. For example when we have a huge gap between the lower bound and upper bound. A tipycal situation could be the case of problems when their best lower bound known is $\Omega(n\log n)$ or $\Omega(n^2)$, however the most efficient algorithm has $O(c^n)$ complexity, for $c>1$. In those case the above concepts could be important tools in order to find the complexity relation to different problems.

  • $\begingroup$ You need to give a little more context and detail about your reasoning. As it is now, the question in impossible to answer. $\endgroup$ – Raphael Sep 3 '17 at 18:10
  • $\begingroup$ @Raphael just added more context and my attempt to solve the question. $\endgroup$ – Nick Sep 3 '17 at 19:55
  • $\begingroup$ Thanks for the edit! Hint: consider different directions of reduction. $\endgroup$ – Raphael Sep 3 '17 at 19:57
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Sep 4 '17 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.