>tfw just proved P = NP
let $A$ be connected graph such that $P$ has a truth table of size $2^{o(\alpha^2)}$. Then $A$ has a truth table of size $2^{o(\alpha^2)}$. We can assume w.l.o.g. that $A$ has no isolated vertices and only one (isolated) cycle. If there are only $p$ components that are not Hamiltonian then, since $A$ has a single cycle, there exists a connected component with at least $p$ vertices. Now, let us define a truth table $\mathcal{T}$ for $A$. In the truth table $\mathcal{T}$, there is exactly one row in each of the $p$ connected components, $x_1x_2\ldots x_p$: the truth table is made with the labels in $V\backslash\{x_1,\ldots,x_p\}$ and the $x_i$ in the truth table correspond to the vertices in the connected component. Since $P$ has a truth table of size $2^{o(\alpha^2)}$ we can have, without loss of generality, the $x_i$ corresponding to the vertices on the cycle (since $P$ does not have isolated cycles). For each of the $p$ rows we label the vertices corresponding to the $x_i$ with $1$ (true) and the other vertices with $0$ (false).
By following each of the first $p$ rows of $\mathcal{T}$ we see that one of the $p$ vertices $x_i$ satisfies $\bigwedge_{1\leq i \leq p}x_i=1$ (since we must make a truth table for each connected component). Now, since $A$ is connected, we must have that $x_i=x_j$ for all $i,j\in \{1,\ldots,p\}$: the $p$ vertices $x_i$ must be identical. This gives us that $x_1x_2\ldots x_p=1$ and, since $A$ has a single cycle, $1$ is a truth table of size $2^{o(\alpha^2)}$ of $A$ contradicting that $P$ is a truth table NP-complete, therefore P = NP.
let $A$ be connected graph such that $P$ has a truth table of size $2^{o(\alpha^2)}$. Then $A$ has a truth table of size $2^{o(\alpha^2)}$. We can assume w.l.o.g. that $A$ has no isolated vertices and only one (isolated) cycle. If there are only $p$ components that are not Hamiltonian then, since $A$ has a single cycle, there exists a connected component with at least $p$ vertices. Now, let us define a truth table $\mathcal{T}$ for $A$. In the truth table $\mathcal{T}$, there is exactly one row in each of the $p$ connected components, $x_1x_2\ldots x_p$: the truth table is made with the labels in $V\backslash\{x_1,\ldots,x_p\}$ and the $x_i$ in the truth table correspond to the vertices in the connected component. Since $P$ has a truth table of size $2^{o(\alpha^2)}$ we can have, without loss of generality, the $x_i$ corresponding to the vertices on the cycle (since $P$ does not have isolated cycles). For each of the $p$ rows we label the vertices corresponding to the $x_i$ with $1$ (true) and the other vertices with $0$ (false).
By following each of the first $p$ rows of $\mathcal{T}$ we see that one of the $p$ vertices $x_i$ satisfies $\bigwedge_{1\leq i \leq p}x_i=1$ (since we must make a truth table for each connected component). Now, since $A$ is connected, we must have that $x_i=x_j$ for all $i,j\in \{1,\ldots,p\}$: the $p$ vertices $x_i$ must be identical. This gives us that $x_1x_2\ldots x_p=1$ and, since $A$ has a single cycle, $1$ is a truth table of size $2^{o(\alpha^2)}$ of $A$ contradicting that $P$ is a truth table NP-complete, therefore P = NP.
