Math Help Forum

Math Help Forum Feed Site Feed

Go Back   Math Help Forum > University Math Help > Advanced Applied Math
Reply
 
Thread Tools Display Modes
  #1  
Old October 6th, 2009, 02:29 AM
Newbie
 
Join Date: Oct 2009
Posts: 5
Thanks: 0
Thanked 0 Times in 0 Posts
jacquelinek is on a distinguished road
Default About "One-way function"

---------------------------------------------------------------------
Suppose a function F satisfies 2 properties:
F(x) is computable within polynomial time,
Computing F^(-1)(x) (the inverse function) is exponential-time hard.
Then can F be considered a one-way function or not?
---------------------------------------------------------------------
I've looked up the definition of one-way function, but I don't think the definition requires inverse function. The definition is, as I know,: Given a y, then it is not feasible to find the corresponding x value.
In addition, shouldn't the inverse function be expressed as F^(-1)(y)? Or this is not the point of this problem?

Please offer me some advice.
Reply With Quote
Advertisement
 
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are Off
Pingbacks are Off
Refbacks are Off
Forum Jump


All times are GMT -7. The time now is 08:51 AM.


Powered by vBulletin® Version 3.7.3
Copyright ©2000 - 2010, Jelsoft Enterprises Ltd.
SEO by vBSEO 3.2.0 ©2008, Crawlability, Inc.
©2005 - 2009 Math Help Forum


Math Help Forum is a community of maths forums with an emphasis on maths help in all levels of mathematics.
Register to post your math questions or just hang out and try some of our math games or visit the arcade.