NP-completeness of deciding non-zero HAVING provenance #
Deciding whether the provenance of a HAVING SUM query over an ℕ[X]- or
𝔹[X]-instance is non-𝟘 is NP-complete, already in data complexity: the
query SELECT DISTINCT 1 FROM R GROUP BY b HAVING SUM(v) = b is fixed and
only the instance varies.
The development is in three parts.
- The bridges (
havingSumProv_ne_zero_iff,havingSumProvBool_ne_zero_iff): overℕ[X] = MvPolynomial X ℕand over𝔹[X] = BoolFunc X, with pairwise distinct variables as annotations, the possible-world provenance ofSUM(t) = Bon a groupUis non-𝟘exactly when some non-emptyW ⊆ Usatisfies∑ i ∈ W, t i = B. Overℕ[X]the monus factor of a world annotation collapses to𝟙and the surviving monomials are pairwise distinct, so no cancellation occurs; over𝔹[X]the valuation realizing exactly the occurrences of a witnessing world satisfies the provenance, whose satisfiability is non-𝟘-ness. - The complexity half: that combinatorial condition, read off a
Language.binWeightsstructure, is a decision problemHavingSumNonzero, and it is NP-complete. Hardness is an FO reduction fromKnapsack(subset-sum with binary weights), so it is stronger than a Karp reduction. - The encoding half, which joins the two: a concrete group is a list of
aggregate values and a constant, encoded by
DescriptiveComplexity.binarySubsetSumEncoding, whose declared size is the total bit length and whose no-padding/no-compression bounds are discharged at construction.havingSumNonzeroHow_faithfulandhavingSumNonzeroBool_faithfulprove thatHavingSumNonzerocomputes exactly non-zero provenance on every encoded group, andexists_concreteNonemptySubsetSum_iff– through the computable decoder ofDescriptiveComplexity.bwDecode– that every structure is such a group, so both halves of the NP-completeness below are statements about concrete groups.
That last half is not bookkeeping. Values written in unary would make the
problem tractable – Provenance.Algorithms.SumDP is the very dynamic program
that solves it, and DescriptiveComplexity.no_unary_encoding shows the size
bounds reject that reading – so the representation is part of the statement,
and the encoding is where it is pinned down.
Hardness is a padding interpretation: keep the instance and add one
weight-zero item per element of the universe. Those items change no reachable
total, but they make a solution non-empty, which is what the possible-world
semantics requires: Having.havingProv sums over the non-empty sub-worlds
of a group only.
Main results #
havingSumProv_ne_zero_iff,havingSumProvBool_ne_zero_iff– the two bridges;HavingSumNonzero– the bundled decision problem;hasNonemptySubsetSum_iff– it isKnapsackcut down by one FO sentence;knapsack_fo_reduction_havingSumNonzero– the padding FO reduction;havingSumNonzero_NP_complete– NP-completeness, in data complexity;havingSumNonzeroHow_faithful,havingSumNonzeroBool_faithful– the encoding of concrete groups is faithful, which carries membership to concrete groups;havingSumNonzeroDecodingandexists_concreteNonemptySubsetSum_iff– the computable decoding back, which carries hardness: the problem is nowhere hard on structures that are not groups.
Step 1: the provenance of a HAVING SUM predicate #
Provenance of HAVING SUM(t) = B on the group of occurrences U, in the
possible-world semantics: the ⊕-sum, over the non-empty worlds whose
aggregate equals B, of the world annotations Having.T.
Equations
Instances For
Dependency graph
Step 2: ℕ[X] with distinct variables – no cancellation #
The exponent vector of a world: with pairwise distinct variables, the
annotation A_W is the monomial with this exponent.
Equations
- Provenance.Complexity.expo x W = ∑ i ∈ W, Finsupp.single (x i) 1
Instances For
Dependency graph
The bridge. Over ℕ[X] with pairwise distinct variables as
annotations, the possible-world provenance of SUM(t) = B on a group U is
non-𝟘 exactly when some non-empty sub-world of U has aggregate B.
Dependency graph
Step 2': 𝔹[X] with distinct variables – the same characterization #
The bridge, over 𝔹[X]. With pairwise distinct variables as
annotations, the possible-world provenance of SUM(t) = B on a group U
is non-𝟘 in 𝔹[X] exactly when some non-empty sub-world of U has
aggregate B: the valuation making true exactly the variables of a
witnessing world satisfies precisely that world's annotation. The
combinatorial characterization is the same as over ℕ[X]
(havingSumProv_ne_zero_iff), so the NP-completeness of the underlying
decision problem covers both semirings.
Dependency graph
Step 3: the decision problem and its membership in NP #
Some non-empty set of items has weights summing to the target.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Dependency graph
The decision problem behind the NP-completeness of non-zero HAVING SUM
provenance: the isomorphism-invariant bundling of HasNonemptySubsetSum.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The target is non-zero.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Some item has weight zero.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Equations
Instances For
Dependency graph
HavingSumNonzero is in NP: it is Knapsack, whose Σ₁ definition is
the binary adder of knapsackKernel, conjoined with a first-order sentence.
Dependency graph
Step 4: NP-hardness, by FO reduction from Knapsack #
Tags of the padding interpretation: the original instance, plus a copy of the universe turned into items of weight zero.
Instances For
Dependency graph
Dependency graph
Equations
- Provenance.Complexity.instFintypeHTag = { elems := {Provenance.Complexity.HTag.orig, Provenance.Complexity.HTag.pad}, complete := ⋯ }
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Equations
Instances For
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
- Provenance.Complexity.HRed.hBitF x✝¹ x✝ = ⊥
Instances For
Dependency graph
Equations
- Provenance.Complexity.HRed.hLeF Provenance.Complexity.HTag.orig Provenance.Complexity.HTag.pad = ⊤
- Provenance.Complexity.HRed.hLeF Provenance.Complexity.HTag.pad Provenance.Complexity.HTag.orig = ⊥
- Provenance.Complexity.HRed.hLeF x✝¹ x✝ = FirstOrder.Language.bwLe.formula₂ (FirstOrder.Language.var (0, 0)) (FirstOrder.Language.var (1, 0))
Instances For
Dependency graph
The padding interpretation: keep the instance, and add one weight-zero item per element of the universe.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
A point of the interpreted universe.
Instances For
Dependency graph
Correctness of the reduction. Padding with weight-zero items makes a solution non-empty without changing which totals are reachable.
Dependency graph
Knapsack FO-reduces to HavingSumNonzero, so the latter is NP-hard
in data complexity: the reduction outputs an instance, the query being
fixed.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
NP-completeness of non-zero HAVING SUM provenance, in data
complexity: membership and FO-hardness from Knapsack. Read through the
bridges havingSumProv_ne_zero_iff and havingSumProvBool_ne_zero_iff, and
through the faithful encoding of Step 5 below, this is the NP-completeness of
deciding non-𝟘 provenance of a concrete group over ℕ[X]- and
𝔹[X]-instances, the values written in binary.
Dependency graph
Step 5: the concrete groups the theorem is about #
A Language.binWeights structure is not what a user has in hand: a HAVING SUM group is a list of aggregate values and the constant the predicate
compares against. That is exactly
DescriptiveComplexity.SubsetSumInstance, and
DescriptiveComplexity.binarySubsetSumEncoding encodes it – with the two size
obligations, no padding and no compression, discharged at construction against
a declared size that counts bit length. What remains is the semantic
obligation, DescriptiveComplexity.Encoding.Faithful: that the decision
problem above computes non-zero provenance on every encoded group. Both
semirings get it from the same encoding, the bridges having shown they have
the same combinatorial content.
A concrete HAVING SUM group: the aggregate values of its occurrences,
and the constant the predicate compares against. This is literally
DescriptiveComplexity.SubsetSumInstance; naming it here records what the
components mean on this side of the bridge.
Instances For
Dependency graph
Some non-empty sub-world of the group aggregates to the constant: the combinatorial content the two bridges give the provenance, on concrete data. Non-emptiness is the possible-world semantics' exclusion of the empty world, not a technicality.
Equations
Instances For
Dependency graph
Non-zero HAVING SUM provenance of a concrete group over ℕ[X], its
occurrences annotated by pairwise distinct variables.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Non-zero HAVING SUM provenance of a concrete group over 𝔹[X], its
occurrences annotated by pairwise distinct variables.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The encoding side is the concrete-instance bridge
BinarySubsetSum.exists_selection_iff, for the condition “non-empty, and
summing to the target”.
Dependency graph
The encoding is faithful, over ℕ[X]: on every encoded group,
HavingSumNonzero computes exactly non-zero provenance of the concrete
group. With the size bounds discharged at construction, this is what makes
havingSumNonzero_NP_complete a statement about lists of binary-written
aggregate values – and not about the unary reading, which
Provenance.Algorithms.SumDP solves.
Dependency graph
The encoding is faithful, over 𝔹[X]: the same encoding serves the
Boolean-function semiring, the two bridges having given the same
combinatorial characterization.
Dependency graph
Step 6: reading the hardness back on concrete groups #
Faithfulness carries membership to concrete groups; hardness needs the
converse – that the problem is not hard only on structures no group encodes.
The decoder of DescriptiveComplexity.bwDecode is problem-independent, so it
serves here unchanged: only its soundness has to be restated against
HavingSumNonzero. There is again no junk to exclude, whence
exists_concreteNonemptySubsetSum_iff for every nonempty finite structure.
Dependency graph
The computable decoding of binary-weighted structures, for non-zero
HAVING SUM provenance. Every nonempty finite structure decodes, so the
NP-hardness above is nowhere hardness on junk alone.