Objective of the theorem: Find a hardcore predicate for a one-way function.
A hardcore predicate is a concept in cryptography that is related to the security of one-way functions. One-way functions are functions that are easy to compute in one direction but computationally difficult to invert. A hardcore predicate is a function that is hard to predict even when the value of the one-way function is known.
Note: In computational complexity theory, problems are classified into various complexity classes based on how efficiently they can be solved by algorithms. The polynomial hierarchy is a structure that extends the classes P and NP to higher levels of complexity.
The polynomial hierarchy is organized into levels: , , , , , , and so on. Each level contains problems that are "harder" to solve than the levels below it. The third level of the polynomial hierarchy is represented as and .
The Goldreich-Levin Theorem: Let be a function from to such that there exists a nondeterministic finite automaton (NFA) with input bits and states that accepts with probability , where is a polynomial in . Then, unless the polynomial hierarchy collapses to its third level, there is no efficient (i.e., polynomial-time) algorithm that approximates significantly better than the trivial algorithm.
Note: I've been away for a while, very happy to announce thoughtForest (opens in a new tab) is now live!