0
$\begingroup$

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?
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Steven
    Jan 28 at 9:30
  • $\begingroup$ 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. $\endgroup$
    – Andrew19
    Jan 28 at 9:37
  • 1
    $\begingroup$ Does this answer your question? Does two languages being in P imply reduction to each other? $\endgroup$ Jan 28 at 10:31
  • 1
    $\begingroup$ Please, before asking a question, make sure that you search if it, or something very similar, already exists on the site. $\endgroup$ Jan 28 at 10:48

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.