Register to reply

Negligible function question.

by Alteran
Tags: function, negligible
Share this thread:
Alteran
#1
Mar15-06, 12:47 AM
P: 19
There is a question:

In constructing obfuscators for point-functions theory, there is a statement that there exists a polynomial-time computable permutation
[tex]pi : B^n -> B^n[/tex] and a constant c such that for every polynomial s(n) and every adversary A of size s for all sufficiently large n,

[tex] Prob[A(pi(x)) = x] <= S(n)^c/2^n [/tex]

I am trying to prove that
[tex]S^c(n)/2^n[/tex]
where s is a polynomial and c is a constant, is also a negligible function.

Could anyone help me with that?
Phys.Org News Partner Science news on Phys.org
Climate change increases risk of crop slowdown in next 20 years
Researcher part of team studying ways to better predict intensity of hurricanes
New molecule puts scientists a step closer to understanding hydrogen storage

Register to reply

Related Discussions
Question about a function General Math 6
A question about an odd function.. Calculus & Beyond Homework 2
Function Question Calculus 2
How far away from earth before the pull is negligible? Classical Physics 5
How to derive the electric field between parallel plates of negligible separation? General Physics 2