snippetMinor
How do you prove that polynomial reductions are not symmetric?
Viewed 0 times
symmetricyoupolynomialareprovethathowreductionsnot
Problem
How would I go about showing that L $\leq_p$ L' does not necessarily imply L' $\leq_p$ L? I was thinking I should show an example of two problems, where one can reduce to the other but not the other way round, but am not sure what such problems could be.
Solution
You have a good plan of approach. Now you need to spend some more time pursuing this. Try to come up with a list of languages $L$ you've seen before, and try different pairs to see if they satisfy the condition. After some trial and error you should be able to solve your problem.
Context
StackExchange Computer Science Q#58084, answer score: 4
Revisions (0)
No revisions yet.