[Rule] Partition to RSDF

[QingyunQian]

Source: Partition
Target: RobustSemidefiniteFeasibility (RSDF)
Motivation: Gives a direct NP-hardness reduction from Partition to RSDF
Reference:

• Ben-Tal, A. & Nemirovski, A. (1998). Robust Convex Optimization. (Section 3.4.1: direct Partition-to-RSDF style hardness construction)
• Gurvits, L. (2003). Classical deterministic complexity of Edmonds' problem and Quantum Entanglement.
• Gharibian, S. (2009/2018). Strong NP-Hardness of the Quantum Separability Problem. (formal promise definition of RSDF)

Reduction Algorithm

Notation:

• Source (Partition): integer vector a = (a_1, ..., a_l) in Z^l; question: does there exist z in {-1, 1}^l such that a^T z = 0?
• Target (RSDF): symmetric rational matrices B_1, ..., B_k in Q^(l x l), and rationals zeta, eta >= 0, with

g(B_1,...,B_k) = max_{||x||_2=1} sum_{i=1}^k (x^T B_i x)^2.

Promise decision:

• YES if g >= zeta + eta
• NO if g <= zeta - eta

Direct Mapping (Partition -> RSDF):

Set k = l(l-1)/2 + 1.

1. Hypercube coupling matrices (k-1 matrices):
   For each pair 1 <= p < q <= l, define a symmetric matrix B^{pq} whose quadratic form is

   x^T B^{pq} x = sqrt(2) * x_p * x_q.
   

   (Equivalent rationally-scaled variants are acceptable in implementation; only polynomial-time computability and threshold scaling matter.)

2. Partition constraint matrix (last matrix):
   Define

   B^k = I - (a a^T)/(1 + a^T a).
   

3. Thresholds:
   Let the absolute YES optimum be

   r* = 2 - 1/l.
   

   (Scaling note: the original Ben-Tal/Nemirovski derivation writes the maximization on ||xi||_2^2 = l,
   where the optimum is 2l^2 - l. RSDF here uses the unit sphere ||x||_2 = 1, and since the objective
   is quartic, values scale by 1/l^2, yielding r* = (2l^2 - l)/l^2 = 2 - 1/l.)

   Set zeta, eta so that:

   • zeta + eta = r*
   • zeta - eta is below r* by at least the polynomially bounded separation margin from the construction.

Correctness sketch:

• The first k-1 matrices force the maximizer geometry to align with sign-vector structure.
• The last matrix enforces the partition balance condition via the projector-like term using a.
• Therefore:
  • Partition YES => g >= zeta + eta (YES side),
  • Partition NO => g <= zeta - eta (NO side),
    with a polynomially separated promise gap.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_matrices (k)	l(l-1)/2 + 1
matrix_dim (l)	l
bit_size of entries and thresholds	polynomial in input bit-size of a

Validation Method

• On small instances, brute-force Partition (z in {-1,1}^l) and compare with RSDF decision from the constructed matrices
• Numerically evaluate g(B_1,...,B_k) by dense sphere sampling / local optimization as a sanity check
• Check both YES and NO instances satisfy the promised inequalities at zeta +/- eta

Example

Source Partition instance:

a = [1, -1], l = 2
Question: exists z in {-1,1}^2 with a^T z = 0?
YES: z = [1, 1]

Target RSDF image (direct):

l = 2 => k = 2

B_1 from pair (1,2):
B_1 = [[0, sqrt(1/2)],
       [sqrt(1/2), 0]]
so x^T B_1 x = sqrt(2) x_1 x_2.

a^T a = 2, aa^T = [[1, -1],[-1, 1]]
B_2 = I - aa^T/(1 + a^T a)
    = I - (1/3)[[1, -1],[-1, 1]]
    = [[2/3, 1/3],[1/3, 2/3]]

Unit vector x = [1/sqrt(2), 1/sqrt(2)] gives:
(x^T B_1 x)^2 = 0.5
(x^T B_2 x)^2 = 1.0
Max g = 1.5

r* = 2 - 1/l = 1.5
set zeta + eta = 1.5 (and zeta - eta by the construction margin)

This is the direct matrix construction route Partition -> RSDF.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Neither Partition nor RSDF exist in the codebase; both models must be added first
Non-trivial	✅ Pass	Matrix gadget construction with coupling matrices and projection terms
Correctness	❌ Fail	Misattributed references; construction not verifiable from cited sources
Well-written	❌ Fail	Incomplete threshold definition; vague overhead; minimal example

Overall: 1 passed, 2 failed, 1 warning

---

Usefulness

Neither Partition nor RobustSemidefiniteFeasibility (RSDF) currently exist in the reduction graph. Running pred list confirms 24 problem types, none of which include Partition or RSDF. This means implementing this rule would first require adding two new model issues.

The reduction itself would be novel (no existing path), but the practical value is limited without the prerequisite models. Additionally, RSDF is a promise problem (with a gap region where any answer is valid), which is a fundamentally different structure from the satisfaction/optimization problems currently in the codebase. Implementing RSDF would require careful design decisions about how promise problems fit the Problem trait hierarchy.

Result: Warn — novel reduction but depends on two non-existent models, one of which (RSDF as a promise problem) may not fit the current framework.

---

Non-trivial

The reduction constructs l(l-1)/2 + 1 symmetric matrices from the Partition input vector: coupling matrices B^{pq} that enforce hypercube-like geometry, and a projection-based constraint matrix B^k = I - aa^T/(1 + a^T a). This is a genuine structural transformation involving auxiliary matrix construction and not a simple variable substitution or type coercion.

Result: Pass.

---

Correctness

Several serious issues with the cited references:

Reference 1: Ben-Tal & Nemirovski (1998), "Robust Convex Optimization"

• The paper exists and is correctly cited (MOR, Vol. 23, pp. 769-805).
• However, the issue claims "Section 3.4.1: direct Partition-to-RSDF style hardness construction." The Ben-Tal & Nemirovski paper is about robust convex optimization methodology — it establishes that robust counterparts of uncertain SDPs are NP-hard in general, but it does not contain a direct, explicit Partition-to-RSDF reduction. The section numbering and claim are misleading.

Reference 2: Gurvits (2003), "Classical deterministic complexity of Edmonds' problem and Quantum Entanglement"

• The paper exists (arxiv: quant-ph/0303055, STOC 2003).
• Gurvits did reduce PARTITION to a quantum separability problem. However, as Gharibian (2009) explicitly notes, "PARTITION is known to be NP-hard only if the magnitudes of the input integers are exponentially large with respect to input length." This means Gurvits' Partition-based reduction only yields weak NP-hardness (inverse exponential precision). Gharibian replaced it with a CLIQUE-based reduction for strong NP-hardness.
• The issue does not acknowledge this fundamental limitation of the Partition-to-RSDF route.

Reference 3: Gharibian (2009/2018), "Strong NP-Hardness of the Quantum Separability Problem"

• The paper exists (arxiv: 0810.4507).
• The issue claims this paper provides the "formal promise definition of RSDF" — this is correct; Definition 2 in Gharibian's paper defines RSDF.
• However, Gharibian's paper explicitly replaces Partition with CLIQUE in the reduction chain (CLIQUE → RSDF → WOPT → WMEM), specifically because the Partition route is too weak.

The specific matrix construction in the issue (coupling matrices B^{pq} with sqrt(2) x_p x_q and projection B^k = I - aa^T/(1 + a^T a)) does not appear in any of the three cited references in the form presented. The scaling argument ("original Ben-Tal/Nemirovski derivation writes the maximization on ||xi||_2^2 = l") cannot be verified against the actual paper content.

Result: Fail — the references are real papers but the claims about what they contain are inaccurate, and the specific construction cannot be verified from the cited sources.

---

Well-written

4a: Information Completeness

Section	Status
Source	Present: "Partition"
Target	Present: "RobustSemidefiniteFeasibility (RSDF)"
Motivation	Minimal — says only "Gives a direct NP-hardness reduction from Partition to RSDF" without explaining why this matters for the project
Reference	Present but misattributed (see Correctness)
Reduction Algorithm	Present with notation and steps
Size Overhead	Present but incomplete
Validation Method	Present
Example	Present but minimal

4b: Algorithm Completeness

The algorithm section provides reasonable step-by-step construction for the matrices. However, the threshold definition is critically incomplete:

• zeta + eta = r* is defined, but zeta - eta is left as "below r* by at least the polynomially bounded separation margin from the construction" — this is not a concrete formula. A programmer cannot implement this without knowing the exact value.
• The "correctness sketch" is a hand-wave: "The first k-1 matrices force the maximizer geometry to align with sign-vector structure" is not a verifiable claim.

4c: Symbol and Notation Consistency

• The overhead table uses bit_size described as "polynomial in input bit-size of a" — this is not a concrete formula and cannot be expressed as an overhead expression in the #[reduction(overhead = {...})] macro. The macro requires expressions using getter methods, not vague asymptotic descriptions.
• The code metric names num_matrices, matrix_dim, bit_size would need to be getter methods on the RSDF type, but since RSDF does not exist yet, these cannot be verified.

4d: Example Quality

The example uses a = [1, -1], l = 2, which is the absolute smallest non-trivial case. While it is fully worked through, a single 2-element example is too small to exercise the reduction meaningfully — with l=2 there is only k=2 matrices and 4 possible sign vectors. A l=3 or l=4 example would be more illustrative.

The example also uses sqrt(1/2) in matrix entries, which raises questions about rational representation (the overhead table claims rational matrices, but sqrt(1/2) is irrational). The issue notes "Equivalent rationally-scaled variants are acceptable" but does not specify what those are.

Result: Fail — incomplete threshold definition (not implementable), vague bit_size overhead, and irrational entries in a supposedly rational construction.

---

Recommendations

1. The Partition-to-RSDF reduction via Gurvits (2003) only gives weak NP-hardness. Consider instead proposing the CLIQUE-to-RSDF reduction from Gharibian (2009), which gives strong NP-hardness and is better documented.
2. Both Partition and RSDF models would need to be added first. Consider filing model issues for both before this rule issue.
3. RSDF is a promise problem — the codebase currently supports SatisfactionProblem (bool metric) and OptimizationProblem (SolutionSize metric). A promise problem with a gap region would need framework-level design discussion.
4. The threshold zeta - eta must be given as a concrete formula for implementability.
5. Resolve the irrational entry issue: either provide the exact rational-scaled variant or explain how sqrt(2) is handled in a rational matrix representation.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Both Source (Partition) and Target (RSDF) are not yet in the codebase; novelty cannot be assessed against existing graph
Non-trivial	✅ Pass	Construction involves coupling matrices, projector gadgets, and threshold separation — structurally non-trivial
Correctness	❌ Fail	Cited references do not support a Partition-to-RSDF reduction; the established reduction is CLIQUE-to-RSDF
Well-written	❌ Fail	Thresholds incompletely specified; algorithm has gaps; overhead uses vague "polynomial in input bit-size"

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

Neither Partition nor RobustSemidefiniteFeasibility (RSDF) exist in the codebase. Both would need to be added as new models before this rule could be implemented. Since neither problem exists, there is no existing path to compare against. However, usefulness is contingent on the correctness of the proposed reduction (see below). The motivation ("Gives a direct NP-hardness reduction from Partition to RSDF") is thin — it does not explain why this specific reduction path matters or what it enables beyond what the known CLIQUE-to-RSDF reduction already provides.

Non-trivial

The proposed construction involves hypercube coupling matrices for each pair of indices, a projector-like partition constraint matrix using the input vector, and explicit threshold calculations. This is structurally non-trivial.

Correctness

This check fails on multiple grounds:

Reference 1: Ben-Tal & Nemirovski (1998), "Robust Convex Optimization"

• The paper exists (Mathematics of Operations Research, Vol. 23, pp. 769-805) and is a seminal work on robust optimization.
• However, the claim that it contains "Section 3.4.1: direct Partition-to-RSDF style hardness construction" could not be verified. The paper's Section 3.4 discusses approximate robust counterparts of uncertain SDP problems and NP-hardness of robust SDP in general, but does not present a direct Partition-to-RSDF reduction. The paper focuses on tractability conditions for robust convex programs, not on NP-hardness reductions from specific combinatorial problems.

Reference 2: Gurvits (2003), "Classical deterministic complexity of Edmonds' problem and Quantum Entanglement"

• The paper exists (arxiv: quant-ph/0303055) and is a legitimate reference.
• However, this paper is about the complexity of Edmonds' problem (deciding if a linear subspace of matrices contains a nonsingular matrix) and its connection to quantum entanglement/separability. It does not contain a Partition-to-RSDF reduction.

Reference 3: Gharibian (2009/2018), "Strong NP-Hardness of the Quantum Separability Problem"

• The paper exists (arxiv: 0810.4507) and does formally define RSDF (Definition 2).
• However, the paper uses a reduction from CLIQUE to RSDF (Theorem 2, attributed to Gurvits and Ioannou), NOT from Partition to RSDF. The reduction leverages the Motzkin-Straus theorem connecting maximum clique to quadratic form optimization.
• The reduction chain in that paper is: CLIQUE →_m RSDF →_m WOPT →_t WMEM.

The fundamental problem: The established literature shows the NP-hardness of RSDF via a CLIQUE-to-RSDF reduction (Gurvits/Ioannou, via Motzkin-Straus). No cited reference contains or supports a direct Partition-to-RSDF reduction. The construction in this issue does not appear in any of the three cited papers, and the specific claim about "Section 3.4.1" in Ben-Tal & Nemirovski (1998) appears to be fabricated.

Additionally, there is a conceptual concern: the Partition problem is NP-hard only in the weak sense (it has a pseudo-polynomial dynamic programming solution). Any valid reduction from Partition would need to carefully handle the distinction between strong and weak NP-hardness, which the issue does not address.

Well-written

Several issues:

1. Incomplete threshold specification (Fail): The algorithm says "Set zeta, eta so that zeta + eta = r* and zeta - eta is below r* by at least the polynomially bounded separation margin from the construction" — but never gives explicit formulas for zeta and eta. The "polynomially bounded separation margin" is undefined and hand-waved.

2. Vague overhead (Fail): The bit_size overhead entry says "polynomial in input bit-size of a" — this is not a concrete formula usable for the #[reduction(overhead = {...})] macro. All overhead entries must be explicit expressions in terms of source problem getters.

3. Irrational entries in "rational" matrices (Fail): The issue states target matrices are in Q^(l x l) (rational), but the coupling matrices use sqrt(2), which is irrational. The issue hand-waves this with "Equivalent rationally-scaled variants are acceptable" without specifying what those variants are.

4. Missing symbol definition: The scaling note references "xi" without prior definition.

5. Example is minimal but adequate: The l=2 example is worked through, though the threshold zeta-eta is left unspecified even in the example.

6. Code metric names: The overhead table uses num_matrices, matrix_dim, bit_size — but since RSDF does not exist in the codebase, these cannot be verified against actual getter methods.

Recommendations

• The established reduction to prove RSDF NP-hardness is CLIQUE → RSDF (Gurvits/Ioannou). If the goal is to add an RSDF reduction, consider implementing that instead.
• If a Partition-to-RSDF reduction is genuinely novel, it requires an independent proof — not citations to papers that do not contain it.
• Provide explicit, concrete formulas for zeta and eta (not just constraints they must satisfy).
• Resolve the rational vs. irrational matrix entry issue with an explicit rational construction.

[GiggleLiu]

Closing as part of batch cleanup.