Documentation

Provenance.HavingComplexity

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.

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 #

Step 1: the provenance of a HAVING SUM predicate #

noncomputable def Provenance.Complexity.havingSumProv {ι K : Type} [DecidableEq ι] [CommSemiringWithMonus K] (α : ι → K) (U : Finset ι) (t : ι → ℕ) (B : ℕ) :
K

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 #

    noncomputable def Provenance.Complexity.expo {ι X : Type} (x : ι → X) (W : Finset ι) :

    The exponent vector of a world: with pairwise distinct variables, the annotation A_W is the monomial with this exponent.

    Equations
    Instances For
      Dependency graph
      theorem Provenance.Complexity.havingSumProv_ne_zero_iff {ι X : Type} [DecidableEq ι] [DecidableEq X] (x : ι → X) (hx : Function.Injective x) (U : Finset ι) (t : ι → ℕ) (B : ℕ) :
      havingSumProv (fun (i : ι) => MvPolynomial.X (x i)) U t B ≠ 0 ↔ ∃ W ⊆ U, W.Nonempty ∧ ∑ i ∈ W, t i = B

      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 #

      theorem Provenance.Complexity.havingSumProvBool_ne_zero_iff {ι X : Type} [DecidableEq ι] [DecidableEq X] (x : ι → X) (hx : Function.Injective x) (U : Finset ι) (t : ι → ℕ) (B : ℕ) :
      havingSumProv (fun (i : ι) => BoolFunc.var (x i)) U t B ≠ 0 ↔ ∃ W ⊆ U, W.Nonempty ∧ ∑ i ∈ W, t i = B

      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
              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
                @[instance_reducible]
                Equations
                Dependency graph
                Dependency graph
                Dependency graph
                Dependency graph
                Dependency graph
                Dependency graph
                Equations
                Instances For
                  Dependency graph
                  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.

                    Equations
                    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.

                        @[reducible, inline]

                        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.

                        Equations
                        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.

                                Equations
                                Instances For
                                  Dependency graph