11/15/2004 CSC 486 : Hem-Ogi 2.1 Proof… contradiction As L is in UP, but cannot be in P, then it must be the case that P  UP This gives us our result: One-to-one one way functions exist ) P  UP We have (quickly) shown both directions of the bi-conditional Thus we've proven point 2 of Thm.
{}