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 answersSome 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.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.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
If A is in P and B is non-trivial, then A p B
complexity theory;time complexity;reductions;polynomial time
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 connectedClearly, 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.