perfectcomplete

Perfectcomplete is a term used in computational complexity theory to describe a property of certain proof and verification systems: perfect completeness. This means that for every statement that is true within the considered language, there exists a witness or proof that makes the verifier accept with probability 1. In other words, the completeness parameter is 1.

In classical models, the notion appears in discussions of Merlin-Arthur games and interactive proof systems, where the variant with completeness 1 is sometimes denoted with a subscript 1, such as MA1 or IP1. In the quantum realm, the analogue is often referred to as QMA1, the quantum version of MA with perfect completeness. The use of perfect completeness highlights a strict requirement: true statements must be provably verifiable with certainty, not just with bounded probability.

The study of perfect completeness touches questions about the power and limitations of different proof systems. Researchers examine whether protocols can be transformed to achieve perfect completeness without altering the class of languages they recognize, and how such transformations impact completeness and soundness parameters. In some models, achieving perfect completeness is known or believed possible under certain assumptions or transformations; in others, whether it can be done without changing computational power remains an area of investigation.

Although perfectcomplete is not a formal name used for a single widely recognized class on its own, it appears as shorthand in discussions about the presence or absence of perfect completeness in various proof and verification frameworks. See also completeness, soundness, interactive proof systems, MA1, QMA1, and IP1.