Favorite Theorem 6

Favorite Theorem 6

• Ogiwara and Watanabe:
  • If P ¹ NP then there are no sparse sets hard for NP via polynomial bounded truth-table reductions.
• Proof uses new technique of “left-sets”, a step function based on lexicographically least witness.

Previous slide

Next slide

Back to the first slide

View Graphic Version

Homer-Longpre - clearer proof with stronger bounds.

Relationships between one-way functions and iso conjecture including relativization results--see proceedings.