Pith. sign in

REVIEW 4 major objections 6 minor 25 references

Sorting by pile shuffles on queue-like and stack-like piles can be hard

T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Deciding whether pile shuffles can sort a deck is NP-hard when the dealer chooses pile types freely each round.

desk verdict Real ideas, plausible result, but the load-bearing Lemma 11.1 is an unreviewable computer-assisted assertion that must be supplied before the main theorem can be taken as established. read the letter →

arxiv 2506.05518 v1 pith:SJNOTKRU submitted 2025-06-05 cs.CC

Kyle B. Treleaven This is my paper
classification cs.CC MSC 68Q1768Q4505A05
keywords pileshufflesortablepermutationsNP-hardnessdeterministicfiniteautomatachangeprofilequeueandstackpilesdealer'schoicecomputationalcomplexity
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

Sorting a deck by repeatedly dealing it into piles on a table is easy to understand but can become computationally hard when a dealer may, in each round, decide how many piles to make and whether each pile behaves like a queue (face-up) or a stack (face-down). This paper proves that the variable-round version of this decision problem, where per-round pile capacities are given, is NP-hard by a polynomial-time reduction from Boolean satisfiability (SAT). The consequence is that, unless P equals NP, no fast algorithm can decide feasibility for arbitrary schedules of pile capacities and pile types. The companion repeated-round problem, in which the same pile capacity is used every round, remains open and is conjectured hard.

What carries the argument

The load-bearing machinery is a correspondence between type schedules and chain-like deterministic finite automata. Given a pile type assignment chi, a word over q for queues and s for stacks, the automaton Pi(chi) has one state per pile plus a terminal state; a queue state self-loops on ascents and moves forward on descents, while a stack state does the reverse. A permutation's ascent/descent word, its change profile, is accepted exactly when the shuffle can sort it, and multi-round schedules are collapsed to single-round virtual type schedules by a backslash composition operator, so the same automaton test applies across rounds. The reductions then build change-profile gadgets whose accepted trajectories encode satisfying assignments of a CNF formula.

What would settle it

Search the class of chain automata $P^{6}$\$P^{{n+2}}$ for an instance where the word align, starting from a start beat, fails to advance at least one extra beat per two measures, or where an unaligned class violates the penalty bound of Lemma 11.2. Finding one would invalidate Lemma 11.2 and the Q_III reduction, and with it the proof of Theorem 1.1; the author's omitted computer-assisted check could be rerun to settle this.

Watch

Extended reading notes

Core claim

The paper's central result is Theorem 1.1: the variable-round Dealer's choice pile shuffle sort problem (Problem 1.2) is NP-hard. The proof reduces SAT through three sort-feasibility variants: first with a fixed first round and a queue-only last round, then with the last-round restriction removed, and then with no type restrictions except three rounds and six piles in the first round. Each reduction encodes a CNF formula as a word over ascent and descent symbols, the change profile of a permutation, and asks whether some legal type schedule yields a chain-like automaton that accepts that word. Because the final variant is a strict subset of Problem 1.2, NP-hardness transfers. The author leaves the uniform-capacity repeated-round problem open and conjectures it is also NP-hard.

Load-bearing premise

The load-bearing premise is the omitted computer-assisted trajectory classification in Lemma 11.1, which asserts that the word align behaves as claimed on thousands of unaligned chain automaton classes; if that classification contains an error, the penalty argument that removes the fixed first-round restriction fails, and the proof of Theorem 1.1 collapses.

Editorial extensions

If this is right

  • Problem 1.2 is NP-hard, so no polynomial-time algorithm decides variable-round dealer-choice sortability unless P equals NP.
  • Because a type schedule is a polynomial-time-checkable certificate, the paper's observations place Problem 1.2 in NP as well, making it NP-complete.
  • The intermediate problems Q_I, Q_II, and Q_III are each NP-hard, with Q_III being the three-round unrestricted-type core from which the main theorem follows.
  • The homogeneous all-queue and all-stack cases, and the single-round dealer-choice case, remain tractable; the hardness enters with multiple rounds of free type choice.
  • The repeated-round uniform-capacity problem remains open, and the author conjectures it is also NP-hard, sketching a partial route through the nearly repeated problem Q_V.

Reading between the lines

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

  • Editorial inference: Should the open repeated-round conjecture hold, the same hardness would apply to the physically natural scenario in which table size, and hence pile capacity, is fixed across rounds.
  • Editorial inference: The chain-automaton reformulation suggests a parameterized view: fixing the number of rounds or the pile capacity makes the certificate search polynomial, though exponential in that fixed parameter, which may invite fixed-parameter tractability or lower-bound follow-ups.
  • Editorial inference: An independent re-run of the omitted computer-assisted trajectory classification in Lemma 11.1, with the trajectory classes published, would be the natural first validation step for readers.
  • Editorial inference: The strategy of penalizing unaligned chains with long gadget words might generalize to other restricted scheduling families, potentially yielding a uniform hardness proof for repeated rounds rather than a bespoke alignment argument.
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

4 major / 6 minor

Summary. This paper considers two decision problems for sorting a deck by repeated pile shuffles in which each round the dealer chooses whether each pile is queue-like or stack-like. The author introduces a chain-automaton reformulation in which a type schedule X is a DFA Pi(X) over the change-profile alphabet {a,d}, and sort feasibility is reduced to acceptance. The central contribution is a sequence of polynomial-time reductions from SAT to three-round sort problems with increasingly relaxed pile-type restrictions; the final reduction to Q_III, a subset of the variable-round problem, is used to conclude Theorem 1.1 that Prob. 1.2 is NP-hard. The paper also proposes but does not resolve an approach to the repeated-round problem. Most gadget lemmas are supported by exhaustive trajectory diagrams, but the final reduction depends on Lemma 11.1, whose proof is replaced by an undocumented computer-assisted claim, and on the incomplete proofs of Lemmas 11.3 and 11.4.

Significance. If completed, the paper would establish NP-hardness for a natural dealer-choice pile-shuffle sorting problem, and the chain-automaton framework would give a reusable certificate language for this family of problems. The reduction chain is explicit, the gadget encodings are concrete, and the hardness result does not rely on fitted parameters or numerical search; the paper honestly separates the established result from the open repeated-round conjecture. The current version, however, cannot be accepted as a proof of the main theorem because the pivotal Lemma 11.1 is asserted rather than demonstrated, and the final reduction contains reader-delegated verifications at exactly the points where the correctness of the reduction is determined.

major comments (4)
  1. [Section 11, Lemma 11.1] Lemma 11.1 is the foundation of the Q_III reduction: it classifies trajectories of the 162-symbol word align over all chains in P^6\P^{n+2}, and its 'penalty' assertions are what allow Lemma 11.2 to rule out both unaligned chains and faulty guards. The proof is omitted with only the statement 'We omit the proof, which the author verified with computer assistance' and no code, data, enumeration protocol, or certificate. Since Theorem 1.1 depends on this lemma through Lemmas 11.3 and 11.4, the proof of the main theorem is not verifiable in the submitted manuscript. The author should supply the verification artifact or a complete written proof, including the exact enumeration of chain classes.
  2. [Section 11, Lemma 11.3] In the final case of Lemma 11.3 the proof says 'otherwise, we let the reader verify that the trajectory reaches a disqualifying state instead.' This is precisely the rejection case for aligned chains whose guard is not (qs)^{n''} or whose assignment prefix is not Psi(x_j)q; it is needed for the 'only if' direction of Lemma 11.4 and hence for Corollary 11.4.1. The delegated verification should be written out or supplied as a machine-checkable case analysis.
  3. [Section 11, Lemma 11.4] Lemma 11.4 is the exact equivalence that turns a satisfying assignment into an accepting chain and a nonsatisfying formula into a rejecting chain; its proof is only a sketch ('proved with the same technique as the proof of Lemma 10.4, but using Lemma 11.3'). Because Lemma 11.4 is the bridge to Q_III and Theorem 1.1, the proof must be expanded to a full argument, including the treatment of the suffix P^m and the use of Lemma 10.3.
  4. [Section 11, Corollary 11.4.1] The proof of Corollary 11.4.1 is omitted as 'stereotypical.' Although the argument is likely routine, the corollary is the final step from Lemma 11.4 to NP-hardness of Q_III; it should be written out sufficiently to confirm that the constructed instance lies in Q'_III and that the yes/no answer is preserved.
minor comments (6)
  1. [Section 2.1] In the example defining string notation, W(2)=w1 should be W(2)=w2.
  2. [Section 5] Lemmas 5.1 and 5.2 and the associativity of the backslash operator are stated without proof ('purely technical'); since this algebra is used throughout, a short proof or a precise pointer to [3] should be included.
  3. [References] Reference [3] is an unpublished 2025 preprint with no repository identifier; given that Lemma 4.3 and the virtual-shuffle framework are imported from it, the citation should include a stable identifier or a self-contained appendix.
  4. [Sections 10 and 12] Lemma 10.2 and Lemma 12.2 are stated as proved results but their proofs are left as exercises; for a journal version these should be proved or explicitly marked as conjectural.
  5. [Figures in Sections 8-12] The trajectory diagrams are informative but some, e.g., Figures 8.5-8.7, are hard to verify in print; consider making the underlying case-enumeration tables or scripts available as supplementary material.
  6. [Section 7.3] The coordinate notation k1\k2\k3 is introduced informally; a one-line formula connecting it to the flat state index would improve precision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: SAT-to-pile-shuffle reductions are constructed from explicit gadgets; the omitted computer-assisted proof is a verification gap, not a circular step.

full rationale

Score 0. The derivation chain is self-contained with respect to the NP-hardness claim: each reduction (Lemmas 9.4, 10.4, 11.4) maps SAT instances to change-profile/certificate-chain instances using explicitly defined gadgets (clause, force-q, align), and the acceptance criteria are proved by trajectory lemmas rather than by assuming the target problem. The virtual-shuffle Lemma 4.3 is cited to the author's prequel [3] but is reproduced and applied with explicit recurrence equations (B.2)-(B.3), and it is a parameter-free equivalence about pile shuffles, not an assumption of NP-hardness; hence it is independent support under the stated rules. The notable weakness is Lemma 11.1, where the paper says 'We omit the proof, which the author verified with computer assistance,' and Lemma 11.3 contains a 'let the reader verify' case: these are omitted-verification risks that could undermine the QIII reduction if the trajectory bounds are wrong, but an unproved computer-assisted lemma is a correctness gap, not a circular reduction of the theorem to its inputs.

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

The proof rests on the author's own virtual-shuffle machinery and on several unproved or computer-checked trajectory lemmas; no fitted parameters or invented entities appear.

free parameters (3)
  • Key first-round type sequence (chi-double-dot = qqqqss) = qqqqss
    Hand-selected six-letter type schedule that anchors the QI and QII reductions; the clause gadgets' trajectories are designed around its beat pattern.
  • Clause gadget words (start-clause, pos, neg, dk, endpos, endneg, enddk) = Explicit strings in Definition 8.1
    Hand-crafted so that the trajectory claims of Lemmas 8.2 through 8.4 hold; correctness of the reduction depends on these exact choices.
  • Gadgets force-q, align, pass = Explicit strings in Sections 10, 11, 12
    Hand-crafted to relax third-round and first-round restrictions; the align gadget is the load-bearing, computer-checked component of Lemma 11.1.
assumptions (5)
  • standard math SAT is NP-complete and polynomial-time many-one reducibility is transitive.
    Used as the source problem and to chain the reductions; standard textbook background from Appendix A.
  • domain assumption The virtual shuffle equivalence of Lemma 4.3 correctly models multi-round pile shuffle as a single-round shuffle on virtual piles.
    Carried from the author's prequel [3] and reproduced in Appendix B; all chain-automaton reasoning depends on it.
  • standard math Every ascent/descent profile over {a,d} of length n-1 is realized by some permutation of [n].
    Used in Section 6.1 to move from CHAIN problems back to SORT problems; the paper does not prove or cite this explicitly.
  • ad hoc to paper Lemma 11.1: the align gadget has the claimed trajectory behavior over all chain classes, accepted on the author's undocumented computer-assisted verification.
    The proof is omitted; no code, enumeration protocol, or reproducible detail is provided, yet Theorem 1.1 depends on it through Lemma 11.4.
  • ad hoc to paper Lemmas 10.2 and 12.2 and several corollaries are valid as stated, with proofs left to the reader.
    The paper states 'We leave the proof as an exercise' and 'straightforward but rather tedious', so these results are assumed without demonstration.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sorting by pile shuffles on queue-like and stack-like piles can be hard." pith.science (2026). https://pith.science/paper/SJNOTKRU

@misc{pith2026250605518,
  author       = {Pith},
  title        = {Pith review of: Sorting by pile shuffles on queue-like and stack-like piles can be hard},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SJNOTKRU}},
  note         = {Machine review of arXiv:2506.05518}
}
read the original abstract

Inspired by a common technique for shuffling a deck of cards on a table without riffling, we continue the study of a prequel paper on the pile shuffle and its capabilities as a sorting device. We study two sort feasibility problems of general interest concerning pile shuffle, first introduced in the prequel. These problems are characterized by: (1) bounds on the number of sequential rounds of shuffle, and piles created in each round; (2) the use of a heterogeneous mixture of queue-like and stack-like piles, as when each round of shuffle may have a combination of face-up and face-down piles; and (3) the ability of the dealer to choose the types of piles used during each round of shuffle. We prove by a sequence of reductions from the Boolean satisfiability problem (SAT) that the more general problem is NP-Hard. We leave as an open question the complexity of its arguably more natural companion, but discuss avenues for further investigation. Our analysis leverages a novel framework, introduced herein, which equates instances of shuffle to members of a particular class of deterministic finite automata.

Figures

Figures reproduced from arXiv: 2506.05518 by the authors.

Figure 6.1
Figure 6.1. The deterministic automata (chain), Π(qqsq). Queue states (piles) consume arbitrarily long ascending “runs” of a permutation, but no descents, while stack states consume descending runs but no ascents: Accordingly, in [PITH_FULL_IMAGE:figures/full_fig_p019_6_1.png] view at source ↗
Figure 7.1
Figure 7.1. Grouping of the chain qqs\qs\qq into two phrases, each of two measures, each of three beats. A beat with coordinates 0\1\1 is shaded. This hierarchical grouping of states allows us to describe positions on a chain using a coordinate notation: We will write k1\k2\k3 to denote the k1-th beat of the k2-th measure of the k3-th phrase, a short-hand for the position k1 + ∥X1∥ (k2 + ∥X2∥ k3). For example, the shaded state … view at source ↗
Figure 8.1
Figure 8.1. Types of trajectories of clause(ϕj ) on ¨χ\A0A1A2. According to Lemma 8.1 (first claim) if the segment ¨χ\A1 encodes a satisfying assign￾ment of ϕj , then a trajectory of clause(ϕj ) starting from start\k1 will end at end\(k1 + n). Otherwise (second claim) it will end no earlier than chain-disq\(k1 + n + 1). An impor￾tant observation then is that as a standalone chain, i.e., with k1 = k2 = 0, ¨χ\A1 accepts clause(ϕj… view at source ↗
Figures from the paper (13 more)
Figure 8.2
Figure 8.2. Figure 8.2: Structure of a conjunctive gate gadget (“AND”) [PITH_FULL_IMAGE:figures/full_fig_p028_8_2.png]
Figure 8.3
Figure 8.3. Figure 8.3: The chain ¨χ. Node color indicates beat significance from [PITH_FULL_IMAGE:figures/full_fig_p029_8_3.png]
Figure 8.4
Figure 8.4. Figure 8.4: Types of trajectories of start-clause on ¨χ\P∗ . Proof. We use the opportunity of proving Lemma 8.2 to introduce a visual aid used for other more complex gadgets in the sequel [PITH_FULL_IMAGE:figures/full_fig_p030_8_4.png]
Figure 8.5
Figure 8.5. Figure 8.5: Trajectories of start-clause from two starting positions on the k-th measure of the chain automata in ¨χ\P∗ . The word dk (“don’t care”) simply passes forward the latest activation status of the clause, regardless of the variable assignment. Lemma 8.3 (Trajectories o…
Figure 8.6
Figure 8.6. Figure 8.6: Trajectories of pos and neg from three starting positions on measure k of the chain automata in ¨χ\P∗ . 32 [PITH_FULL_IMAGE:figures/full_fig_p032_8_6.png]
Figure 8.7
Figure 8.7. Figure 8.7: Trajectories of dk from three starting positions on measure k of the chain automata in ¨χ\P∗ . actd\k actd\k ≥ clause-disq\k actd\(k + 1) actd\(k + 1) ≥ clause-disq\(k + 1) pos, neg, dk pos, neg, dk pos if xk = q, neg if xk = s dk, pos if xk ̸= q, neg if xk ̸= s [PI…
Figure 8.8
Figure 8.8. Figure 8.8: Types of trajectories of test on ¨χ\P∗ . Comparing them demonstrates the role of instances of test within an instance of clause, of populating the disjunctive clause at the end of a conjunctive formula. AB AB A A(B + C) AB + C A C C [PITH_FULL_IMAGE:figures/full_fig…
Figure 8.9
Figure 8.9. Figure 8.9: Structure of a conditioned disjunction gate (“OR”). [PITH_FULL_IMAGE:figures/full_fig_p033_8_9.png]
Figure 8.10
Figure 8.10. Figure 8.10: Types of trajectories of end-test(ϕj ) on ¨χ\P∗ . At last we have the tools needed for the proof of Lemma 8.1. 34 [PITH_FULL_IMAGE:figures/full_fig_p034_8_10.png]
Figure 9.1
Figure 9.1. Figure 9.1: Trajectories of next on chain automata of the form ¨χ\x0 . . . xn (only xk = q) starting from end\k. The figure demonstrates the function of the word next, which is to move from the end of one measure to the start of the next one. It provides us a key adaptation of L…
Figure 8
Figure 8. Figure 8: , only with [PITH_FULL_IMAGE:figures/full_fig_p037_8.png]
Figure 10.1
Figure 10.1. Figure 10.1: Trajectories of force-q from two starting positions on measure k of the chain automata in ¨χ\P∗ . 39 [PITH_FULL_IMAGE:figures/full_fig_p039_10_1.png]
Figure 12.1
Figure 12.1. Figure 12.1: Trajectories of pass from three starting positions on measure k of the chain automata in ¨χ\P∗ . • We replace each testi(ϕj ) with dkk−1 testi(ϕj ); • and each end-testi(ϕj ) with dkk−1 end-testi(ϕj ) passk−1 . • We replace each instance of force-q with force-q pass…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    ifA 1 = Ψ(x)qfor somex∈SAT(ϕ j), thenclause(ϕ j)∈start\k 1 →end\(k 1 +n)

    work page

  2. [2]

    chain disqualified

    otherwise,clause(ϕ j)∈start\k 1 → ≥chain-disq\(k1 +n+ 1); 3.clause(ϕ j)∈chain-disq\k 1 → ≥chain-disq\(k1 +n+ 1), unconditionally. We will prove the lemma at the end of the section after developing additional machinery. Lemma 8.1 is concerned with segments ofn+ 1 measures in length ( ¨χ\A 1) within ¨χ- aligned chains, and with two starting positions and tw...

    work page

  3. [3]

    virtual piles

    showed that a minimal sort can be obtained, if one exists, in time that is linear in the permutation length, by combining (4.2) with a greedy strategy for choosing a minimizing types assignmentχ ∗. 4.1.2 Demonstration In this section we offer a demonstration of sorting with pile shuffle as guided by Lemma 4.2. We start by writing an example permutation in...

    work page

  4. [4]

    if for eachj∈[m],A j = Ψ(x j)qfor somex j ∈SAT(ϕ j), thenf ormula I(ϕ)∈ start\0→end\(m(n+ 1)−1)

    work page

  5. [5]

    Proof.We start with the first case

    otherwise,f ormula I(ϕ)∈start\0→ ≥chain-disq\m(n+ 1). Proof.We start with the first case. Due to Lemma 9.2, for eachj∈[m−1], the segment clause(ϕj)nextmoves from state ˜kj−1 =start\(j−1)(n+ 1) to state ˜kj =start\j(n+ 1). Then, due to Lemma 8.1,clause(ϕ m) moves from state ˜km−1 =start\(m−1)(n+ 1) to state ˜km =end\(m(n+ 1)−1). In the second case, there i...

    work page

  6. [6]

    if for eachj∈[m],A j =qΨ(x j)qfor somex j ∈SAT(ϕ j), thenf ormula II(ϕ)∈ start\0→end\(m(n+ 2)−1)

    work page

  7. [7]

    penalize

    otherwise,f ormula II(ϕ)∈start\0→ ≥chain-disq\m(n+ 2). We leave the proof of the lemma as an exercise for the reader. The logic is essentially the same as for Lemma 9.3, but with the placements off orce-qensuring thatA j =qΨ(x j)q rather thanA j = Ψ(xj)qpreviously. (We will soon exploit the symmetry of having aqon each side of an assignment embedding.) Fo...

    work page

  8. [8]

    Analysis of casino shelf shuffling machines.The Annals of Applied Probability, 23(4):1692 – 1720, 2013

    Persi Diaconis, Jason Fulman, and Susan Holmes. Analysis of casino shelf shuffling machines.The Annals of Applied Probability, 23(4):1692 – 1720, 2013

    work page 2013

Show all 25 references
  1. [9]

    Kyle Petersen

    Jason Fulman and T. Kyle Petersen. Card shuffling and p-partitions.Discrete Mathe- matics, 344(8):112448, 2021

    2021

  2. [10]

    Treleaven

    Kyle B. Treleaven. Sorting permutations with pile shuffle on queue-like and stack-like piles, 2025

    2025

  3. [11]

    Knuth.The art of computer programming, volume 3: (2nd ed.) sorting and searching

    Donald E. Knuth.The art of computer programming, volume 3: (2nd ed.) sorting and searching. Addison Wesley Longman Publishing Co., Inc., USA, 1998

    1998

  4. [12]

    Patience is a virtue: Revisiting merge and sort on modern processors

    Badrish Chandramouli and Jonathan Goldstein. Patience is a virtue: Revisiting merge and sort on modern processors. InProceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 731–742, 2014

    2014

  5. [13]

    Combinatorics of patience sorting piles

    Alexander Burstein and Isaiah Lankham. Combinatorics of patience sorting piles. S´ eminaire Lotharingien de Combinatoire, 54:B54Ab, 2006

    2006

  6. [14]

    A survey of stack-sorting disciplines.The Electronic Journal of Combi- natorics, pages A1–A1, 2002

    Mikl´ os B´ ona. A survey of stack-sorting disciplines.The Electronic Journal of Combi- natorics, pages A1–A1, 2002

    2002

  7. [15]

    Sorting using networks of queues and stacks.Journal of the ACM (JACM), 19(2):341–346, April 1972

    Robert Tarjan. Sorting using networks of queues and stacks.Journal of the ACM (JACM), 19(2):341–346, April 1972

    1972

  8. [16]

    The complexity of sorting with networks of stacks and queues

    Stefan Felsner and Martin Pergel. The complexity of sorting with networks of stacks and queues. InAlgorithms-ESA 2008: 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings 16, pages 417–429. Springer, 2008. 49

    2008

  9. [17]

    Sorting Permutations Via Shuffles.SSRN Electronic Journal, 2023

    Lara Pudwell and Rebecca Smith. Sorting Permutations Via Shuffles.SSRN Electronic Journal, 2023

    2023

  10. [18]

    Sorting by shuffling methods and a queue, July 2022

    Stoyan Dimitrov. Sorting by shuffling methods and a queue, July 2022. arXiv:2103.04332 [math]

    2022 arXiv

  11. [19]

    Gates and Christos H

    William H. Gates and Christos H. Papadimitriou. Bounds for sorting by prefix reversal. Discrete Mathematics, 27(1):47–57, 1979

    1979

  12. [20]

    Gargano, U

    L. Gargano, U. Vaccaro, and A. Vozella. Fault tolerant routing in the star and pancake interconnection networks.Information Processing Letters, 45(6):315–320, 1993

    1993

  13. [21]

    Disjoint paths routing in pancake graphs

    Keiichi Kaneko and Shietung Peng. Disjoint paths routing in pancake graphs. In2006 Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT’06), pages 254–259, 2006

    2006

  14. [22]

    Pancake flipping is hard.Journal of Computer and System Sciences, 81(8):1556–1574, 2015

    Laurent Bulteau, Guillaume Fertin, and Irena Rusu. Pancake flipping is hard.Journal of Computer and System Sciences, 81(8):1556–1574, 2015

    2015

  15. [23]

    Chapman and Hall/CRC, Boca Raton, Fla., 1st edition edition, June 2004

    Miklos Bona.Combinatorics of Permutations. Chapman and Hall/CRC, Boca Raton, Fla., 1st edition edition, June 2004

    2004

  16. [24]

    Stirling-euler-mahonian triples of permutation statistics.arXiv e- prints, pages arXiv–2305, 2023

    Frederick Butler. Stirling-euler-mahonian triples of permutation statistics.arXiv e- prints, pages arXiv–2305, 2023

    2023

  17. [25]

    easiest” classes of problems that is considered “hard

    Michael Sipser.Introduction to the Theory of Computation. Course Technology, Boston, MA, 3rd edition, 2012. 50 A Background: Decision Problems and NP In computational complexity theory, adecision problemis a set of questions with yes or no answers; for our purposes, a setQof p...

    2012

Pith tools

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