Repository navigation
[Rule] Partition to RSDF #175
Description
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 existz in {-1, 1}^lsuch thata^T z = 0? - Target (RSDF): symmetric rational matrices
B_1, ..., B_k in Q^(l x l), and rationalszeta, 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.
-
Hypercube coupling matrices (
k-1matrices):
For each pair1 <= p < q <= l, define a symmetric matrixB^{pq}whose quadratic form isx^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.)
-
Partition constraint matrix (last matrix):
DefineB^k = I - (a a^T)/(1 + a^T a). -
Thresholds:
Let the absolute YES optimum ber* = 2 - 1/l.(Scaling note: the original Ben-Tal/Nemirovski derivation writes the maximization on
||xi||_2^2 = l,
where the optimum is2l^2 - l. RSDF here uses the unit sphere||x||_2 = 1, and since the objective
is quartic, values scale by1/l^2, yieldingr* = (2l^2 - l)/l^2 = 2 - 1/l.)Set
zeta, etaso that:zeta + eta = r*zeta - etais belowr*by at least the polynomially bounded separation margin from the construction.
Correctness sketch:
- The first
k-1matrices 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.
- Partition YES =>
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.
Activity
zazabap commentedon Mar 10, 2026
Issue Quality Check — Rule
Overall: 1 passed, 2 failed, 1 warning
Usefulness
Neither
PartitionnorRobustSemidefiniteFeasibility(RSDF) currently exist in the reduction graph. Runningpred listconfirms 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
Problemtrait 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 + 1symmetric matrices from the Partition input vector: coupling matricesB^{pq}that enforce hypercube-like geometry, and a projection-based constraint matrixB^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"
Reference 2: Gurvits (2003), "Classical deterministic complexity of Edmonds' problem and Quantum Entanglement"
Reference 3: Gharibian (2009/2018), "Strong NP-Hardness of the Quantum Separability Problem"
The specific matrix construction in the issue (coupling matrices
B^{pq}withsqrt(2) x_p x_qand projectionB^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
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, butzeta - etais left as "belowr*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.k-1matrices force the maximizer geometry to align with sign-vector structure" is not a verifiable claim.4c: Symbol and Notation Consistency
bit_sizedescribed as "polynomial in input bit-size ofa" — 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.num_matrices,matrix_dim,bit_sizewould 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 — withl=2there is onlyk=2matrices and 4 possible sign vectors. Al=3orl=4example 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, butsqrt(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_sizeoverhead, and irrational entries in a supposedly rational construction.Recommendations
SatisfactionProblem(bool metric) andOptimizationProblem(SolutionSize metric). A promise problem with a gap region would need framework-level design discussion.zeta - etamust be given as a concrete formula for implementability.sqrt(2)is handled in a rational matrix representation.zazabap commentedon Mar 11, 2026
Issue Quality Check — Rule
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"
Reference 2: Gurvits (2003), "Classical deterministic complexity of Edmonds' problem and Quantum Entanglement"
Reference 3: Gharibian (2009/2018), "Strong NP-Hardness of the Quantum Separability Problem"
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:
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.
Vague overhead (Fail): The
bit_sizeoverhead 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.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.
Missing symbol definition: The scaling note references "xi" without prior definition.
Example is minimal but adequate: The l=2 example is worked through, though the threshold zeta-eta is left unspecified even in the example.
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
GiggleLiu commentedon Mar 20, 2026
Closing as part of batch cleanup.