{"id":"ea2e840e-0aff-4eb3-af29-587a2956b75a","arxiv_id":"2411.18137","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The problem of deciding whether a given coin appears in the greedy solution for a target amount is P-complete under log-space reductions.","lead":"This paper introduces the Greedy Coin Change decision problem and proves it is P-complete under log-space reductions. The result means that, unless P equals NC, simulating the greedy coin algorithm is inherently sequential and has no efficient parallel or low-space implementation.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.6's final step does not prove that the query coin c* is the largest denomination at the halting configuration; if any j=T coin exceeds c* while still fitting, the reduction can fail even when M accepts.","rationale":"The central reduction is credible: the coin set is constructed so that greedy selections mimic Turing-machine transitions, and the time-step shifts in the coin values plausibly separate coins from different steps. The reader's identified weakest assumption is indeed the load-bearing gap. Lemma 3.7 gives a case analysis for intermediate amounts during a transition, but the proof of Lemma 3.6 stops after noting that c* matches the first three cells of the accepting configuration. It does not establish maximality of c* among all denominations at time T, which is necessary to conclude that the greedy algorithm actually selects c*. My own analysis suggests the maximality claim is true and can be proved with the same digit-comparison technique used in Lemma 3.7, but the paper as written leaves it to the reader. The other issues mentioned by the reader (missing membership-in-P argument and a citation error) are also present, but they are less central: membership in P follows immediately by simulating the greedy algorithm with division rather than one coin at a time, and the citation error is immaterial to correctness. Because the final maximality step is provable yet unproven, a conditional acceptance is appropriate; no change to the reader's verdict is needed.","tokens_in":11500,"tokens_out":32124,"duration_ms":276989,"concrete_test":"Supply the missing maximality check for the halting configuration C_T = $(q_accept⊥)⊥a_4...a_T at j=T. For each coin type (copy, transition, left-end) and each time step, compare c* = $(q_accept⊥)⊥0^{T-3} with C_T and verify that no coin c satisfies c* < c ≤ C_T. In particular: (i) left-end coins start with (q$)>$, hence exceed C_T; (ii) transition coins with i≥3 start with 0, so they are below c*; (iii) for i=2, a coin with third digit >⊥ exceeds C_T, while a third digit ≤⊥ makes it at most c*; (iv) copy coins are bounded by alphabet values and cannot exceed c*. Independently, run a brute-force enumeration of all coin values for small T and several B to confirm that no c with c* < c ≤ C_T exists.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1.1 relies on Lemma 3.7 to guarantee that, at every intermediate amount during a simulated transition, the intended coin is the largest denomination not exceeding the remainder. The paper then concludes Lemma 3.6 by noting only that the query coin c* 'matches the configuration of the first three tape cells' at time T. This is insufficient: at the halting configuration the greedy algorithm must select the largest coin less than or equal to the full remaining amount C_T, and c* has zeros in positions 4..T while C_T generally does not. One must rule out all j=T coins with value greater than c* yet still at most C_T. Candidate threats include: transition coins with i=2 and a larger third digit; left-end transition coins whose leading digit (q$) exceeds $; and any coin from an earlier time step whose larger shift makes it too big. These can be excluded using Propositions 3.3 and 3.4 together with the time-step shift separation, but the paper never supplies this case analysis. Without it, the 'if' direction of Lemma 3.6 is unsupported: the fact that M accepts does not formally imply c* is included in the greedy set.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Greedy Coin Change (GCC) decision problem—given a target amount W, a set of denominations C, and a query coin c*, decide whether the greedy algorithm selects c*—and claims that GCC is P-complete under log-space reductions. The hardness proof constructs, for an arbitrary polynomial-time Turing machine M and input x, a coin-change instance whose initial amount encodes the initial configuration and whose coins encode local tape transitions (copy coins, transition coins, and left-end coins) at each time step. The intended correctness route is that Lemma 3.7 shows greedy simulates each machine transition, and Lemma 3.6 concludes that the query coin is selected exactly when M accepts. The reduction is clever and the paper is clearly written, but the proof as it stands has two load-bearing gaps: it never establishes membership of GCC in P, and the final query-coin step of Lemma 3.6 does not fully justify that c* is the unique largest admissible coin at the halting configuration.","tokens_in":11768,"tokens_out":19715,"duration_ms":171226,"significance":"If the theorem is correct, GCC is a natural P-complete problem that reflects the inherently sequential nature of the greedy algorithm, in the same spirit as Lexicographically First Maximal Independent Set. The main strength of the paper is the reduction idea: encoding configurations as time-shifted base-B blocks and coins as local rewriting rules is original and, with the case analysis in Lemma 3.7, largely convincing. The paper also correctly explains the parallel-complexity consequences under the NC vs. P separation. However, the two missing pieces noted below are not cosmetic: P-completeness requires both membership in P and a complete hardness proof. Both gaps are repairable within the scope of the manuscript, so the result is promising but not yet established.","major_comments":[{"comment":"The proof of Theorem 1.1 only establishes P-hardness: it constructs a log-space reduction from an arbitrary language in P to GCC. To conclude P-completeness, the paper must also show that GCC belongs to P. This is not immediate because a naive simulation of the greedy algorithm can take W/min(C) steps, which is exponential in the input length when W is encoded in binary. A short argument suffices: at any point, the largest coin v not exceeding the current remainder R is used floor(R/v) times, and the next remainder is R mod v; since the successive coin values strictly decrease, there are at most |C| iterations, and each iteration requires only comparisons and division. I recommend adding an explicit lemma proving GCC ∈ P before the statement of Theorem 1.1.","section":"Theorem 1.1, Section 3.3"},{"comment":"The 'if' direction of Lemma 3.6 is incomplete. After inductively applying Lemma 3.7, the remaining amount is C_T, the halting configuration. The paper only observes that c* 'matches the configuration of the first three tape cells' when M accepts, but matching is not the same as being the largest coin not exceeding C_T. The greedy algorithm selects the largest denomination at most C_T, so the authors must rule out all coins with value in (c*, C_T]. Candidate threats include: (i) T-time-step transition coins with i=2 and a third digit larger than ⊥; (ii) left-end transition coins whose leading (q$) digit exceeds $; and (iii) coins from earlier time steps whose larger shift places their value above C_T. Item (iii) follows from the B^T shift separation, and items (i)–(ii) can be excluded by comparing leading digits using Propositions 3.3 and 3.4, but this case analysis is absent. Without it, the statement that M accepts implies c* ∈ G is unsupported. Please add the missing maximality proof.","section":"Lemma 3.6, Section 3.3"}],"minor_comments":[{"comment":"Definition 2.3 first defines GCC as a function problem ('output the greedy set') and then introduces the decision version. The decision version should be phrased as a yes/no question: given W, C, and c*, is c* in the greedy set? The current wording is slightly confusing.","section":"Definition 2.3"},{"comment":"In Definition 2.1, the standing assumption that a coin of value 1 is always in C is stated for the classic optimization problem CC. This assumption is not needed for GCC and is in fact not satisfied by the coin set constructed in the reduction. Please state explicitly that the coin-1 convention applies only to CC, not to GCC.","section":"Section 2.1"},{"comment":"In the proof of Lemma 3.7, the sentence 'The case where j = T is easier as there are no negative terms in the coin values' is confusing, since the lemma describes a transition from time step j to j+1 and for j=T there is no next time step. Either clarify that the lemma is intended for j ≤ T-1, or remove the sentence.","section":"Lemma 3.7"},{"comment":"In the proof of Theorem 1.1, the discussion of converting from base B to base 2 should first fix B as a constant power of two (B = 2^m with m = O(1)) before claiming that each base-B digit maps to O(1) binary bits; as written, the wording is slightly circular.","section":"Theorem 1.1 proof"},{"comment":"The citation [GHN20] is used for the claim about improved algorithms for the change-making problem, but the listed title concerns orthogonal range reporting and text indexing, which appears to be a citation error. Also, 'Person proposed' on page 1 should read 'Pearson proposed'.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper presents a promising P-completeness result with a novel reduction. The two major issues—the missing membership-in-P proof and the incomplete maximality argument in Lemma 3.6—are both local and repairable, so I do not see a fundamental flaw in the reduction idea. The authors should, however, also verify the citation for [GHN20] and tighten the j=T discussion in Lemma 3.7. If the authors supply the missing proofs and clarifications, the paper would be suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hey, quick take on arXiv:2411.18137. The Greedy Coin Change problem is a genuinely new P-completeness result: first decision version of greedy coin selection, shown hard under log-space reductions. The construction is a textbook generic TM simulation, with a neat trick of local transition coins and shifting time layers. The high-level proof strategy is sound, and the paper is readable.\n\nWhat's actually new: the problem itself and the P-completeness theorem. It joins LFMIS and friends as a natural greedy P-complete problem. If correct, it's a useful addition to the toolbox for parallel complexity arguments.\n\nSoft spots: First, membership in P is never explicitly shown. It's easy—for each denomination in descending order, divide the remaining amount—but the paper should state it. Second, the final step of Lemma 3.6 is under-argued. The paper asserts that c* is selected at the halting configuration because it matches the first three tape cells, but it doesn't prove that no other j=T coin is larger and still fits. The stress-test concern is real as a gap: you need a short case analysis with Propositions 3.3 and 3.4 to rule out copy coins with leading digit $ (they blow up at the second digit) and transition coins with larger pairs. My own check says that case analysis goes through, so the proof is fixable, but the text doesn't supply it. Third, [GHN20] is cited as the follow-up to Chan-He on coin change, but the reference is an unrelated range-reporting paper; that's a clear citation error. Also, the bound T = C_M n^ℓ for small inputs is hand-waved, but that's a standard padding fix.\n\nNone of these are load-bearing. The core reduction is convincing, and the missing pieces are straightforward. The paper deserves a serious referee and probably acceptance after minor revisions. I'd bring it to the reading group and would cite it if I were working on P-completeness.","headline":"A solid new P-completeness result with a few easily repairable gaps in exposition.","tokens_in":12234,"tokens_out":7848,"would_cite":true,"duration_ms":69018,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68Q17","68W10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that asking whether the greedy coin-change algorithm selects a given coin is P-complete under log-space reductions.","keywords":["greedy algorithm","coin change","change-making problem","P-completeness","log-space reduction","parallel complexity","Turing machine simulation","NC"],"falsifier":"Enumerate every coin of the form $c_{\\mathrm{transition}}(q,a_-,a,a_+,i,T)$ and the query coin $c^*$ for a small accepting machine, compare them against the final remaining change amount of the simulated halting configuration, and check whether $c^*$ is strictly the largest fitting denomination; a single larger fitting coin would mean the greedy run diverges from the accepting simulation and the reduction would fail.","tokens_in":11345,"feed_emoji":"🪙","tokens_out":9432,"duration_ms":79316,"temperature":0.7,"pith_summary":"The paper introduces a decision version of the familiar greedy coin-change rule: given denominations, a target amount, and one queried coin, will the greedy rule — repeatedly taking the largest denomination that fits — ever use that coin? It proves that this decision problem is complete for P, the class of polynomial-time-decidable problems, under reductions that use only logarithmic space. The result matters because it makes the greedy rule's sequential character precise: unless the polynomial-time problems are all efficiently parallelizable, no substantially parallel algorithm can reproduce its choices, and unless they are all log-space solvable, no substantially space-limited algorithm can. The proof encodes an arbitrary polynomial-time Turing machine into the coin system, so the greedy run becomes a step-by-step simulation of the machine.","feed_headline":"Greedy coin change is P-complete, so likely not parallelizable","feed_subtitle":"Asking whether greedy change picks one named coin can encode any polynomial-time computation.","key_machinery":"The central object is a coin set built from base-B blocks, with each block representing one tape cell of a Turing-machine configuration. There are copy coins, transition coins, and a left-end transition coin; subtracting a coin from the current change amount moves a block from the higher configuration range to a lower range, which is exactly one local transition of the machine. The initial target amount is the start configuration shifted to the top range, and the query coin is the transition that would produce the accepting halting configuration. The reduction works because each coin's leading digits are arranged so that, when base-B blocks are compared, the largest coin that fits the current remainder is always the intended local transition.","core_discovery":"On the paper's own terms, the central discovery is that the Greedy Coin Change problem is P-complete under log-space reductions. For any language decided by a polynomial-time Turing machine and any input, the authors construct a coin set and target amount whose greedy solution mirrors the computation of that machine. The remaining change amount at each step encodes the current configuration, and each coin encodes one local tape transition: copying an unchanged cell, applying the transition function at the head, or handling the left endmarker. The queried coin is included in the greedy set exactly when the simulated machine reaches its accepting halting configuration. Membership in P is immediate because a single greedy run is itself a polynomial-time process.","pith_inferences":["A concrete check of the reduction is to instantiate it for a small accepting machine and compare every greedy choice against the intended transition; a divergence at any unexamined coin would locate the exact point where the local-maximality argument needs strengthening.","Because the output coin set is highly repetitive, the same encoding may yield hardness results for succinctly represented coin systems, where the coin list is given implicitly rather than explicitly.","The block-shift trick is likely transferable to other 'take the largest feasible item' greedy rules with local update structure, suggesting that similar P-completeness results may hold for greedy variants of scheduling or packing problems."],"forward_implications":["The decision version of the Greedy Coin Change problem is P-complete under log-space reductions, placing it among the hardest problems in P for that reduction notion.","Unless P collapses to NC, the class of problems solvable in polylogarithmic parallel time, no parallel algorithm with polynomially many processors can simulate the greedy rule on arbitrary coin systems.","Unless P collapses to L, the class of problems solvable in logarithmic space, no Turing machine using only logarithmic space can decide whether the greedy rule uses a queried coin.","Any polynomial-time computation can be read off from a greedy coin-change run, because the constructed coin system simulates an arbitrary polynomial-time Turing machine step by step."],"supporting_citations":[{"why":"defines log-space transducers and the theorem that log-space reducibility preserves membership in NC and L","marker":"[Sip96]"},{"why":"introduces P-completeness and the lexicographically-first maximal independent set as a model greedy problem","marker":"[Coo85]"},{"why":"supplies the standard P-completeness theory that frames the result's significance for parallel computation","marker":"[GHR95]"},{"why":"introduces the change-making problem and the greedy algorithm, the object whose behavior is classified here","marker":"[CG70]"},{"why":"gives tight bounds for when greedy coin change fails, the background against which this hardness result is stated","marker":"[KZ94]"}],"fun_headline_variants":["Greedy coin change is P-complete, killing parallel hopes","P-completeness hits greedy coin change: no fast parallel fix","Greedy coin change encodes all of P, so no easy parallel","When greedy coins go wrong: P-complete, not parallel-friendly","Greedy change problem is P-complete: parallelization unlikely"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reduction stands or falls on the claim that at every intermediate change amount the intended copy, transition, or left-end coin is strictly the largest denomination no larger than the current remainder; the proof's final maximality step for the halting configuration checks only the first three tape cells.","fun_headline_variants_meta":{"raw":{"variants":["Greedy coin change is P-complete, killing parallel hopes","P-completeness hits greedy coin change: no fast parallel fix","Greedy coin change encodes all of P, so no easy parallel","When greedy coins go wrong: P-complete, not parallel-friendly","Greedy change problem is P-complete: parallelization unlikely"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000135,"raw_usage":{"total_tokens":1103,"prompt_tokens":867,"completion_tokens":236,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":483,"completion_tokens_details":{"reasoning_tokens":144}},"tokens_in":483,"tokens_out":236,"duration_ms":2975,"temperature":1.0,"reasoning_tokens":144,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:30:32.763392+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate every coin of the form $c_{\\mathrm{transition}}(q,a_-,a,a_+,i,T)$ and the query coin $c^*$ for a small accepting machine, compare them against the final remaining change amount of the simulated halting configuration, and check whether $c^*$ is strictly the largest fitting denomination; a single larger fitting coin would mean the greedy run diverges from the accepting simulation and the reduction would fail.","supporting_citations":[],"review_version":1}