  Motivated by the application of Hall's Marriage Theorem in various
LP-rounding problems, we introduce a generalization of the classical marriage
problem (CMP) that we call the Fractional Marriage Problem. We show that the
Fractional Marriage Problem is NP-Complete by reduction from Boolean
Satisfiability (SAT). We show that when we view the classical marriage problem
(a.k.a. bipartite matching) as a sub-class of SAT we get a new class of
polynomial-time satisfiable SAT instances that we call CMP-SAT, different from
the classically known polynomial-time satisfiable SAT instances 2-SAT, Horn-SAT
and XOR-SAT.
  We next turn to the problem of recognizing CMP-SAT instances, first using SAT
embeddings, and then using their embeddings within the universe of Fractional
Marriage Problems (FMPs). In the process we are led to another generalization
of the CMP that we call the Symmetric Marriage Problem, which is polynomial
time decidable and leads to a slight enlargement of the CMP-SAT class. We
develop a framework for simplifying FMP problems to identify CMP instances that
we call Fragment Logic. Finally we give a result that sheds light on how
expressive the FMP need be to still be NP-Complete. The result gives a second
NP-Complete reduction of the FMP, this time to Tripartite Matching. We conclude
with a wide assortment of suggested additional problems.
