Can you solve it? The word game at the cutting edge of computer science

A crossword puzzle with a twist

UPDATE: You can read the solutions here

Today's puzzle illuminates one of the smash hits of theoretical computer science, a mind-boggling result that left even experts in the field gobsmacked.

We'll get to that result (the PCP theorem) later. But first, to the challenge!