We construct a PCP for NTIME(2n) with constantsoundness, 2n\poly(n) proof length, and \poly(n)queries where the verifier's computation is simple: thequeries are a projection of the input randomness, and thecomputation on the prover's answers is a 3CNF. Theprevious upper bound for these two computations waspolynomial-size circuits. Composing this verifier with aproof oracle increases the circuit-depth of the latter by2. Our PCP is a simple variant of the PCP byBen-Sasson, Goldreich, Harsha, Sudan, and Vadhan (CCC2005). We also give a more modular exposition of thelatter, separating the combinatorial from the algebraicarguments.

If our PCP is taken as a black box, we obtain a moredirect proof of the result by Williams, later withSanthanam (CCC 2013) that derandomizing circuits on nbits from a class C in time 2nn(1) yieldsthat NEXP is not in a related circuit class C. Ourproof yields a tighter connection: C is an And-Or ofcircuits from C. Along the way we show that the samelower bound follows if the satisfiability of the And ofany 3 circuits from C can be solved in time2nn(1) .