# The problems in the P class can be polynomially reduced to its complement and vica versa?

I considered the Euler circle problem to decide this. The polynomial reduction is: I add a new vertex in the graph:

• If the degree of each vertex is even, then I connect all the vertices with this new vertex
• Otherwise, I only connect the vertices with an odd number of degrees to the new vertex Is this a correct reduction?
• Can you clarify the question? Are you looking for a reduction from the problem of deciding whether a graph contains an Eulerian cycle to its complement, or are you interested in knowing whether all problems in NP can be reduced to their respective complements? Jan 28 at 9:30
• I try to prove that every P problems can be reduced to its complements and the opposite direction is also true. For this purpose I used the Euler circuit problem. Jan 28 at 9:37
• Does this answer your question? Does two languages being in P imply reduction to each other? Jan 28 at 10:31
• Please, before asking a question, make sure that you search if it, or something very similar, already exists on the site. Jan 28 at 10:48

The claim is false. $$\emptyset$$ cannot be reduced to its complement $$\Sigma^*$$ (and vice-versa).
However, if you restrict yourself to languages $$L$$ such that $$L \not\in \{ \emptyset, \Sigma^*\}$$ then it is true that $$L \le \overline{L}$$. To see this let $$n$$ be any fixed element of $$L$$ and let $$y$$ be any fixed element of $$\overline{L}$$. Such elements exist by our choice of $$L$$.
The reduction is given by: $$f(x) = \begin{cases} y & \mbox{if } x \in L \\ n & \mbox{if } x \not\in L \end{cases}.$$ Notice that $$f$$ can be computed in polynomial time since $$L \in \mathsf{P}$$, which means that we can decide in polynomial time whether $$x \in L$$.