| paper | d4-conf-sagt-2025-0022 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Block detection is weakly \(\mathrm{NP}\)-complete; testing pair-size stability is weakly \(\mathrm{coNP}\)-complete, even when \(\tau=K=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given courses \(C\) with integral credits \(O(c)\), types \(T\) with rational masses \(\mu_t\) summing to \(1\), rational per-capita capacities \(q_c\), and an explicit allocation \(x_{t,A}\) of each type's mass to feasible integral bundles \(A\), decide whether the allocation is pair-size-stable. A block exists if some positive mass assigned to \(A\) can switch to \((A\setminus D)\cup\{c\}\), where \(c\notin A\), the type prefers \(c\) to every course in \(D\subseteq A\), \(O(c)\ge O(D)\), and \(O(A)-O(D)+O(c)\le T_t\); course \(c\) must have spare capacity or be able to replace lower-priority mass.
Represent interchangeable students by types carrying rational mass, with each type specifying its course rankings, credit limit, and course-priority class. The variables \(x_{t,A}\) assign mass to integral bundles, and rational course capacities scale with the cohort. A deviation moves positive mass from a bundle by dropping courses and taking one preferred course, subject to the paper's pair-size credit conditions and course acceptance.
The paper assumes strict course rankings over named students, while pooling a cohort into one type requires equal priority within that type; the case names priority classes but does not fully justify this departure from the strict-ranking assumption.
fatal: False
The mirror covers the pair-size stability verification component of Theorem 1. It leaves the other verification results, stable-matching existence and construction, maximum-size matching, master-list variants, and lower-quota results aside.
The strongest case I believe is narrow: a continuous version of pair-size stability verification, rather than a mirror of every result in the paper.
Consider a large university cohort whose members share the same complete course type: the same acceptable courses, strict ranking, credit limit, and relevant course-priority class. Let the society be given by rational type masses \(\mu_t\), with \(N\gg\tau\); the clearest case has \(\tau=1\), while \(N\) can be arbitrarily large. Each individual still receives an integral bundle of courses. The allocation records how much mass of each type receives each bundle: \(x_{t,A}\ge0\), with \(\sum_A x_{t,A}=\mu_t\). Course loads are mass totals, constrained by rational per-capita capacities \(q_c\). This fits settings with large standardized cohorts and shared course choices. It continuizes the population while keeping courses and each person’s bundle discrete.
My lead anchor is Theorem 1, proved in this paper. It states that ca-fc-test, ca-c-test, and ca-ps-test are weakly co-NP-complete. I rely on its ca-ps-test result: deciding whether a given matching is pair-size-stable is weakly co-NP-complete. The proof reduces from Subset Sum using one student with credit limit \(W=\sum_i w_i\), one course \(c_i\) of credit value \(w_i\) for each item, and a course \(b\) of credit value \(K\), where each course has upper quota \(1\). The student ranks \(b\) above all the \(c_i\), and the matching assigns the student to every \(c_i\). The matching fails pair-size stability exactly when some subset of the \(c_i\) has total credits \(K\): the student can replace that subset with \(b\) without reducing her credits. The hardness is weak because the reduction uses binary-encoded credit values.
Lead problem — Continuous Pair-Size Stability Verification (\(\mathrm{CPSV}_\infty\)). An instance specifies a finite course set \(C\), integer credit values \(O(c)\), rational course capacities \(q_c\), and a finite list of types with rational masses summing to \(1\). A type \(t\) specifies its course ranking, acceptable courses, credit limit \(T_t\), and course-priority information. A proposed allocation is given explicitly as a sparse list of masses \(x_{t,A}\) assigned to feasible, integral bundles \(A\subseteq C\), satisfying \(\sum_A x_{t,A}=\mu_t\) and \(\ell_c(x):=\sum_{t,A:c\in A}x_{t,A}\le q_c\).
The question is whether this allocation is pair-size-stable. A blocking certificate consists of a type \(t\), a bundle \(A\) with \(x_{t,A}>0\), a course \(c\notin A\), a dropped set \(D\subseteq A\), and a positive mass \(\delta\) that can switch from \(A\) to \((A\setminus D)\cup\{c\}\). The type must find \(c\) acceptable and prefer it to every course in \(D\); the credit conditions are \(O(c)\ge O(D)\) and \(O(A)-O(D)+O(c)\le T_t\). The course must be able to accept that mass, through spare capacity or by replacing lower-priority mass. The output is YES if no such block exists, and NO with such a witness otherwise. Each member of a cohort receives whole courses; only the mass of a cohort split across bundles can be fractional.
The reduction behind Theorem 1 embeds directly in \(\mathrm{CPSV}_\infty\). Use one type of mass \(1\), with all \(c_i\) acceptable and ranked below \(b\); set every course capacity to \(1\); and assign the whole type mass to \(A=\{c_i\}\). Course \(b\) is empty. A positive mass can block with \(b\) precisely when some \(D\subseteq A\) has \(O(D)=O(b)=K\). Conversely, any pair-size block must use \(b\), since the type already receives every other course. Thus the continuous verifier is weakly co-NP-hard even at \(\tau=1\). With the allocation given as an explicit sparse list, a blocking certificate can be checked in polynomial time, so I expect weak co-NP-completeness. This is Class B: the hardness lives in the number of courses and their binary-encoded credit values, so population continuization does not remove it.
The mirror is recognizable as the authors’ own pair-size stability question: it preserves their credit-preserving deviation rule and changes the unit of population from named students to interchangeable cohorts. The clone interpretation is especially direct here: for any large \(N\), the mass-one type represents \(N\) identical students, and capacity \(1\) represents \(N\) seats.
This covers only the paper’s pair-size stability verification result. It does not claim a continuous solution for the paper’s stable-matching existence or maximum-size problems. It raises natural next questions: whether the weak hardness disappears when credits are polynomially bounded, how the verifier behaves with multiple types and mass distributed across many bundles, and whether the paper’s algorithm for finding a pair-size-stable matching extends to rational type masses.
The weakest point is also the anchor’s strength: its reduction uses one student, and the continuous embedding essentially clones that student. It shows a sensible high-multiplicity mirror, but not a new hardness phenomenon caused by a continuum. The original types may also be too exact to compress many real student populations. I would present this as a narrow, credible mirror whose complexity transfers—not as evidence that continuization itself makes this problem harder.
The strongest objection is to the proponent’s “direct clone” bridge. The paper assumes strict course rankings over named students. If \(N\) otherwise identical students are given distinct ranks at every course, those ranks are part of the information stability uses, so the students are not one complete type under the programme’s definition. The proposed type-level “priority class” instead makes a course indifferent among members of the class. That is a natural matching model, but it changes the paper’s strict-priority assumption. The continuous definition also treats a positive mass as the blocking deviation, whereas the paper defines a block by one student and a course. Both changes may be ones the authors would accept; they should be stated as part of the mirror rather than presented as a literal clone of their model.
That objection does not defeat the best version of the mirror. Priority classes are plausible in course allocation, and the paper itself discusses priorities based on grades and seniority. With strict priorities between classes and indifference within each class, the continuous pair-size stability question is recognizable. In the proposed one-type reduction, course priorities do not even do much work: the blocking course \(b\) is vacant, and the decision is whether some dropped bundle has total credit \(K\). The Subset Sum obstruction survives exactly. Rational mass switching is well-defined, and a blocking certificate remains checkable in polynomial time.
Nor can I dismiss the anchor because it has only one type or because its answer transfers unchanged. The programme explicitly values hardness that persists at \(\tau=1\), and a transferred answer is still a result about the continuous problem. The paper’s note that practical credits may be polynomially bounded limits the practical relevance of this *weak* hardness, but it does not make the encoded problem ill-posed or unworthy under the programme’s stated aims.
So the case against can fairly say that this anchor is narrow and depends on an explicit priority-class and mass-blocking formulation. It cannot honestly establish that no worthwhile continuous mirror exists: the pair-size stability verification mirror remains a credible counterexample to that universal claim.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.