yesinstance

Yesinstance, also encountered as yes-instance or yes-instance input, refers to a specific kind of input to a decision problem. A decision problem asks a yes/no question about each input, and its set of inputs is partitioned into yes-instances, for which the answer is yes, and no-instances, for which the answer is no. The term yes-instance is used to describe precisely those inputs that satisfy the problem’s predicate.

In formal terms, a decision problem is a function that maps each input to either true (yes) or false (no). An input is a yes-instance when the function evaluates to true. The distinction between yes-instances and no-instances is central to complexity theory, reductions, and algorithm design, since many results describe performance or feasibility on inputs of each type. Some analyses and reductions preserve yes-instances, meaning that a yes-instance of one problem maps to a yes-instance of another.

Examples help illustrate the concept. In the satisfiability (SAT) problem, a formula is a yes-instance if it is satisfiable by some assignment. In graph coloring with k colors, a graph is a yes-instance if it can be colored with at most k colors. In the Hamiltonian cycle problem, a graph is a yes-instance if it contains a Hamiltonian cycle.

Notes on terminology: while yes-instance is standard, some texts and authors hyphenate or reverse the order (yes-instances, yes instance). The concept is fundamental to understanding how decision problems are framed and analyzed in theory and practice.