Succinct certification of monotone circuits

Abstract Monotone Boolean circuits are circuits where each gate is either an AND gate or an OR gate. In other words, negation gates are not allowed on monotone circuits. This class of circuits has sparked the attention of researchers working in several subfields of combinatorics and complexity theory. In this work, we consider the notion of certification-width of a monotone Boolean circuit, a complexity measure that intuitively quantifies the minimum number of edges that need to be traversed by a minimal set of positive weight inputs in order to certify that a given circuit is satisfied. We call the problem of computing this invariant as Succinct Monotone Circuit Certification (SMCC) . We prove that SMCC is NP-complete even when the input monotone circuit is planar. Subsequently, we show that k -SMCC , the problem parameterized by the size of the solution, is W[1]-hard, but still in W[P]. In contrast, we show that k -SMCC is fixed-parameter tractable when restricted to monotone circuits of bounded genus.