2

Intuitively, pseudorandom functions are functions that look random. A linear function $f$ satisfies $$ f(x+y) = f(x)+f(y) $$ for all $x,y$, which is highly unlikely for a random function. Similarly, an affine function $f$ satisfies $$ f(x+y) - f(x+z) = f(y) - f(z) $$ for all $x,y,z$, which is highly unlikely for a random function.


1

I'm assuming that both $A$ and $B$ are decision problems and that we are talking bout Karp reductions. Suppose towards a contradiction that $A \not\in NP$, $A \le_p B$, and $B \in NP$. Then, a non-deterministic polynomial-time Turing machine that decides $A$ would be the following: Use the Karp reduction $f$ from $A$ to $B$ to transform an instance $x$ of $...


Only top voted, non community-wiki answers of a minimum length are eligible