# Tag Info

I assume $X,Y$ and $Z$ are languages. Now if a language $A$ is polynomial-time reducible to another language $B$ this means there exists a function $f$ that can be computed in $O(n^k)$ such that: $$p\in A \iff f(p) \in B$$ Now if such a function $f_{xy}$ exists for $X$ and $Y$ and such a function $f_{yz}$ for $Y$ and $Z$, you can construct a new function $... 1 It's true: Assume$Y\in NP$. Now let$N$be the poly time verifier for$Y$. Lets also call the poly time reduction$\phi$. Then, notice that$x\in X\iff\phi(x)\in Y\iff \exists w.N(\phi(x),w)$. Therefore, let us build the poly time verifier for$X$as follows:$M(x,w):$Compute$\phi(x)$in poly time Emulate$N(\phi(x),w)$and accept if and only if$N\$ ...