patternModerate
Can any problem in P be converted to any other problem in P in polynomial time?
Viewed 0 times
problemcanpolynomialanytimeotherconverted
Problem
Is it possible to convert any problem in P to any other problem in P in polynomial time?
Solution
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.
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.
Context
StackExchange Computer Science Q#124446, answer score: 14
Revisions (0)
No revisions yet.