[Model] CosineProductIntegration

[isPANN]

Motivation

COSINE PRODUCT INTEGRATION (P233) from Garey & Johnson, A7 AN14. Given a sequence of integers, the problem asks whether the integral of the product of cosines (with those integers as frequency coefficients) over [0, 2pi] equals zero. This is equivalent via Fourier analysis to asking whether there is NO partition of the integers into two equal-sum subsets, making it the complement of the PARTITION problem. NP-complete by reduction from PARTITION (Plaisted, 1976). Despite being phrased as a continuous integral, the problem encodes purely discrete combinatorial structure. Solvable in pseudo-polynomial time via dynamic programming on achievable partial sums.

Associated reduction rules:

• As target: R177 (PARTITION to COSINE PRODUCT INTEGRATION)
• As source: (none known)

Definition

Name: CosineProductIntegration

Canonical name: Cosine Product Integration
Reference: Garey & Johnson, Computers and Intractability, A7 AN14

Mathematical definition:

INSTANCE: Sequence (a_1, a_2, . . . , a_n) of integers.
QUESTION: Does ∫_0^{2π} (∏_{i=1}^{n} cos(a_i·θ)) dθ = 0?

Variables

• Count: n (one binary variable per element, representing the sign assignment in the product-to-sum expansion)
• Per-variable domain: {0, 1} -- conceptually, 0 maps to sign +1, and 1 maps to sign -1 in the expansion cos(a_i θ) = (e^{i a_i θ} + e^{-i a_i θ})/2
• Meaning: The integral equals (2π / 2^n) times the number of sign assignments ε ∈ {-1,+1}^n such that Σ ε_i a_i = 0. The integral is zero iff no such sign assignment exists, i.e., iff PARTITION has no solution. Thus the "variables" correspond to the partition choices, and the problem is a decision problem with no explicit configuration space.

Schema (data type)

Type name: CosineProductIntegration
Variants: none (no type parameters; coefficients are plain integers)

Field	Type	Description
coefficients	Vec<i64>	Integer sequence (a_1, a_2, ..., a_n) of cosine frequencies

Complexity

• Best known exact algorithm: The problem reduces to PARTITION (complement): the integral is nonzero iff a balanced sign assignment exists. The Schroeppel-Shamir meet-in-the-middle algorithm (1981) solves the underlying PARTITION/SUBSET SUM problem in O*(2^(n/2)) time and O*(2^(n/4)) space. Additionally, the problem is solvable in pseudo-polynomial time O(n · S) where S = Σ|a_i|, since one can track achievable partial sums via dynamic programming. [Plaisted, 1976; Schroeppel & Shamir, SIAM J. Comput. 10(4):456-464, 1981.]

Extra Remark

Full book text:

INSTANCE: Sequence (a_1, a_2, . . . , a_n) of integers.
QUESTION: Does ∫_0^{2π} (∏_{i=1}^{n} cos(a_i·θ)) dθ = 0?

Reference: [Plaisted, 1976]. Transformation from PARTITION.
Comment: Solvable in pseudo-polynomial time. See reference for related complexity results concerning integration.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^n sign assignments ε ∈ {-1,+1}^n; check if any yields Σ ε_i a_i = 0. The integral is zero iff no such assignment exists.)
• It can be solved by reducing to integer programming. (Binary ILP: variables x_i ∈ {0,1}, constraint Σ (2x_i - 1) · a_i = 0. Feasible iff integral ≠ 0.)
• Other: Pseudo-polynomial DP in O(n · S) time tracking achievable signed sums, where S = Σ|a_i|.

Example Instance

Input:
Sequence: (2, 3, 5) (n = 3)

Analysis:
Enumerate all 2^3 = 8 sign assignments:

• (+2, +3, +5) = 10
• (+2, +3, -5) = 0 ✓
• (+2, -3, +5) = 4
• (+2, -3, -5) = -6
• (-2, +3, +5) = 6
• (-2, +3, -5) = -4
• (-2, -3, +5) = 0 ✓
• (-2, -3, -5) = -10

Two sign assignments yield zero, so the integral = (2π/8) · 2 = π/2 ≠ 0.

Answer: NO -- the integral does NOT equal zero (because a partition 2+3 = 5 exists).

Another example (integral = 0):
Sequence: (1, 2, 6) (n = 3)
Sign assignments: sums are 9, -3, 5, -7, 7, -5, 3, -9. None equal zero.
Answer: YES -- the integral equals zero (no balanced partition exists since 1+2+6 = 9 is odd... wait, with signs: we need Σ ε_i a_i = 0, i.e., the positive and negative groups have equal sum. Total = 9, so each group would need sum 4.5, impossible with integers.)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but essentially equivalent to PARTITION (complement); may be better as a reduction rule
Non-trivial	⚠️ Warn	Very close to PARTITION complement; the cosine integral is a thin encoding of the same combinatorial structure
Correctness	✅ Pass	Mathematical claims verified; Schroeppel-Shamir reference has minor volume number error (10(3) not 10(4))
Well-written	✅ Pass	Well-structured with clear variable mapping, schema, and worked examples

Overall: 2 passed, 2 warnings, 0 failed

---

Usefulness

The problem does not exist in the codebase and is from Garey & Johnson (A7 AN14). However, the issue itself states: "the integral is zero iff no such sign assignment exists, i.e., iff PARTITION has no solution." This means the problem is the complement of PARTITION. Adding it as a separate model would primarily be valuable if:

1. There are non-trivial reductions from/to CosineProductIntegration that are distinct from PARTITION reductions.
2. The continuous integral formulation enables different algorithmic approaches.

The issue proposes only one associated rule (PARTITION to CosineProductIntegration), which is essentially the equivalence itself. No outgoing reductions are proposed. The problem risks being an orphan that merely duplicates PARTITION's computational content under a different name.

That said, the problem is legitimately distinct in its formulation (continuous integral vs discrete partition), and the codebase does not yet have a Partition problem either, so this could fill a gap in the algebra/number theory category.

Non-trivial

The issue honestly acknowledges the equivalence to PARTITION complement. The transformation between the two is essentially a one-liner: expand the product of cosines using the product-to-sum identity, then the integral picks out the DC component, which counts balanced sign assignments.

However, the problem does have a genuinely different input format (a sequence of integers defining cosine frequencies, rather than a multiset to partition). The feasibility constraint is also stated differently (integral equals zero vs existence of an equal-sum partition). By the project's criteria -- "genuinely different feasibility constraint or objective function" -- this is borderline. The feasibility constraint is mathematically equivalent but syntactically different.

Since the issue clearly documents the equivalence and the transformation is not completely trivial (it requires Fourier analysis to see the connection), this is a Warn rather than a Fail.

Correctness

• Plaisted (1976): Referenced in Garey & Johnson as the source of the NP-completeness transformation from PARTITION. The specific paper could not be independently located via web search (it may be a technical report or conference paper from 1976, predating JCSS publication). However, the mathematical claim is verifiable: the integral of a product of cosines equals (2pi/2^n) times the count of balanced sign assignments, which is a standard result from Fourier analysis. The NP-completeness follows immediately from PARTITION's NP-completeness.
• Schroeppel & Shamir (1981): Confirmed. "A T=O(2^(n/2)), S=O(2^(n/4)) Algorithm for Certain NP-Complete Problems," SIAM J. Comput. 10(3):456-464, 1981. Note: the issue cites volume 10(4); the correct volume/issue is 10(3). This is a minor bibliographic error.
• Mathematical verification of the example:
  • Sequence (2, 3, 5): The 8 sign assignments and their sums are correctly computed. Two assignments yield sum 0: (+2,+3,-5) and (-2,-3,+5). The integral = (2pi/8)*2 = pi/2 is correct. Answer NO (integral is nonzero) is correct.
  • Sequence (1, 2, 6): Total sum = 9 (odd), so no balanced partition exists. The sign sums 9,-3,5,-7,7,-5,3,-9 are correct. None equal zero. Answer YES (integral is zero) is correct.
• Formula for the integral: The claim that the integral equals (2pi/2^n) times the number of sign assignments with sum zero is correct, following from the product-to-sum expansion of cosines.

Well-written

Strengths:

• Clear, precise mathematical definition matching Garey & Johnson.
• Well-defined variable mapping: n binary variables with domain {0,1}, representing sign assignments. This is directly implementable with dims() = vec![2; n].
• Clean schema with a single coefficients field.
• Two worked examples (one YES, one NO) with full sign-assignment enumeration.
• Multiple solver approaches identified: brute-force (checked), ILP formulation (described but not checked), and pseudo-polynomial DP.
• The connection to PARTITION is thoroughly explained.

Minor issues (not failures):

• The ILP solver checkbox is unchecked despite a valid ILP formulation being described. Consider checking it.
• No concrete complexity string for declare_variants! is given. A natural choice would be "2^num_coefficients" (brute force) or reference the Schroeppel-Shamir bound.
• The Schroeppel-Shamir citation has volume 10(4) instead of 10(3).

Recommendations

• Provide a concrete complexity string, e.g., "2^(num_coefficients / 2)" for the Schroeppel-Shamir bound.
• Fix the Schroeppel-Shamir citation: SIAM J. Comput. 10(3):456-464, not 10(4).
• Consider implementing PARTITION first (as a prerequisite model), then adding CosineProductIntegration as a complementary formulation with a bidirectional reduction rule.
• Check the ILP solver checkbox since a valid formulation is described.