{"id":"fa2e12d4-d5f3-4348-9959-a64bc22623c0","arxiv_id":"2411.18590","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Recoverable robust optimization with discrete budgeted uncertainty is Sigma-3-p-complete for a broad class of NP-hard nominal problems, via new blow-up SSP reductions.","lead":"This paper proves that recoverable robust versions of 24 classic NP-hard optimization problems are complete for the third level of the polynomial hierarchy under discrete budgeted uncertainty. It introduces a reusable reduction framework that traces these hardness results to a single abstract property, while leaving some appendix reductions with gaps.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 13's partition property fails for the paper's Partition and Dominating Set reductions, so the claimed Σ3^p-completeness for those problems is not proven.","rationale":"The reader's weakest assumption is exactly the load-bearing issue: the blow-up preserving condition in Definition 13 is what lets distances be inherited along the reduction chain, and if a reduction is not even an SSP reduction, the solution-set bijection breaks down. The counterexamples for Partition and Dominating Set are small, concrete, and use instances the reductions must handle. They invalidate the proof of Theorem 17 for at least Partition, Scheduling (via Partition), and Dominating Set; the Feedback Arc Set reduction is similarly suspect. These are localized gaps rather than a collapse of the whole framework: Theorem 9's main reduction from R-Adj-Sat to Comb.RR and the base blow-up reductions in Section 5.1 and Appendix A appear internally coherent, and the cost-version reduction (Theorem 10) is plausibly repairable by adding an explicit bounded-cost assumption. Since the reader already assigned CONDITIONAL, my stress-test does not move the verdict; the paper should be accepted only after the defective reductions are corrected or replaced and the missing cost assumption is stated.","tokens_in":34172,"tokens_out":13315,"duration_ms":125423,"concrete_test":"Run an exhaustive checker on the two contested reductions. For the Partition reduction, enumerate all subsets of {1,5,2,6} with sum 7 and test whether 6 is contained in every such subset; it is not, since {5,2} is a solution. For the Dominating Set reduction, take the one-edge graph on {u,v}, set k=2, and enumerate all dominating sets of size at most 2 in the constructed graph; at least one such set (e.g., {w1,w2}) contains no original vertex, so Equation (1) fails. Either failure settles that the reduction does not satisfy Definition 13 and Theorem 14 cannot be applied.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim depends on Theorem 14, which requires every blow-up preserving reduction to split new universe elements into f(U), Uon (always in solutions), or Uoff (never in solutions). Two appendix reductions violate this requirement, so the affected problems are not covered by Theorem 17.\n\nPartition (Appendix B): the reduction from Subset Sum adds y=M+1 and x=Σa_i+1−M and declares Uon={x}. For the subset-sum instance {1,5}, M=1, the partition instance has solutions {1,6} and {5,2}; x=6 is not in the second solution, so Uon is false. More seriously, the reduction is not an SSP reduction: the partition solution {5,2} intersects f(U)={1,5} in {5}, which is not a subset-sum solution for target 1, contradicting Equation (1). Hence Partition and Scheduling (which is reduced from Partition) are unsupported.\n\nDominating Set (Section 6.1): the VC-to-DS reduction adds |V|+1 edge vertices and puts them all in Uoff. For the one-edge graph with k=2, {w1,w2} is a dominating set of size 2, so edge vertices do occur in solutions. Its intersection with f(V) is empty, which is not a vertex cover, again violating Equation (1). The Feedback Arc Set reduction in Appendix B has the same structural weakness: its subdivided arcs are claimed Uoff but can be chosen when deleting arcs to break cycles for larger k.\n\nA secondary gap is Theorem 10: defining blocked costs as 2t(I)+1 requires 2t(I)+1 ≥ d(I)(u) for all blocked u, which is neither stated nor implied by the LOP definition. This is fixable by stating/ensuring nonnegative bounded costs, but as written the reduction to the cost version is missing an assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops an abstract framework for proving Σ3^p-completeness of recoverable robust optimization problems with discrete budgeted uncertainty. It formalizes linear optimization problems, SSP problems, SSP reductions, blow-up SSP reductions, and blow-up-preserving SSP reductions. The main reduction (Theorem 9) goes from R-Adj-Sat to the combinatorial recoverable robust problem of any SSP-NP-hard problem admitting a blow-up SSP reduction from 3Sat, and Theorem 10 transfers the hardness to the cost-based recoverable robust problem. Section 5.1 presents a blow-up SSP reduction from 3Sat to Vertex Cover and states analogous reductions for independent set, subset sum, directed Hamiltonian path, two directed disjoint paths, and Steiner tree. Section 6 and Appendix B then use blow-up-preserving reductions to extend the result to a list of 24 nominal problems and three distance measures: κ-addition, κ-deletion, and Hamming distance.","tokens_in":34502,"tokens_out":10572,"duration_ms":100741,"significance":"If the framework and the reduction list are correct, the paper would be a substantial unification: it would show that recoverable robust versions of many unrelated NP-complete problems are Σ3^p-complete for the same structural reason, and it would rule out compact IP formulations for all of them under NP ≠ Σ3^p. The main reduction in Theorem 9 is conceptually clean and mostly correct, and the blow-up gadget in Section 5.1 is a useful reusable device. However, the claimed full list is not currently established: three of the preserving reductions — Dominating Set, Partition, and Feedback Arc Set — violate Definition 13, and the consequences for Scheduling via Partition are also unsupported. The significance of the paper therefore hinges on repairing or removing these reductions.","major_comments":[{"comment":"The reduction from Vertex Cover to Dominating Set is claimed to be blow-up preserving with Uoff equal to the set of added edge vertices. This is false. In the instance consisting of a single edge {u,v} with k=1, the added vertex w_{uv}^1 alone dominates u', v', and itself, so it is a dominating set of size 1. Thus added edge vertices do occur in valid solutions, contradicting the definition of Uoff. Moreover, the SSP equality in Claim 18 fails for this instance: the dominating set {w_{uv}^1} has empty intersection with f(V), which is not a vertex cover of the original graph, violating Eq. (1). Consequently, Theorem 14 cannot be applied, and the Σ3^p-hardness of recoverable robust Dominating Set is not established.","section":"Section 6.1, Claim 19"},{"comment":"The reduction from Subset Sum to Partition declares Uon = {Σa_i + 1 − M} and Uoff = {M + 1}. For the Subset Sum instance {1,5} with M=1, the constructed Partition instance has total sum 14 and target 7; the set {5,2} is a valid side of a partition. Its intersection with f(U) = {1,5} is {5}, whose sum is not M, so Eq. (1) fails. The element x = Σa_i + 1 − M = 6 is not in every partition solution, and y = M + 1 = 2 is in this particular solution, so both Uon and Uoff are false. Therefore the blow-up-preserving chain from Subset Sum to Partition, and then to Two-Machine Scheduling, is unsupported, and RR-Partition and RR-Scheduling are not covered by Theorem 17.","section":"Appendix B, Partition"},{"comment":"The reduction from Vertex Cover to Feedback Arc Set puts all subdivided arcs between v'_1 and w'_0, and between w'_1 and v'_0, into Uoff. For a single-edge vertex-cover instance with k=1, the constructed directed graph has one directed cycle v'_0 → v'_1 → w'_0 → w'_1 → v'_0 (with subdivisions). Deleting a single subdivision arc on the path v'_1 → w'_0 makes the graph acyclic, giving a feedback arc set of size 1 whose intersection with f(V) is empty. Such a solution does not correspond to a vertex cover, so Eq. (1) fails and the subdivided arcs are not in Uoff. Thus the claimed blow-up-preserving reduction is invalid, and RR-Feedback Arc Set is not covered.","section":"Appendix B, Feedback Arc Set"},{"comment":"The reduction from Comb.RR-Π' to RR-Π sets the upper cost of every u ∈ B to 2t(I)+1 and the threshold to t' = 2t(I). For this to make blocked elements prohibitively expensive, one needs 2t(I)+1 ≥ d(I)(u) for every blocked u, together with suitable nonnegativity assumptions; otherwise the 'blocked' upper bound can be lower than the nominal cost, and the simulation of blockers fails. The proof neither states nor derives such a condition. This gap is patchable, for instance by defining the upper cost as max(d(I)(u), 2t(I)+1) and adjusting the threshold, but as written Theorem 10 is not fully proved for arbitrary LOP problems.","section":"Theorem 10"}],"minor_comments":[{"comment":"The line 'we have S1 ∩ fφ(Y) = S2 ∩ fφ(Y) by the property of a blow-up reduction' should refer to fφ(LX), not fφ(Y), because the blow-up property is defined for Lb = LX. The subsequent notation A2 ∩ (X ∪ X) = AX is also confusing and should be written in terms of LX.","section":"Theorem 9, reverse direction"},{"comment":"Claim 19 is titled 'The reduction from above from Vertex Cover to Dominating Set is an SSP reduction', but the intended statement is that the reduction is blow-up preserving; the wording duplicates Claim 18 and should be corrected.","section":"Claim 19"},{"comment":"The SSP definition of Set Cover declares the universe to be {S_i | i = 1,...,n}, but the solution set is then defined as subsets S ⊆ ⋃_i S_i. A set cover solution should be a subfamily of the sets {S_i}; as written, the formal definition is inconsistent with the mapping f(v) = S_v used in the reduction.","section":"Appendix B, Set Cover definition"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the paper builds heavily on the authors' own earlier work [19,21]. That is not improper, but it increases the importance of checking the new reductions independently, since the current manuscript contains concrete counterexamples to three of the claimed blow-up-preserving reductions. If those reductions cannot be repaired, the published version should either remove the affected problems from Theorem 17 or replace the reductions with valid ones. The main framework itself appears promising and the central reduction from R-Adj-Sat is essentially sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea is good: define blow-up SSP reductions and blow-up preserving SSP reductions, then show that one reduction from R-Adj-Sat yields Sigma_3^p-hardness for any problem carrying the right structure. That is a real step beyond problem-specific proofs, and the main reduction in Theorem 9 is mostly coherent. The new reduction notions are the paper's real contribution, and the vertex-cover blow-up gadget in Section 5.1 is carefully argued.\n\nBut the full theorem as stated is not established. I checked the appendix counterexamples from the stress test, and they hold. In the Dominating Set reduction, with k larger than the minimum, edge-gadget vertices can appear in dominating sets of size at most k: for a single edge and k=2, the set {w1,w2} dominates, its intersection with f(V) is empty, and that empty set is not a vertex cover. So Claim 19's Uoff is false, and the reduction is not SSP. The Feedback Arc Set reduction has the same structural weakness. In the Partition reduction from Subset Sum, the extra numbers do not behave as claimed: for {1,5}, M=1, the partition instance has solutions {1,6} and {5,2}; the element 6 is not in every solution, and the intersection {5} is not a subset-sum solution for target 1. These are not typos; the reductions do not satisfy Definition 13 and Theorem 14, so the affected problems are not covered by the framework as written.\n\nTheorem 10 has a separate gap. The reduction from Comb.RR to RR sets c1 = d(I), blocked costs to 2t(I)+1, and threshold to 2t(I). Even with nonnegative costs, the reverse direction does not imply S1 is in S(I): from c1(S1)+c2(S2) <= 2t(I) you only get c1(S1) <= 2t(I), not d(I)(S1) <= t(I). The proof's \"thus\" is doing unsupported work. This needs a real fix, not just an added assumption.\n\nBottom line: the framework is plausible and likely salvageable, and the core Theorem 9 reduction is worth keeping. But the manuscript overclaims in Theorem 17, and the cost-version reduction is incomplete. It deserves a serious referee, with major revision required: repair or drop the failing reductions, and prove Theorem 10's equivalence correctly.","headline":"A genuinely useful framework with a mostly coherent core reduction, but the full 24-problem completeness list is not proven: several appendix reductions violate the blow-up-preserving premise, and Theorem 10's cost-reduction argument has a gap.","tokens_in":35052,"tokens_out":8734,"would_cite":true,"duration_ms":85100,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q15","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"For 24 classic problems, recoverable robust optimization is Sigma-3-p-complete","keywords":["recoverable robust optimization","polynomial hierarchy","Sigma-3-completeness","discrete budgeted uncertainty","min-max-min problems","compact integer programming","SSP reductions","two-stage optimization"],"falsifier":"Inspect the reductions labelled blow-up preserving in the paper's own presentation. For the Subset Sum-to-Partition reduction, take any small instance and check whether the element 'sum of all numbers + 1 minus M' belongs to every balanced partition; a single balanced partition omitting it refutes the 'always-in' classification. For the Vertex Cover-to-Dominating Set reduction, check whether any added edge vertex can belong to a dominating set of size k'; if so, the 'never-in-solution' classification fails.","tokens_in":33957,"feed_emoji":"","tokens_out":5082,"duration_ms":42880,"temperature":0.7,"pith_summary":"This paper claims that for each of 24 classic NP-complete problems—satisfiability, vertex cover, dominating set, subset sum, TSP, Steiner tree, and others—the recoverable robust optimization problem under discrete budgeted uncertainty is $\\Sigma^p_3$-complete (complete for the third level of the polynomial hierarchy). This holds for all three standard distance measures: $\\kappa$-addition, $\\kappa$-deletion, and Hamming. The result matters because a $\\Sigma^p_3$-complete problem admits no compact (polynomial-size) integer programming formulation unless $\\mathrm{NP} = \\Sigma^p_3$, so these models are fundamentally hard to express. The paper's main contribution is showing that all these problems are hard 'for the same reason': they satisfy an abstract property that forces their recoverable robust counterparts to be $\\Sigma^p_3$-complete.","feed_headline":"24 robust problems land in Sigma-3-p-complete","feed_subtitle":"One abstract reduction property unifies the hardness of all these problems under discrete budgeted uncertainty.","key_machinery":"The load-bearing device is the blow-up SSP reduction: an SSP reduction from 3-SAT to a problem $\\Pi$ that, for a chosen set $L_b$ of literals closed under negation, builds an instance with a polynomial blow-up factor $\\beta$ such that two solutions have distance at most $\\beta$ iff they agree on the image of $L_b$. Because blow-up SSP reductions are not transitive, the paper adds the blow-up preserving SSP reduction, which only introduces elements that are always or never in solutions, preserving distances exactly. These two gadgets compose into a reduction tree rooted at 3-SAT and yield $\\Sigma^p_3$-hardness of the combinatorial recoverable robust problem, which a short reduction converts into completeness for the cost-based recoverable robust problem.","core_discovery":"On its own terms, the central claim is that the recoverable robust version of every listed nominal problem is $\\Sigma^p_3$-complete under discrete budgeted uncertainty, for each of the three distance measures. More generally, the paper identifies a sufficient abstract condition: if an SSP problem is blow-up SSP reducible from 3-SAT and the reduction chain can be extended by blow-up preserving SSP reductions, then the combinatorial recoverable robust problem is $\\Sigma^p_3$-hard; a short cost-gadget reduction transfers this hardness to the standard linear recoverable robust problem. The paper proves this transfer and applies it to 24 problems, thereby unifying and extending known $\\Sigma^p_3$-completeness results for clique/independent set, TSP, shortest path, and others.","pith_inferences":["If the reduction premises are repaired for the affected problems, the same abstract property would likely apply to further NP-complete problems beyond the 24 listed, since only a handful of base reductions are needed.","The result suggests that recoverable robust versions of even polynomial-time nominal problems, such as shortest path, may be $\\Sigma^p_3$-complete when a distance constraint is added; the paper cites one such case, and the framework's logic points to more.","The near-absence of compact IP formulations for these problems redirects practical research toward approximation algorithms, heuristics, or restricted uncertainty sets rather than exact compact modeling."],"forward_implications":["Every one of the 24 recoverable robust problems listed in the paper, with any of the three distance measures, is $\\Sigma^p_3$-complete under discrete budgeted uncertainty.","None of these problems admits a compact integer programming formulation unless $\\mathrm{NP} = \\Sigma^p_3$, so exact solution via standard compact IP models is inherently blocked.","The framework supplies a reusable certificate: a new nominal problem only needs to be shown blow-up SSP reducible from 3-SAT, or blow-up preserving reducible from an already classified problem, to inherit $\\Sigma^p_3$-completeness.","The three distance measures are covered by a single mechanism because the blow-up gadget is compatible with $\\kappa$-addition, $\\kappa$-deletion, and Hamming distances."],"supporting_citations":[{"why":"Supplies the SSP and SSP reduction framework and the base list of SSP-NP-complete problems that this paper extends.","marker":"[21]"},{"why":"Provides R-Adj-Sat, the $\\Sigma^p_3$-complete problem used as the starting point of the hardness reduction.","marker":"[19]"},{"why":"Provides the classical 3-SAT to Vertex Cover reduction modified into the first blow-up SSP reduction.","marker":"[16]"},{"why":"Provides the classical reductions (to Set Cover, Hitting Set, Feedback Vertex Set, Partition, and others) converted into blow-up preserving SSP reductions.","marker":"[29]"},{"why":"Provides the 3-SAT to Directed Hamiltonian Path reduction used for the directed Hamiltonian path and cycle chain.","marker":"[1]"},{"why":"Provides the reduction from 3-SAT to Directed Two Disjoint Path that is extended with a blow-up gadget.","marker":"[15]"},{"why":"Provides the Vertex Cover to Uncapacitated Facility Location reduction reused for p-center and p-median.","marker":"[12]"}],"fun_headline_variants":["24 robust problems land in Sigma-3-p-complete","Recoverable robust tasks jump to Sigma-3-p-complete uniformly","No compact IPs: 24 recoverable robust problems are Sigma-3-p-complete","Unified proof: robust SAT, TSP, clique all Sigma-3-p-complete"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument rests on every reduction chain beyond the first blow-up reduction being a blow-up preserving SSP reduction: each newly introduced universe element is either in every solution or in no solution, so the distance between solutions is unchanged; if one of the listed reductions violates this partition property, the hardness proof for that problem does not go through.","fun_headline_variants_meta":{"raw":{"variants":["24 robust problems land in Sigma-3-p-complete","Recoverable robust tasks jump to Sigma-3-p-complete uniformly","No compact IPs: 24 recoverable robust problems are Sigma-3-p-complete","Unified proof: robust SAT, TSP, clique all Sigma-3-p-complete"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000613,"raw_usage":{"total_tokens":2877,"prompt_tokens":999,"completion_tokens":1878,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":615,"completion_tokens_details":{"reasoning_tokens":1803}},"tokens_in":615,"tokens_out":1878,"duration_ms":13105,"temperature":1.0,"reasoning_tokens":1803,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:05:57.316443+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Inspect the reductions labelled blow-up preserving in the paper's own presentation. For the Subset Sum-to-Partition reduction, take any small instance and check whether the element 'sum of all numbers + 1 minus M' belongs to every balanced partition; a single balanced partition omitting it refutes the 'always-in' classification. For the Vertex Cover-to-Dominating Set reduction, check whether any added edge vertex can belong to a dominating set of size k'; if so, the 'never-in-solution' classification fails.","supporting_citations":[{"cited_title":"Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the SSP and SSP reduction framework and the base list of SSP-NP-complete problems that this paper extends."},{"cited_title":"On the complexity of robust multi-stage problems with discrete recourse","cited_arxiv_id":null,"evidence_quote":"Provides R-Adj-Sat, the $\\Sigma^p_3$-complete problem used as the starting point of the hardness reduction."},{"cited_title":"The uncapicitated facility location problem","cited_arxiv_id":null,"evidence_quote":"Provides the Vertex Cover to Uncapacitated Facility Location reduction reused for p-center and p-median."}],"review_version":1}