Is it Easier to Prove Theorems that are Guaranteed to be True?

Rafael Pass, Muthuramakrishnan Venkitasubramaniam

Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in NP imply the existence of one-way functions?, or (b) Does a hard-o…