yesinstances

Yes-instances, sometimes written as yes-instances, yes instances, or simply yesinstances, is a term used in the theory of computation to describe inputs to a decision problem for which the correct answer is "yes." Formally, a decision problem is defined by a language L over some alphabet, and yes-instances are the strings x such that x belongs to L. The complementary set of inputs, where the correct answer is "no," are called no-instances.

In practice, yes-instances illustrate the objects a problem is designed to recognize. For example, in the graph connectivity problem, yes-instances are the graphs that are connected; in the satisfiability problem 3-SAT, yes-instances are the boolean formulas that are satisfiable. The distinction between yes-instances and no-instances provides a framework for analyzing algorithmic behavior, complexity, and reductions between problems.

Yes-instances are central to numerous concepts in computational complexity. Reductions between decision problems often concern preserving yes-instances: a problem A reduces to problem B if a yes-instance of A maps to a yes-instance of B in a way that allows solving A by solving B. In probabilistic and approximate models, properties such as completeness and soundness relate to correctly identifying yes-instances versus no-instances with high probability. In promise problems, the term yes-instances refers to inputs that lie within the promised subset of instances, while inputs outside the promise may not be subject to the same requirements.

Understanding yes-instances helps clarify what it means for an algorithm to decide a problem, how problems relate through reductions, and how different computational models treat inputs that should yield a positive answer.