HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How do you prove that polynomial reductions are not symmetric?

Submitted by: @import:stackexchange-cs··
0
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.