PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
hard core (Definition)

If $ f$ is a function and $ R$ is a polynomial time computable relation, we say $ R$ is a hard-core of $ f$ if for any probabilistic, polynomial time computable relation $ S$ and any polynomial function $ p$, there is some $ m$ such that for all $ n>m$:

$\displaystyle \operatorname{Pr}[S(f(x))=R(x)]<\frac{1}{p(n)}$

In particular, if $ f$ is one-to-one polynomial time computable then $ f$ is one-way, since if it were not $ f$ could be reversed to find $ x$, and then $ R(x)$ calculated (since $ R$ is polynomial time computable).



"hard core" is owned by Henry.
(view preamble)

View style:

Other names:  hard-core

Cross-references: one-way, one-to-one, polynomial function, relation, computable, polynomial time, function

This is version 1 of hard core, born on 2002-09-15.
Object id is 3459, canonical name is HardCore.
Accessed 3890 times total.

Classification:
AMS MSC68Q30 (Computer science :: Theory of computing :: Algorithmic information theory )

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
rate | post | correct | update request | add derivation | add example | add (any)