Computer-Aided Verification of P/NP Proofs: A Survey and Discussion

Abstract

We survey a collection of proofs towards equality, inequality, or independence of the relation of P to NP. Since the problem has attracted much attention from experts, amateurs, and in-betweens, this work is intended as a pointer into directions to enable a “self-assessment” of ideas laid out by people interested in the problem. To this end, we identify the most popular approaches to proving equality, inequality, or independence. Since the latter category appears to be without any attempts to follow the necessary proof strategies, we devote a Section to an intuitive outline of how independence proofs would work. In the other cases of proving equality or inequality, known barriers like (affine) relativization, algebrization, and others are to be avoided. The most important and powerful technique available in this regard is a formalization of arguments in automated proof assistants. This allows an objective self-check of a proof before presenting it to the scientific community.

Keywords

• P/NP question
• proofs
• barriers
• relativization
• proof assistants