World's most popular travel blog for travel bloggers.

polynomial time reduction of 2 langauges

, , No Comments
Problem Detail: 

If we can reduce a language y to x.

x ≤P y

how do I prove

 x(complement) ≤P  y (complement) 
Asked By : Swathi
Answered By : David Richerby

The definition of many-one reducibility means that, if you've proven that $X\leq Y$, you get $\overline{X}\leq\overline{Y}$ for free.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback