[Solved]: If A is in P and B is non-trivial, then A ≤p B

Problem Detail: 

On wikipedia's article on Polynomial-time reduction it states:

Every nontrivial decision problem in P (the class of polynomial-time decision problems, where nontrivial means that not every input has the same output) may be reduced to every other nontrivial decision problem, by a polynomial-time many-one reduction. To transform an instance of problem A to B, solve A in polynomial time, and then use the solution to choose one of two instances of problem B with different answers

Some looking into the history of this entry reveals a link to math.SE that was referenced as a proof at one time.

However I am still confused as to exactly how this works. I understand polynomial-time reductions but there are some specific questions I have in regards to this statement.

1. Is it required that A is non-trivial as stated on wikipedia? Some places seem to suggest that the requirement is only B has to be non-trivial, and A doesn't matter if trivial or non-trivial. Based on this question.

2. Can someone provide me a concrete example of this working. I don't quite understand how there are two instances of problem B with different answers and how it relies on problem A to choose

Asked By : ParoX

Answered By : jmite

First, it's important to realize here that the output of a decision problem will always be "Yes" or "No." So what this is saying is basically that $B$ has at least two inputs $x,y$ where $x \in L_B$ and $y \not \in L_B$, if $L_B$ is the set (language) of all accepted inputs to $B$.

Let's let $B$ be SAT. We'll take two instances, $x = v_1 \vee \neg v_1$, which has a solution and thus is in SAT, and $y = v_1 \wedge \neg v_1$.

Let's let $A$ be the undirected graph-connectivity problem. We know that we can solve this in polynomial time using Breadth First Search.

So, given a graph $G$ as input to $A$, we'll define a function $f$:

$f(G) = x$ if $BFS(G)$ returns connected

$f(G) = y$ if $BFS(G)$ returns not connected

Clearly, we can compute $f(G)$ in linear time for any graph, since it's just a breadth-first search. Moreover, we see that $G$ is connected if and only if $f(G) \in SAT$.

The whole process is kind of trivial (in the mathematical sense), because we're basically saying "If we could solve $B$ in polynomial time, we could also solve $A$ in polynomial time". But we can always solve $A$ in polynomial time, so the whole thing is trivially true.

It holds for the same reason $P \implies \top$ is always true.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33964

3.2K people like this

 Download Related Notes/Documents