Define \Delta^{1}(n)=P(n+1)-P(n)$and \Delta^{i}(n)=\Delta^{i-1}(n+1)-\Delta^{i-1}(n)$ for $i>1$. Since $P(n)$ has degree at most 2012, we know that \Delta^{2012}(n)$is constant. Computing, we obtain \Delta^{1}(0)=2-P(0)$ and \Delta^{i}(0)=2^{i-1}$for$1<i \leq 2012$. We see that continuing on gives \Delta^{2012}(0)=\Delta^{2012}(1)=P(0)$ and \Delta^{i}(2012-i)=2^{2013-i}$for$1 \leq i \leq 2011$. Then,$P(2013)=$$P(2012)+\Delta^{1}(2012)=\ldots=P(2012)+\Delta^{1}(2011)+\ldots+\Delta^{2012}(0)=P(0)+2^{2013}-2$. Now, we want to minimize the value of$P(0)^{2}+P(2013)^{2}=2 P(0)^{2}+2 P(0)\left(2^{2013}-2\right)+\left(2^{2013}-2\right)^{2}$, but this occurs simply when$P(0)=-\frac{1}{2}\left(2^{2013}-2\right)=1-2^{2012}$.