Also note that I haven't taken into account 2-coboundaries here, so the above should be taken to read that there is some representative of the cohomology class $[\zeta]$ such that $\zeta(q,p) +\zeta(qp^{-1}q^{-1}, qp)$ is divisible by $n$ for all $q \in Q, p \in Q'$. Adding a coboundary to the preceding expression changes it by $b(p)+ b(qp^{-1}q^{-1})$ for some 1-cochain (i.e., function) $b\colon Q \to \mathbb{Z}$. Interestingly, the latter expression only depends on the restriction of $b$ to $Q'$.

Ah, in fact, here's a slightly cleaner sufficient condition: $\zeta(q_1,q_2)$ should be divisible by $n$ whenever at least one of $q_1,q_2$ is in $Q'$.

@EdwardCooper: Indeed :). I think there may be some fiddling one can do by trying to relate the final condition to the 2-cocycle condition, which might lead to a "cleaner" condition. For example, by playing a bit, you can get that it's equivalent to have $\zeta(q,p) + \zeta(qp^{-1} q^{-1}, qp)$ divisible by $n$ for all $q \in Q, p \in Q'$. This might seem a little "more plausible", since in both of the terms here, at least one of the arguments is in $Q'$... (using the cocycle condition with $a_0=qp^{-1}q^{-1}$, $a_1=qp$, $a_2=q^{-1}$)

Typo: $Q$ -> $Q'$ in "$\zeta'' \in H^2(Q;\mathbb{Z})$." Also, you're assuming that there exists a $\zeta''$ such that $n \zeta'' = \zeta'$, right? Given $\zeta'$, such $\zeta''$ need not always exist...

It depends what the question meant by "effective proof". If they meant "there is an algorithm but you can't find it" - then I agree with you, this isn't really possible. But even universal search (or better: using universal search to find optimal circuits for SAT, and then using the optimal circuits instead, to cut down the potentially large overhead of universal search) can only find the best algorithm that exists. If that algorithm still take time $n^{10^{10^{10}}}$, it's still not "effective" (in the other sense of the word).

@GilKalai: I do not think P versus NP is the formulation - even morally - of the idea that certain algorithms require exponential time. The latter question is essentially P vs EXP, where we've known the answer for half a century. I think P versus NP is much closer to the formalization of the question of whether some algorithmic problems require brute force search (which is, conjecturally, just a small subset of EXP). However, perhaps the more relevant point is that whatever P vs NP formalizes, it is "just" a flagship conjecture indicative of a huge number of related open conjectures.

@AndrewMacFie: Not just because interesting proofs teach us how to prove other things, but also because interesting proofs suggest to us other interesting questions that we might seek proofs for. Even in the most optimistic of P=NP scenarios, the issue of formulating interesting and useful questions would still be left to mathematicians.