8
$\begingroup$

Is it possible to convert any problem in P to any other problem in P in polynomial time?

$\endgroup$
1
  • 2
    $\begingroup$ Consider an empty language $\endgroup$ Apr 20, 2020 at 20:39

1 Answer 1

14
$\begingroup$

If by convert you mean reduce (through a Karp-reduction), then it is possible to reduce any problem $A$ in $P$ to any non-trivial problem $B$ in $P$.

Here "non trivial" means that $B$ has at least one yes instance $I_Y$ and at least one no instance $I_N$ (i.e., the language associated to $B$ is not $\emptyset$ nor $\Sigma^*$).

To map an instance $I_A$ of $A$ to an instance $I_B$ of $B$ simply solve $A$ using a polynomial-time algorithm. If $I_A$ is a yes instance let $I_B = I_Y$, otherwise let $I_B = I_N$.

It is not possible to reduce any problem $A \in P$ to any problem $B \in P$. To see this let $A$ be a non-trivial problem and let $B$ be a trivial problem. Two possible languages corresponding to $A$ and $B$ are $\{ \varepsilon \}$ and $\emptyset$, respectively.

$\endgroup$
6
  • 1
    $\begingroup$ What. I don't get this argument. When I think of "reduce A to B", then in my mind we map a problem instance of A to a problem instance of B in polynomial time, solve the B problem and by that get a solution to A. Do you intend to say that the polytime mapping is: run A, then map to some fixed B instance depending on the outcome? In other words, inside the same class of problems, you can map everything to everything by just solving the original problem as part of the mapping? $\endgroup$
    – kutschkem
    Apr 21, 2020 at 6:26
  • $\begingroup$ @kutschkem $I_B$ has an answer when the mapping is made whether you know it or not. So I'm not sure that there is meaningful distinction between mapping to a fixed $B$ instance or a different one, given that the answers correspond to those to $A$ instances appropriately. As a concrete example, let $A$ be the problem of whether a given element exists in some list, an $B$ be whether an integer is even or not. Once you've chosen an integer corresponding to $I_A$, the answer is determined, whether you always pick $1$ and $0$ or somehow encode the list as a number. $\endgroup$
    – Ryan1729
    Apr 21, 2020 at 9:04
  • $\begingroup$ @kutschkem, exactly. Solve $I_A$ (the instance of $A$), and map $I_A$ to one of two fixed instances of $B$ depending on the outcome. As you say, inside $P$ you can reduce any problem to any non-trivial problem by solving the first problem in polynomial-time as part of the reduction. $\endgroup$
    – Steven
    Apr 21, 2020 at 9:53
  • 3
    $\begingroup$ @kutschkem I remember having the same confusion that you did. The idea behind performing reductions is that the amount of computational power you allow in the reduction needs to be lower than the amount of computational power you allow when solving the problem. If your reduction can do a polynomial amount of work, then your reduction could be "just solve the problem and output the answer." $\endgroup$ Apr 21, 2020 at 18:54
  • 2
    $\begingroup$ @Konchog Keep in mind that we are talking about decision problems and that a Karp reduction from $A$ to $B$ only shows that $B$ is "at least as hard as" $A$ up to polynomial factors. This concept of reduction is not fine-grained enough to give any information about the hardness of problems in $P$. $\endgroup$
    – Steven
    Apr 22, 2020 at 8:55

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.