Is an obviously-correct obviously-PTIME algorithm in a programming language a proof of polynomial time reduction? This is about NP and NP-completeness. I want to prove that language $L_1$ is polynomial time reducible to $L_2$.
If I describe both languages as two sets of strings and write a program or a function in a programming language that takes string $S_1$ as input and outputs/returns $S_2$ iff $S_1 \in L_1$ and otherwise returns error or throws an exception or halts otherwise without returning a string in $L_2$, does it count as proof?
 A: In order to show a reduction from $L_1$ to $L_2$, you need to do three things:


*

*Describe a mapping $f$ from $L_1$ instances to $L_2$ instances.

*Prove that this mapping preserves the desired answer -- that is, that $f(x)\in L_2$ if and only if $x\in L_1$.

*Show that $f$ can be computed in polynomial time.


For some reductions, part 1 is all you really need to write down, because parts 2 and 3 are obvious once one understands what the mapping does.
It is also common to need to do parts 1 and 2 explicitly, but that step 3 is still obvious enough to be left to the reader's imagination.
Finally, there are cases where part 3 needs actual ingenuity, such that you have to not only explain how the output relates to the input, but also how you actually manage to perform that transformation in polynomial time. The most common way to do this is to describe an algorithm using pseudocode, but in principle there is nothing wrong with using an actual programming language instead.
Note, however, that programs written in real programming languages tend to be more verbose than pseudocode. They often need to spend much breath on details that a human reader would be perfectly able to imagine on his own (say, on memory management, the mechanics of traversing a graph/tree in a particular order you need to traverse it in, or the precise parsing and formatting of problem instances), such that it becomes harder to grasp the actually important idea behind the argument. As such, pseudocode will often result in a better proof than using a real programming language (where "better" refers to how much effort a knowledgeable reader needs to expend to convince himself that your claim is true, guided by the proof you've written down). However, claiming that an actual program "will not be taken seriously" (as a now-deleted answer did) is taking that much too far.
In principle, a program (or pseudocode) could also serve to fulfill part 1 of the plan. But this is rarely a good idea, because that will often just make part 2 harder -- in order to convince someone that the reduced problem instance has the correct answer you will almost always need a more higher-level description of what it is, rather than just step-by-step instructions for how to create it.
