Pith. sign in

REVIEW 2 major objections 5 minor 23 references

The Greedy Coin Change Problem

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that asking whether the greedy coin-change algorithm selects a given coin is P-complete under log-space reductions.

desk verdict A solid new P-completeness result with a few easily repairable gaps in exposition. read the letter →

arxiv 2411.18137 v1 pith:26OXI7OY submitted 2024-11-27 cs.CC

Shreya Gupta , Boyang Huang , Russell Impagliazzo This is my paper · ORCID
classification cs.CC MSC 68Q1568Q1768W10
keywords greedyalgorithmcoinchangechange-makingproblemP-completenesslog-spacereductionparallelcomplexityTuringmachinesimulationNC
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [Theorem 1.1, Section 3.3] 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.
  2. [Lemma 3.6, Section 3.3] 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.
minor comments (5)
  1. [Definition 2.3] 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.
  2. [Section 2.1] 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.
  3. [Lemma 3.7] 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.
  4. [Theorem 1.1 proof] 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.
  5. [References] 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'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the P-completeness reduction is a self-contained construction from a generic Turing machine, and the only self-citation appears in a future-work paragraph where it is not load-bearing.

full rationale

The paper's central claim, Theorem 1.1, is proved by a direct log-space reduction from an arbitrary polynomial-time Turing machine to the Greedy Coin Change decision problem. The instance construction in Section 3.2 defines the initial change amount, the copy coins, the transition coins, the left-end transition coin, and the query coin entirely in terms of the simulated machine's state set, tape alphabet, transition function, and time bound. No parameter is fitted to the target answer, and no quantity called a 'prediction' is derived from data or from the queried output. The correctness proof, Lemma 3.6, rests on Lemma 3.7, whose case analysis argues that at each intermediate change amount the intended coin is the largest denomination not exceeding the remainder. Even if, as a correctness concern, the final step of Lemma 3.6 could require a fuller maximality argument, that would be a proof gap rather than circularity: the greedy rule is not defined in terms of the query coin's membership, and the query coin is not used to select the denominations. The only self-citation in the paper, the authors' factored-graphs paper [GHI+24], appears in Section 4 as a suggested future-work analogy and plays no role in the derivation of Theorem 1.1. External results such as Theorem 2.5 are cited from Sipser and are not invoked to forbid alternative constructions. There is no self-definitional step, no fitted input renamed as a prediction, no load-bearing self-citation chain, and no imported uniqueness theorem. The derivation is therefore self-contained with respect to the P-completeness claim, and the appropriate circularity score is 0.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The construction has no data-fitted parameters. The only hand-chosen constant is the encoding base B, whose value is constrained by |Q| and |Gamma|. The proof relies on standard Turing machine normal forms and standard facts about log-space reductions. No new physical or mathematical entities are postulated.

free parameters (1)
  • Encoding base B = B=2^m with m=O(1) and B >= (s+1)k+2
    A hand-chosen construction constant so that state-alphabet pairs sort above bare alphabet digits and below B-1. It is not fitted to data and does not encode the answer, but it is a chosen parameter of the reduction.
assumptions (3)
  • domain assumption Every language in P can be decided by a deterministic single-tape TM halting within T=C_M n^ell steps and satisfying Assumptions 3.1 and 3.2.
    Invoked in Sections 3.1 and 3.2. Standard constant-factor simulation, but it is load-bearing for defining the final query coin.
  • standard math Log-space reductions compose and satisfy the closure property of Theorem 2.5.
    Used to interpret P-completeness and its consequences for NC and L. Cited from Sipser.
  • domain assumption The Greedy Coin Change decision problem is solvable in polynomial time by directly simulating the greedy algorithm with integer division.
    Needed for membership in P. The paper does not explicitly prove this, but it follows from standard polynomial-time division on binary numbers.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Greedy Coin Change Problem." pith.science (2026). https://pith.science/paper/26OXI7OY

@misc{pith2026241118137,
  author       = {Pith},
  title        = {Pith review of: The Greedy Coin Change Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/26OXI7OY}},
  note         = {Machine review of arXiv:2411.18137}
}
abstract

The Coin Change problem, also known as the Change-Making problem, is a well-studied combinatorial optimization problem, which involves minimizing the number of coins needed to make a specific change amount using a given set of coin denominations. A natural and intuitive approach to this problem is the greedy algorithm. While the greedy algorithm is not universally optimal for all sets of coin denominations, it yields optimal solutions under most real-world coin systems currently in use, making it an efficient heuristic with broad practical applicability. Researchers have been studying ways to determine whether a given coin system guarantees optimal solutions under the greedy approach, but surprisingly little attention has been given to understanding the general computational behavior of the greedy algorithm applied to the coin change problem. To address this gap, we introduce the Greedy Coin Change problem and formalize its decision version: given a target amount $W$ and a set of denominations $C$, determine whether a specific coin is included in the greedy solution. We prove that this problem is $\mathbf P$-complete under log-space reductions, which implies it is unlikely to be efficiently parallelizable or solvable in limited space.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

  1. [1]

    The complexity of tensor circuit evaluation

    Martin Beaudry and Markus Holzer. The complexity of tensor circuit evaluation. In Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science , MFCS '01, page 173–185, Berlin, Heidelberg, 2001. Springer-Verlag

    work page 2001

  2. [2]

    S. K. Chang and Arthur Gill. Algorithmic solution of the change-making problem. J. ACM , 17(1):113--122, jan 1970

    work page 1970

  3. [3]

    Chan and Qizheng He

    Timothy M. Chan and Qizheng He. On the change-making problem. In Martin Farach - Colton and Inge Li G rtz, editors, 3rd Symposium on Simplicity in Algorithms, SOSA 2020, Salt Lake City, UT, USA, January 6-7, 2020 , pages 38--42. SIAM , 2020

    work page 2020

  4. [4]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition . MIT Press, 2009

    2009

  5. [5]

    Stephen A. Cook. A taxonomy of problems with fast parallel algorithms. Inf. Control. , 64(1-3):2--21, 1985

    work page 1985

  6. [6]

    The complexity of tensor calculus

    Carsten Damm, Markus Holzer, and Pierre McKenzie. The complexity of tensor calculus. Comput. Complex. , 11(1/2):54–89, June 2002

    work page 2002

  7. [7]

    New techniques for proving fine-grained average-case hardness

    Mina Dalirrooyfard, Andrea Lincoln, and Virginia Vassilevska Williams . New techniques for proving fine-grained average-case hardness. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 774--785. IEEE, 2020

    work page 2020

  8. [8]

    The computational complexity of factored graphs, 2024

    Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, and Christopher Ye. The computational complexity of factored graphs, 2024

    work page 2024

Show all 23 references
  1. [9]

    Fast preprocessing for optimal orthogonal range reporting and range successor with applications to text indexing

    Younan Gao, Meng He, and Yakov Nekrich. Fast preprocessing for optimal orthogonal range reporting and range successor with applications to text indexing. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, ...

    2020

  2. [10]

    James Hoover, and Walter L

    Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo. Limits to parallel computation: P-completeness theory . Oxford University Press, Inc., USA, 1995

    1995

  3. [11]

    M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, USA, 1979

    1979

  4. [12]

    Goodrich and Roberto Tamassia

    Michael T. Goodrich and Roberto Tamassia. Algorithm Design and Applications . Wiley Publishing, 1st edition, 2014

    2014

  5. [13]

    On the fine-grained complexity of one-dimensional dynamic programming

    Marvin K \" u nnemann, Ramamohan Paturi, and Stefan Schneider. On the fine-grained complexity of one-dimensional dynamic programming. CoRR , abs/1703.00941, 2017

    2017 arXiv

  6. [14]

    Optimal bounds for the change-making problem

    Dexter Kozen and Shmuel Zaks. Optimal bounds for the change-making problem. Theor. Comput. Sci. , 123(2):377--388, 1994

    1994

  7. [15]

    Processing Succinct Matrices and Vectors

    Markus Lohrey and Manfred Schmidt-Schauß. Processing Succinct Matrices and Vectors . Theory of Computing Systems , 61(2):322--351, August 2017

    2017

  8. [16]

    G.S. Lueker. Two NP-complete Problems in Nonnegative Integer Programming . Princeton University. Department of Electrical Engineering, 1975

    1975

  9. [17]

    A list of p-complete problems, 1989

    Satoru Miyano, Shuji Shiraishi, and Takayoshi Shoudai. A list of p-complete problems, 1989

    1989

  10. [18]

    A polynomial-time algorithm for the change-making problem

    David Pearson. A polynomial-time algorithm for the change-making problem. Oper. Res. Lett. , 33(3):231--234, 2005

    2005

  11. [19]

    Introduction to the theory of computation

    Michael Sipser. Introduction to the theory of computation. SIGACT News , 27(1):27--29, 1996

    1996

  12. [20]

    A measure of parallelization for the lexicographically first maximal subgraph problems

    Ryuhei Uehara. A measure of parallelization for the lexicographically first maximal subgraph problems. In Rolf H. M \" o hring, editor, Graph-Theoretic Concepts in Computer Science, 23rd International Workshop, WG '97, Berlin, Germany, June 18-20, 1997, Proceedings , volume 13...

    1997

  13. [21]

    Another measure for the lexicographically first maximal subgraph problems and its threshold value on a random graph

    Ryuhei Uehara. Another measure for the lexicographically first maximal subgraph problems and its threshold value on a random graph. In 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 23-25 June 1999, Fremantle, Australia , pages 350...

    1999

  14. [22]

    A measure for the lexicographically first maximal independent set problem and its limits

    Ryuhei Uehara. A measure for the lexicographically first maximal independent set problem and its limits. Int. J. Found. Comput. Sci. , 10(4):473--482, 1999

    1999

  15. [23]

    J. W. Wright. The change-making problem. J. ACM , 22(1):125--128, jan 1975

    1975

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.