# Tag Info

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.
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 \$...