Proof Systems with Advice and Instance Complexity

18 concepts4 papers2 proposals

In classical computational complexity, we typically evaluate the hardness of a problem by its worst-case performance on inputs of a given length. However, this approach often misses a deeper, more granular reality: some specific instances of a problem are inherently harder to solve or verify than others, regardless of their size.

To understand this variation, researchers have connected proof complexity (the length of the shortest proof of a statement) with computational complexity (the time or resources needed to compute a solution). A particularly powerful framework for exploring this connection involves augmenting traditional proof systems with advice—auxiliary, non-uniform information that helps a verifier validate a proof more efficiently. By studying how advice shortens proofs, we gain deep insights into the fundamental limits of verification and the structural hardness of individual problem instances.

The Core Mechanism: Proof Systems with Advice

A standard propositional proof system is a polynomial-time algorithm that verifies whether a given string is a valid proof for a tautology. If a proof system is polynomially bounded, it means every tautology has a proof whose size is at most a polynomial function of the formula's length. Whether such a system exists is one of the major open problems in theoretical computer science, as it is equivalent to asking whether $NP = coNP$.

To probe the boundaries of this problem, we can grant the proof verification system access to an external piece of information called advice. This advice string can depend on the length of the input or even the specific instance being verified.

The central question then becomes: Does advice actually help to shorten proofs?

In Does Advice Help to Prove Propositional Tautologies?, Sebastian Müller et al. explored this exact mechanism. The authors demonstrated that the power of advice is not necessarily tied to its arbitrary complexity. In fact, highly complex advice strings can often be simplified or entirely replaced by structured forms of non-uniform computation, such as sparse NP-oracles or logarithmic-length advice.

Crucially, the authors established a profound structural consequence: if adding advice does not significantly shorten the length of propositional proofs, then optimal proof systems (systems that can simulate any other proof system with at most a polynomial slowdown) must exist without any advice. Because the existence of such optimal systems is widely considered unlikely, this result strongly implies that advice does indeed provide a genuine, irreplaceable reduction in proof length.

Bridging Proof Length and Instance Complexity

Why does advice help shorten proofs? The intuition lies in the concept of instance complexity, which measures the environment needed to decide or verify a specific input instance, rather than the entire language.

In Nondeterministic Instance Complexity and Proof Systems with Advice, Johannes Köbler et al. established a tight mathematical equivalence between these two concepts. They showed that a language possesses a polynomially bounded proof system that utilizes logarithmic input advice if and only if the language belongs to the nondeterministic instance complexity class $NIC[\log, \text{poly}]$.

$$\text{Polynomially Bounded Proof System w/ } \log \text{-advice} \iff \text{Membership in } NIC[\log, \text{poly}]$$

This equivalence reveals why the mechanism works: the advice string acts as a targeted computational shortcut. If a specific instance is highly complex, a small amount of trusted advice can pinpoint the exact "hard core" of that instance, bypassing the need for an exponentially long uniform proof. The difficulty of efficiently proving a statement is thus fundamentally bounded by how hard it is for a small nondeterministic machine to verify that specific instance.

From Tautologies to Total Functions and Practical Solvers

This interplay between proof verification and computational complexity extends far beyond propositional logic. It provides a unifying lens for characterizing other complex problem domains, such as total search problems and automated reasoning.

Unifying Total Functions (TFNP)

In the realm of total NP search problems (TFNP)—where a solution is guaranteed to exist, but finding it can be computationally hard—proof verification serves as a foundational tool to map out complexity. In Towards a Unified Complexity Theory of Total Functions, Paul W. Goldberg et al. introduced a framework centered on a "Wrong Proof" problem. Instead of searching for a solution directly, the problem focuses on finding an error in a concisely represented formal proof. By leveraging these novel deductive systems, the authors demonstrated that all major subclasses of TFNP can be reduced to this single proof-verification defect, unifying a fragmented landscape through proof complexity.

Conditional Optimality in Practical Systems

The theoretical limits explored by advice-bounded systems also dictate the performance of practical modern solvers. For instance, in Answer Set Programming (ASP)—a declarative problem-solving paradigm—solvers must certify both consistent and inconsistent programs.

In ASP-QRAT: A Conditionally Optimal Dual Proof System for ASP, Alexis de Colnet et al. introduced a proof system that translates ASP problems into Quantified Boolean Formulas (QBFs). The authors proved that their system is conditionally optimal. This means that any attempt to prove a super-polynomial lower bound for this system would automatically resolve major, long-standing open problems in structural complexity theory.

Conclusion

By studying proof systems augmented with advice, complexity theorists have bridged the gap between uniform algorithmic hardness and the specific difficulty of individual instances. Whether by replacing complex advice with sparse oracles, equating proof lengths to nondeterministic instance complexity, or establishing conditional optimality for practical logic solvers, this research direction demonstrates that the act of proving a statement is inextricably linked to the non-uniform computational resources available to verify it.

Key Foundational Work

Does Advice Help to Prove Propositional Tautologies? (2009) — contributed 10 concept elements to this direction.
Nondeterministic Instance Complexity and Proof Systems with Advice (2009) — contributed 5 concept elements to this direction.
Towards a Unified Complexity Theory of Total Functions (2018) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_proof_systems_with_advice_273f01d9,
  title = {proof systems with advice},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proof-systems-with-advice/rdr_273f01d987084be995e41fee14fc9f8e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_proof_systems_with_advice_273f01d9_v1,
  title = {proof systems with advice},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proof-systems-with-advice/rdr_273f01d987084be995e41fee14fc9f8e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake