Gate 01
QuestionThe black-box test
Would each key step still work if every machine could ask the same black box for answers?
Name the first step that would stop. If no step stops, the method may hit the relativization barrier.
A kind first check
Test your proof first
These checks can save you and your readers time. A pass does not show that a proof is right. A fail can show that a method cannot work as written. Ask a specialist if you are not sure.
Three barriers
Gate 02
QuestionThe natural-proof test
Does your circuit test rule out small circuits, run fast on a truth table, and accept many random functions?
If all three answers are yes, say how your proof avoids the natural proofs barrier. This check rests on a stated hardness assumption.
Gate 03
QuestionThe polynomial black-box test
Would each key step still work if the black box also gave low-degree polynomial values away from Boolean inputs?
Name the extra fact your proof uses. Low degree alone is not enough. If no key step breaks, the method may hit the algebrization barrier.
Two gates from the Deolalikar review
Gate 04
QuestionDoes the narrow model cover all of P?
Did you limit the kind of machine or logic that your proof studies?
If so, prove that the narrow model still covers every method in P. Also prove that the change keeps the feature used by your lower bound.
Gate 05
QuestionDoes the sign of hardness also show up in an easy problem?
Does your proof say that a shape, cluster, frozen value, or rough search space makes a problem hard?
Run the same test on an easy case such as XOR-SAT. Check it again after each lift, map, or promise used by the proof.
Eight more warning signs
Scott Aaronson wrote a short list of signs that help a reader choose what to check first. They are warning signs, not proofs that a claim is wrong. Read “Eight Signs A Claimed P≠NP Proof Is Wrong”.
If your proof clears these first checks, see how to submit a claim.