Amitabh Saxena

2005-11-19 04:19:18 UTC

Permalink

Suppose I have computational problems A and B which both seem to beRaw Message

hard but problem A appears to be harder than problem B. For

instance, I can reduce B to A using an oracle but not the other way

round. Is there any way to prove this for sure (say by constructing a

decisional problem C using A and B and than proving that if A reduces

to B than C is easy)

I wanted to know if there are any mathematical tool (eg. like random

oracle model) to prove that some problem is provably NOT as hard as

other problem.

Essentially, I want to prove the "opposite" of what normally the random

oracle model is used for (to prove that a given problem is as hard as

some other problem).

I would appreciate if someone can point me in the right direction on

how to prove that one problem is definitely EASIER than the other,

although both of them are computationally hard.