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 '20 at 20:39
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 '20 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 '20 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 '20 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 '20 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 '20 at 8:55

Your Answer

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

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