Pith. sign in

REVIEW 5 major objections 5 minor 94 references

The sliding tile puzzle, roots to polynomials, and $\textbf{P}$ vs. $\textbf{NP}$ complexity

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

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

Pith's one-line read The paper claims that the number of solvable $n \times n$ sliding-tile boards is at most $4(n^2 - n - 4)$, a polynomial-sized solution space where the standard count gives $(n^2)!/2$.

desk verdict The paper's central counting claim is off by five orders of magnitude for the 3x3 puzzle, the errors are elementary, and it does not deserve referee time. read the letter →

arxiv 2501.10480 v1 pith:NFTKBU75 submitted 2025-01-17 math.GM

Roy Burson This is my paper · ORCID
classification math.GM MSC 68Q1568Q17
keywords slidingtilepuzzle15-puzzlesolvableconfigurationssolutionspacesizePvsNPcomputationalcomplexitypolynomialrootfindingverificationtime
topics P versus NP
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 tries to establish that the solvable configurations of an $n \times n$ sliding-tile puzzle are vastly fewer than the classic count of $(n^2)!/2$. Its central result, Theorem 4, bounds the solvable set by $|S_n| \le 4(n^2 - n - 4)$ for $n \ge 3$, a quadratic polynomial in the board size. If that bound were correct, the solution space would be polynomial rather than factorial, and an exhaustive search over all solvable boards would become a polynomial-time procedure, reframing the puzzle's role in the P versus NP discussion. The paper adds a logarithmic bound on the minimal number of moves (Theorem 2, $\Psi(A) \le \log_4(n^2!)$), an explicit construction of a computable general solution by exhaustion (Lemma 8), and a proof that verification of a candidate solution runs in polynomial time (Theorem 8). A separate thread claims that the roots of any real polynomial are determined by an algebraic system whose coefficient functions arise from expanding the polynomial's factorization, tying root-finding's difficulty to the cost of formulating and solving that system.

What carries the argument

The load-bearing object is the set of four legal transformations $\{\phi_1, \phi_2, \phi_3, \phi_4\}$ acting on $n \times n$ matrices with entries in $\mathbb{N} \cup \{\emptyset\}$, together with the counting identity behind Theorem 4: summing the one-step moves from the corners ($8$), the edges ($12(n-2)$), and the interior ($4(n^2 - 4n)$) gives the quadratic bound $4(n^2 - n - 4)$. A second identity, $4^{\Psi(A)} \le n^2!$, converts the cardinality of the full matrix set into the logarithmic move bound of Theorem 2. The machinery replaces the standard group-permutation treatment of the puzzle with a matrix-counting one, and its role in the argument is to make the solution space small enough that the general solution can be computed by outright exhaustion.

What would settle it

Count the solvable configurations of the $3 \times 3$ board: the standard theory gives $9!/2 = 181{,}440$ solvable states, while Theorem 4's formula caps the set at $4(9 - 3 - 4) = 8$. The board obtained from the goal state by moving the empty tile up and then left is solvable, is two moves from the goal, and is not among the eight one-step boards the theorem counts, so a reader can settle the claim by checking whether that single board exceeds the bound.

Watch

Extended reading notes

Core claim

The paper's central claim is that the solvable sliding-tile configurations form a polynomial-sized set, not a factorial-sized one. Theorem 4 asserts that for $n \ge 3$, $|S_n(\mathbb{N} \cup \{\emptyset\})| \le 4(n^2 - n - 4)$, and the proof obtains this by adding the legal moves available from each position of the empty square: $8$ from the four corners, $12(n-2)$ from the non-corner edge positions, and $4(n^2 - 4n)$ from the interior. The supporting results are Theorem 2, which bounds the minimal solution length by $\Psi(A) \le \log_4(n^2!)$, and Lemma 8, which constructs the general solution map $f$ as an exhaustive search of the bounded solution space and bounds its running time. On the polynomial side, Theorem 7 claims that for every $p \in \mathbb{R}[x] \subseteq \mathbb{C}[x]$ there is a solvable algebraic system, built from coefficient functions $f_i(r)$ obtained by expanding the factored form, whose solution yields exactly the roots of $p$ in $\mathbb{C}$.

Load-bearing premise

The argument depends on the assumption that counting, for each position of the empty square, the boards reachable in one legal move gives an upper bound on the number of solvable boards — in other words, that every solvable configuration appears among these one-step boards, even though a solvable board can sit many moves away from the goal and many solvable boards can share the same empty-square position.

Editorial extensions

If this is right

  • If Theorem 4 is correct, the number of solvable $n \times n$ boards is $O(n^2)$, so a program that enumerates the whole solvable set and tests each board runs in polynomial time.
  • Theorem 2's bound $\Psi(A) \le \log_4(n^2!)$ puts the minimal solution length of any solvable board at logarithmic in $n^2!$, and Corollary 1 gives the explicit quadratic cap $\Psi(A) \le 4(n^2 - n - 2)$.
  • Lemma 8's exhaustive construction shows the general solution map $f$ is computable and bounds its running time by $4k(n^2 + 2) + 27k$, where $k$ is the solution-space bound from Theorem 3.
  • Theorem 8 places the check that a candidate move sequence reaches the goal in polynomial time, with the explicit bound $(\operatorname{length}(\gamma)^2 + 1)^{n^2 + 27k + 1}$, matching the verifier side of the P versus NP framing.
  • For polynomials, Theorem 7 claims every real polynomial's roots are captured by an algebraic system whose coefficient functions come from expanding its factorization, so root-finding reduces to formulating and solving that system.

Reading between the lines

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

  • My inference: the counting behind Theorem 4 can be tested without any complexity theory — applied to the $3 \times 3$ board it yields $8$, while the board reached by two moves from the goal is solvable and outside that count, so the bound stands or falls on whether multi-step solvable boards exist beyond the one-step shells.
  • My inference: if the general solution were computable in the claimed polynomial time, the sliding-puzzle decision problem would sit in P by explicit enumeration, a conclusion the paper gestures toward but does not state as a formal corollary.
  • My inference: the same one-step counting transplanted to a $d$-dimensional board (with $2d$ moves per position) would yield an analogous polynomial bound in the total cell count, so the argument, if correct, would extend naturally to the tensor puzzles the paper names as future work.
  • My inference: on the root-finding side, the construction puts the open difficulty exactly where the paper says — the existence of the coefficient functions $f_i(r)$ is shown inductively, but whether they can be written down and solved in polynomial time remains the unproved step that separates this from a polynomial-time root-finding algorithm.
Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: The paper's central claim is that the solvable sliding-tile configurations form a polynomial-sized set, not a factorial-sized one. Theorem 4 asserts that for $n \ge 3$, $|S_n(\mathbb{N} \cup \{\emptyset\})| \le 4(n^2 - n - 4)$, and the proof obtains this by adding the legal moves available from each position of the empty square: $8$ from the four corners, $12(n-2)$ from the non-corner edge positio

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 5 minor

Summary. The paper claims to establish a connection between the sliding tile puzzle, polynomial root finding, and the P vs. NP problem. Its central assertions are that the set of solvable n-by-n sliding tile configurations has size O(n^2) (Theorem 4), that every solvable puzzle can be solved in O(log n) moves (Theorem 2), and that verifying a sliding tile solution can be done in polynomial time (Theorem 8). The paper also introduces a class of 'nicely factored' polynomials and claims that a general solution to the root-finding problem can be expressed through algebraic systems (Theorems 6 and 7). The manuscript ends by claiming that the solution space of sliding tile puzzles is polynomial in the matrix size, which would contradict known results if true.

Significance. If the paper's central claims were correct, they would overturn a well-established body of results: the number of solvable n-by-n sliding tile configurations is known to be (n^2)!/2 for n ≥ 2, and the generalized sliding tile puzzle is NP-complete. The paper offers no machine-checked proofs, no reproducible code, and no empirically verified predictions. Its only clearly correct part is the worked move sequence in Example 1, which merely illustrates the basic definitions. Because the load-bearing theorems contain elementary counting and algebraic errors, the paper's significance is currently negative: it does not provide a usable foundation for the claimed complexity results.

major comments (5)
  1. [Section 1, Lemma 1 (Eq. (3))] The proof of Lemma 1 is circular: it assumes the existence of a bijection F : T_n → {1, 2, ..., n^2!} and then concludes |T_n| = n^2!, but the existence of such a bijection is exactly the statement being proved. The cardinality claim itself is true (there are (n^2)! distinct arrangements), but the proof as written does not establish it. This is a foundational error because Lemma 1 is used in Theorem 2 and in the bound for the solution space.
  2. [Section 1, Theorem 4 (proof, pp. 6–7)] Theorem 4 asserts |S_n(N ∪ {∅})| ≤ 4(n^2 − n − 4) by summing, over each possible position of the blank, the number of legal moves (2, 3, or 4) available at that position. This counts only configurations that are one move away from some board with the blank in a given position; it does not count configurations reachable by longer move sequences. Distinct solvable configurations can share the same blank position, so the location of the blank does not determine the configuration. For n = 3, the claimed bound gives 8, while the standard parity argument yields 9!/2 = 181,440 solvable configurations. This error invalidates the central claim in Section 4 that the solution space is polynomial in the matrix size.
  3. [Section 1, Theorem 2 (Eq. (18))] The proof of Theorem 2 derives 4^{Ψ(A)} ≤ |M_n(N ∪ {∅})| = n^2! and concludes Ψ(A) ≤ log_4(n^2!). This inequality has the wrong direction: the number of move sequences of length Ψ is 4^Ψ, and many distinct sequences can lead to the same board configuration, so 4^Ψ is an upper bound on the number of reachable boards, not a lower bound. The correct relation is that the number of distinct boards reachable in exactly Ψ moves is at most 4^Ψ, which does not bound Ψ by log_4(n^2!). Thus Theorem 2 is false as stated, and the subsequent bound in Theorem 3 and the computability argument in Lemma 8 inherit this flaw.
  4. [Section 2, Theorem 5 (pp. 10–11) and Definition 13/Lemma 3] Theorem 5 claims that |f|_∞ = max|a_i| is an absolute value on R[x]. This is false because multiplicativity fails: for f(x) = 1 + x, |f·f|_∞ = |1 + 2x + x^2|_∞ = 2, but |f|_∞·|f|_∞ = 1. The proof's assertion that equality holds for terms achieving the maximum is incorrect, since the leading coefficient of the product is not generally the product of the leading coefficients of the factors. This invalidates the reliance on an absolute value in Definition 13. Moreover, Lemma 3 is circular: Definition 13 defines 'nicely factored' polynomials as those satisfying p ∈ V(p(x)), where V selects a divisor with maximal degree and absolute value, and Lemma 3 then 'proves' that such a polynomial factors into linear factors. The conclusion is built into the definition, so the factorization result carries no content.
  5. [Section 3, Theorem 8 (Eq. (70))] Theorem 8 claims that verifying a sliding tile solution can be done in polynomial time, but the bound T_M(γ) ≤ (length(γ)^2 + 1)^{n^2 + 27k + 1} is not a polynomial bound in the standard sense: the exponent depends on the input parameters n and k, so the expression is exponential in n and k. Additionally, the proof uses the existence and running time of the 'general solution' f as an input to the bound, but Lemma 8's computability proof relies on the false bounds from Theorems 3 and 4. The verification problem as normally defined (given a sequence and a board, check whether the sequence reaches the goal) is trivially in P for each fixed sequence; the theorem instead attempts to bound the time to compute a function in COMP_M(f), conflating finding and verifying. The claimed P membership is therefore unsupported.
minor comments (5)
  1. [Section 1, Definition 4] The definition of solvable sliding tiles in Eq. (10) contains a typo: the composition is written as (ϕ_ϵ(i) ∘ ϕ_ϵ(i) ∘ ... ∘ ϕ_ϵ(k)), but the subscripts on ϵ should be distinct indices, likely 1, 2, ..., k. The same notation issue appears in Definition 5 and Theorem 1.
  2. [Section 1, Theorem 3] The proof of Theorem 3 states 'we will ignore the fact that we cannot swap the empty tile down or to the right starting at the goal matrix.' This is an explicit admission that the counting overcounts; the proof should account for boundary constraints instead of ignoring them, and the bound is therefore not justified as written.
  3. [Section 2, Example 4] Example 4 contains several algebraic slips: for instance, in Case II the equation (−2r_2)r_2^2 = π/2 is written as r_2^3 = −π/4 (missing a factor of −2), and later in Case III the transformation of Eq. (39) to Eq. (40) is not valid, as the square root of a squared expression does not preserve the sign. These errors make the example's conclusion unreliable as an illustration of the proposed method.
  4. [References] Reference [90] duplicates reference [40] (both are Goldreich's 'P, NP, and NP-Completeness'), and several entries are incomplete or lack page numbers (e.g., [45], [61], [82]). The reference list would benefit from careful checking.
  5. [Throughout] There are numerous typographical issues: 'ϕ 4(ϕ3(A)) = A' is repeated in Eq. (14) in place of the intended identity for ϕ_3(ϕ_4(A)), 'the the' appears in Section 1.0.4, and equation numbering is inconsistent (e.g., Eq. (34) is used for both the factorization and the coefficient system in Example 4).

Circularity Check

1 steps flagged · score 6.0 of 10

Root-finding 'nicely factored' theorem is a definitional tautology; the sliding-tile bound is an error, not circular.

  1. self definitional [Section 2.0.2, Definition 13 and Lemma 3]
    "The set of Nicely factored polynomials over R is the set N_R[x] = { p ∈ R[x] : p(x) ∈ V(p(x)) }. If an absolute value function |·| does not exist on R then instead we alternatively define N_R[x] as the set of all reducible polynomials that are not divisible by any irreducible polynomial. So that its factorization does not depend on any irreducible. Since, |q(x)| ≥ |k(x)| for any other divisor k(x) | p(x) we must conclude that q(x) = c∏_{i=1}^k (x − r(i))^{m(i)} = p(x)."

    By Definition 11, V(p) selects the maximal-degree reducible divisor of p; for any reducible p, p itself satisfies deg(p) ≥ deg(q) for all q | p, so p ∈ V(p) merely restates that p is reducible. The alternative clause of Definition 13 defines 'nicely factored' directly as 'not divisible by any irreducible polynomial,' i.e., as having a full linear factorization. Lemma 3 then 'proves' exactly that conclusion by invoking the same V-maximality and absolute-value comparison. The proof's final equality q(x) = c∏(x−r_i)^{m_i} = p(x) discards the irreducible factor ι(x) only because the definition already decreed no irreducible factor may remain; the theorem is the definition restated.

full rationale

The only circular step exhibitable from the paper's own equations is in Section 2. Definition 13 defines N_R[x] so that 'nicely factored' already means its factorization does not depend on any irreducible factor, and Lemma 3 then derives the full linear factorization from that definition plus the V(p)-maximality condition that p itself always satisfies. This is a definitional tautology, not a derivation. The circularity propagates into Theorem 6 (which constructs f_i by expanding the linear factors assumed by Lemma 3) and Theorem 7 (which invokes Theorem 6 for arbitrary polynomials). The sliding-tile branch is independent of this circularity: Theorem 4's polynomial bound is not circular, but a counting error (summing per-blank-position degrees counts only one-move neighbors of a single configuration, not all reachable configurations); Theorem 3 is a flawed count of move sequences, not a definitional identity; and Theorem 8 is an ordinary, if misbounded, verifier analysis rather than a self-referential prediction. Because one of the paper's two central derivation chains reduces to its own definition, the score is 6 (partial circularity), while the headline sliding-tile claim itself is not circular.

Assumptions & free parameters 0 free parameters · 6 assumptions · 2 invented entities

The central claims rest on several unproven or false assumptions: an inconsistent state count for the puzzle, a false norm multiplicativity claim, a circularly defined class of polynomials, and the assertion of a computable general solution whose running time is used in the complexity argument. No free parameters are fitted.

assumptions (6)
  • ad hoc to paper The set T_n of n×n sliding-tile matrices has cardinality n²! (Lemma 1).
    The definition restricts all entries to values ≤ n−1 with no repetitions, so an n×n matrix cannot have n² distinct values; the asserted count is inconsistent with the definition and is used to bound the move count in Theorem 2.
  • ad hoc to paper |M_n(N∪{∅})| = n²!.
    Used in Theorem 2 to write 4^Ψ(A) ≤ n²!, inheriting the false count from Lemma 1.
  • ad hoc to paper The maximum-coefficient norm |f|∞ = max|a_i| is an absolute value on R[x] (Theorem 5).
    The max norm is not multiplicative in general (e.g., (x+1)(x+1) has max coefficient 2, not 1); this false axiom underpins the definitions of V and N_R[x].
  • ad hoc to paper Every nicely factored polynomial p satisfies p = c∏(x−r_i)^{m_i} (Lemma 3).
    This conclusion is built into Definition 13 of N_R[x]; the proof assumes the reducible divisor chosen by V is p itself.
  • domain assumption A computable general solution f for sliding puzzles exists (Lemma 8).
    Existence by exhaustive search over the finite state space is plausible, but the proof's time bound is exponential; the later complexity argument treats f as if it were efficiently computable.
  • ad hoc to paper The algebraic system f_i(r)=a_i has a unique solution r ∈ C^k (Theorem 7).
    No proof of existence or uniqueness is given; the map from coefficients to roots is not one-to-one in a simple sense, and solving polynomial systems is not guaranteed to be tractable.
invented entities (2)
  • nicely factored polynomials (N_R[x])
    purpose: To assert that any polynomial in this class has a complete linear factorization and can be represented via Vieta-style functions.
    The class is defined by membership in V(p), which already selects a maximal reducible divisor; the definition is engineered so the factorization theorem is true by construction.
  • general solution f for sliding puzzles
    purpose: To argue that finding a solution takes at most the time of applying f, while verification is faster.
    f is asserted to exist and be computable; no explicit algorithm is given, and the complexity consequences drawn from it are not justified.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The sliding tile puzzle, roots to polynomials, and $\textbf{P}$ vs. $\textbf{NP}$ complexity." pith.science (2026). https://pith.science/paper/NFTKBU75

@misc{pith2026250110480,
  author       = {Pith},
  title        = {Pith review of: The sliding tile puzzle, roots to polynomials, and $\textbfP$ vs. $\textbfNP$ complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NFTKBU75}},
  note         = {Machine review of arXiv:2501.10480}
}
abstract

This work explores the relationship between solution space and time complexity in the context of the $\textbf{P}$ vs. $\textbf{NP}$ problem, particularly through the lens of the sliding tile puzzle and root finding algorithms. We focus on the trade-off between finding a solution and verifying it, highlighting how understanding the structure of the solution space can inform the complexity of these problems. By examining the relationship between the number of possible configurations and the time complexity required to traverse this space we demonstrate that the minimal time to verify a solution is often smaller than the time required to discover it. Our results suggest that the efficiency of solving $\textbf{NP}$-complete problems is not only determined by the ability to find solutions but also by how effectively we can navigate and characterize the solution space. This study contributes to the ongoing discourse on computational complexity, particularly in understanding the interplay between solution space size, algorithm design, and the inherent challenges of finding versus verifying solutions.

Figures

Figures reproduced from arXiv: 2501.10480 by the authors.

Figure 1
Figure 1. An example of the number of moves in a 5x5 sliding tile along every component. □ Corollary 1. Let n ≥ 3 for A ∈ Sn(N ∪ {∅}) Ψ(A) ≤ 4(n 2 − n − 2) [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

94 extracted references · 78 canonical work pages

  1. [1]

    ”Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles.” The Mathematical Intelligencer (2024): 1-14

    Brunck, Florestan, and Matthew Kwan. ”Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles.” The Mathematical Intelligencer (2024): 1-14

    2024

  2. [2]

    ”New progress in real and complex polynomial root-finding.” Computers & Mathematics with Applications 61.5 (2011): 1305-1334

    Pan, Victor Y., and Ai-Long Zheng. ”New progress in real and complex polynomial root-finding.” Computers & Mathematics with Applications 61.5 (2011): 1305-1334

    2011

  3. [3]

    Jenkins, Michael A., and Joseph F. Traub. ”Algorithm 419: zeros of a complex polynomial [c2].” Communica- tions of the ACM 15.2 (1972): 97-99

    1972

  4. [4]

    A., and Joseph Frederick Traub

    Jenkins, M. A., and Joseph Frederick Traub. An algorithm for an automatic general polynomial solver. Computer Science Department, School of Humanities and Sciences, Stanford University, 1967

    1967

  5. [5]

    ”The history and status of the P versus NP question.” Proceedings of the twenty-fourth annual ACM symposium on Theory of computing

    Sipser, Michael. ”The history and status of the P versus NP question.” Proceedings of the twenty-fourth annual ACM symposium on Theory of computing. 1992

    1992

  6. [6]

    ”Introduction to the Theory of Computation.” ACM Sigact News 27.1 (1996): 27-29

    Sipser, Michael. ”Introduction to the Theory of Computation.” ACM Sigact News 27.1 (1996): 27-29

    1996

  7. [7]

    ”Borel sets and circuit complexity.” Proceedings of the fifteenth annual ACM symposium on Theory of computing

    Sipser, Michael. ”Borel sets and circuit complexity.” Proceedings of the fifteenth annual ACM symposium on Theory of computing. 1983

    1983

  8. [8]

    Jefferson, Robert A., and Robert C. Myers. ”Circuit complexity in quantum field theory.” Journal of High Energy Physics 2017.10 (2017): 1-81

    2017

Show all 94 references
  1. [9]

    Ryan Williams

    Murray, Cody D., and R. Ryan Williams. ”On the (non) NP-hardness of computing circuit complexity.” Theory of Computing 13.1 (2017): 1-22

    2017

  2. [10]

    ”Relativized circuit complexity.” Journal of Computer and System Sciences 31.2 (1985): 169-181

    Wilson, Christopher B. ”Relativized circuit complexity.” Journal of Computer and System Sciences 31.2 (1985): 169-181

    1985

  3. [11]

    Introduction to circuit complexity: a uniform approach

    Vollmer, Heribert. Introduction to circuit complexity: a uniform approach. Springer Science & Business Media, 1999

    1999

  4. [12]

    ”Circuit complexity before the dawn of the new millennium.” International Conference on Foun- dations of Software Technology and Theoretical Computer Science

    Allender, Eric. ”Circuit complexity before the dawn of the new millennium.” International Conference on Foun- dations of Software Technology and Theoretical Computer Science. Berlin, Heidelberg: Springer Berlin Heidel- berg, 1996

    1996

  5. [13]

    ”Derandomizing polynomial identity tests means proving circuit lower bounds”

    Kabanets, Valentine; Impagliazzo, Russell Graham (2004). ”Derandomizing polynomial identity tests means proving circuit lower bounds”. Computational Complexity. 13 (1): 1–46. doi:10.1007/s00037-004-0182-6. S2CID 12451799

    2004 doi

  6. [14]

    ”Michael A

    Traub, Joseph P. ”Michael A. Jenkins Queen’s University.” (1974)

    1974

  7. [15]

    Bini, Dario A., Luca Gemignani, and Victor Y. Pan. ”Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations.” Numerische Mathematik 100 (2005): 373-408

    2005

  8. [16]

    ”A quaternion QR algorithm.” Numerische Mathematik 55 (1989): 83-95

    Bunse-Gerstner, Angelika, Ralph Byers, and Volker Mehrmann. ”A quaternion QR algorithm.” Numerische Mathematik 55 (1989): 83-95

    1989

  9. [17]

    ”Horner’s method of approximation anticipated by Ruffini.” (1911): 409-414

    Cajori, Florian. ”Horner’s method of approximation anticipated by Ruffini.” (1911): 409-414

    1911

  10. [18]

    ”The Fifteen Puzzle—A New Approach through Hybridizing Three Heuristics Methods.” Computers 12.1 (2023): 11

    Hasan, Dler O., et al. ”The Fifteen Puzzle—A New Approach through Hybridizing Three Heuristics Methods.” Computers 12.1 (2023): 11

    2023

  11. [19]

    ”Approximately Optimal Search on a Higher-dimensional Sliding Puzzle.” arXiv preprint arXiv:2412.01937 (2024)

    Merleau, Nono SC, et al. ”Approximately Optimal Search on a Higher-dimensional Sliding Puzzle.” arXiv preprint arXiv:2412.01937 (2024)

    2024 arXiv

  12. [20]

    Precise numerical methods using C++

    Aberth, Oliver. Precise numerical methods using C++. Academic Press, 1998

    1998

  13. [21]

    Introduction to precise numerical methods

    Aberth, Oliver. Introduction to precise numerical methods. Elsevier, 2007

    2007

  14. [22]

    M¨ oller, H. E. R. B. E. R. T. ”An efficient reliable algorithm for the approximation of all polynomial roots based on the method of D. Bernoulli.” Proceedings of the Steklov Institute of Mathematics 280.Suppl 2 (2013): S43-S55

    2013

  15. [23]

    ”A new look at the fifteen puzzle.” Mathematics Magazine 40.4 (1967): 171-174

    Spitznagel Jr, Edward L. ”A new look at the fifteen puzzle.” Mathematics Magazine 40.4 (1967): 171-174

    1967

  16. [24]

    ”A modern treatment of the 15 puzzle.” The American Mathematical Monthly 106.9 (1999): 793-799

    Archer, Aaron F. ”A modern treatment of the 15 puzzle.” The American Mathematical Monthly 106.9 (1999): 793-799

    1999

  17. [25]

    ”Sliding Puzzles Gym: A Scalable Benchmark for State Representation in Visual Reinforcement Learning.” arXiv preprint arXiv:2410.14038 (2024)

    de Oliveira, Bryan LM, et al. ”Sliding Puzzles Gym: A Scalable Benchmark for State Representation in Visual Reinforcement Learning.” arXiv preprint arXiv:2410.14038 (2024)

    2024

  18. [26]

    ”Some numerical methods for locating roots of polynomials.” Quarterly of Applied Mathe- matics 3.2 (1945): 89-105

    Fry, Thornton C. ”Some numerical methods for locating roots of polynomials.” Quarterly of Applied Mathe- matics 3.2 (1945): 89-105

    1945

  19. [27]

    ”Unmasking Dunning-Kruger Effect in Visual Reasoning & Judg- ment.” IEEE Transactions on Visualization and Computer Graphics (2024)

    Chen, Mengyu, Yijun Liu, and Emily Wall. ”Unmasking Dunning-Kruger Effect in Visual Reasoning & Judg- ment.” IEEE Transactions on Visualization and Computer Graphics (2024)

    2024

  20. [28]

    Numerical Methods for Roots of Polynomials-Part II

    McNamee, John M., and Victor Pan. Numerical Methods for Roots of Polynomials-Part II. Newnes, 2013

    2013

  21. [29]

    ”Global convergence of the basic QR algorithm on Hessenberg matrices.” Mathematics of Computation 22.104 (1968): 803-817

    Parlett, Beresford. ”Global convergence of the basic QR algorithm on Hessenberg matrices.” Mathematics of Computation 22.104 (1968): 803-817

    1968

  22. [30]

    ”The 15 puzzle: how it drove the world crazy.” The puzzle that started the craze of (1880)

    Slocum, Jerry, and Dic Sonneveld. ”The 15 puzzle: how it drove the world crazy.” The puzzle that started the craze of (1880)

  23. [31]

    ”Depth-first iterative-deepening: An optimal admissible tree search.” Artificial intelligence 27.1 (1985): 97-109

    Korf, Richard E. ”Depth-first iterative-deepening: An optimal admissible tree search.” Artificial intelligence 27.1 (1985): 97-109

    1985

  24. [32]

    ”Computational complexity of puzzles and related topics.” Interdisciplinary Information Sciences 29.2 (2023): 119-140 28 R

    UEHARA, Ryuhei. ”Computational complexity of puzzles and related topics.” Interdisciplinary Information Sciences 29.2 (2023): 119-140 28 R. BURSON

    2023

  25. [33]

    ”Open problems related to quantum query complexity.” ACM Transactions on Quantum Computing 2.4 (2021): 1-9

    Aaronson, Scott. ”Open problems related to quantum query complexity.” ACM Transactions on Quantum Computing 2.4 (2021): 1-9

    2021

  26. [34]

    ”Quantum computational complexity from quantum information to black holes and back.” The European Physical Journal C 82.2 (2022): 128

    Chapman, Shira, and Giuseppe Policastro. ”Quantum computational complexity from quantum information to black holes and back.” The European Physical Journal C 82.2 (2022): 128

    2022

  27. [35]

    ”DSolving: a novel and efficient intelligent algorithm for large-scale sliding puzzles.” Journal of Experimental & Theoretical Artificial Intelligence 29.4 (2017): 809-822

    Wang, GuiPing, and Ren Li. ”DSolving: a novel and efficient intelligent algorithm for large-scale sliding puzzles.” Journal of Experimental & Theoretical Artificial Intelligence 29.4 (2017): 809-822

    2017

  28. [36]

    ”Large-scale parallel breadth-first search.” AAAI

    Korf, Richard E., and Peter Schultze. ”Large-scale parallel breadth-first search.” AAAI. Vol. 5. No. 1. 2005

    2005

  29. [37]

    Ellis, George H., and Layne T. Watson. ”A parallel algorithm for simple roots for polynomials.” Computers & mathematics with applications 10.2 (1984): 107-121

    1984

  30. [38]

    ”On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles.” Proceedings of the AAAI Conference on Artificial Intelligence

    Gozon, Marcus, and Jingjin Yu. ”On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles.” Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 9. 2024

    2024

  31. [39]

    ”Geometric complexity theory.” An approach (2007)

    Mulmuley, Ketan, and Milind Sohoni. ”Geometric complexity theory.” An approach (2007)

    2007

  32. [41]

    Ford, J. A. ”A generalization of the Jenkins-Traub method.” Mathematics of Computation 31.137 (1977): 193- 203

    1977

  33. [42]

    ”P, NP and mathematics–a computational complexity perspective.” Proceedings of the ICM

    Wigderson, Avi. ”P, NP and mathematics–a computational complexity perspective.” Proceedings of the ICM. Vol. 6. 2006

    2006

  34. [43]

    ”A short history of computational complexity.” Bulletin of the EATCS 80.01 (2003): 2003

    Fortnow, Lance, and Steve Homer. ”A short history of computational complexity.” Bulletin of the EATCS 80.01 (2003): 2003

    2003

  35. [44]

    ”The P versus NP problem.” Clay Mathematics Institute 2.6 (2000): 3

    Cook, Stephen. ”The P versus NP problem.” Clay Mathematics Institute 2.6 (2000): 3

    2000

  36. [45]

    ”The importance of the P versus NP question.” Journal of the ACM (JACM) 50.1 (2003): 27-29

    Cook, Stephen. ”The importance of the P versus NP question.” Journal of the ACM (JACM) 50.1 (2003): 27-29

    2003

  37. [46]

    ”The P versus NP Problem, April 2000.” Clay Mathematics Institute at http://www

    Cook, Stephen A. ”The P versus NP Problem, April 2000.” Clay Mathematics Institute at http://www. clay- math. org/sites/default/files/pvsnp. pdf (2020)

    2020

  38. [47]

    ”Scheduled relaxation Jacobi method: improvements and applications.” Journal of Computational Physics 321 (2016): 369-413

    Adsuara, Jos´ e E., et al. ”Scheduled relaxation Jacobi method: improvements and applications.” Journal of Computational Physics 321 (2016): 369-413

    2016

  39. [48]

    ”Parallel multigrid smoothing: polynomial versus Gauss–Seidel.” Journal of Computational Physics 188.2 (2003): 593-610

    Adams, Mark, et al. ”Parallel multigrid smoothing: polynomial versus Gauss–Seidel.” Journal of Computational Physics 188.2 (2003): 593-610

    2003

  40. [49]

    Pulliam, and David W

    Lomax, H., Thomas H. Pulliam, and David W. Zingg. ”Relaxation Methods.” Fundamentals of Computational Fluid Dynamics. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. 153-176

    2001

  41. [50]

    C., and R

    Cassell, A. C., and R. E. Hobbs. ”Numerical stability of dynamic relaxation analysis of non-linear structures.” International Journal for numerical methods in engineering 10.6 (1976): 1407-1410

    1976

  42. [51]

    ”Reheating and thermalization, linear vs

    Boyanovsky, D., et al. ”Reheating and thermalization, linear vs. non-linear relaxation.” arXiv preprint hep- ph/9507414 (1995)

    1995

  43. [52]

    Crow, Mariesa L., and M. D. Ili´ c. ”The waveform relaxation method for systems of differential/algebraic equa- tions.” Mathematical and computer modelling 19.12 (1994): 67-84

    1994

  44. [53]

    ”The general theory of relaxation methods applied to linear systems.” Proceedings of the Royal Society of London

    Temple, G. ”The general theory of relaxation methods applied to linear systems.” Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences 169.939 (1939): 476-500

    1939

  45. [54]

    Rangarajan, S. K. ”Non-linear relaxation methods: I. An operator formalism.” Journal of Electroanalytical Chemistry and Interfacial Electrochemistry 56.1 (1974): 1-25

    1974

  46. [55]

    ”Francis’s algorithm.” The American Mathematical Monthly 118.5 (2011): 387-403

    Watkins, David S. ”Francis’s algorithm.” The American Mathematical Monthly 118.5 (2011): 387-403

    2011

  47. [56]

    ”The Compendious Book on Calculation by Completion and Balancing, al-Khw¯ arizm ¯ ı.” English Translation

    Rosen, Frederic. ”The Compendious Book on Calculation by Completion and Balancing, al-Khw¯ arizm ¯ ı.” English Translation. Retrieved (2009): 09-14

    2009

  48. [57]

    Richard Witmer, and Oystein Ore

    Cardano, Girolamo, T. Richard Witmer, and Oystein Ore. The rules of algebra: Ars Magna. Vol. 685. Courier Corporation, 2007

    2007

  49. [58]

    Galois, ´Evariste, and Peter M. Neumann. The mathematical writings of ´Evariste Galois. Vol. 6. European Mathematical Society, 2011

    2011

  50. [59]

    ”Sur les conditions de r´ esolubilit´ e des ´ equations par radicaux.” Journal de math´ ematiques pures et appliqu´ ees 11 (1846): 417-444

    Galois, E. ”Sur les conditions de r´ esolubilit´ e des ´ equations par radicaux.” Journal de math´ ematiques pures et appliqu´ ees 11 (1846): 417-444

  51. [60]

    General recursion theory

    Fenstad, Jens E. General recursion theory. Vol. 10. Cambridge University Press, 2017

    2017

  52. [61]

    ”Numerical solution of multivariate polynomial systems by homotopy continuation methods.” Acta numerica 6 (1997): 399-436

    Li, Tien-Yien. ”Numerical solution of multivariate polynomial systems by homotopy continuation methods.” Acta numerica 6 (1997): 399-436

    1997

  53. [62]

    C., and James A

    Alexander, J. C., and James A. Yorke. ”The homotopy continuation method: numerically implementable topo- logical procedures.” Transactions of the American Mathematical Society 242 (1978): 271-284

    1978

  54. [63]

    ”Numerical polynomial homotopy continuation method and string vacua.” Advances in High Energy Physics 2011.1 (2011): 263937

    Mehta, Dhagash. ”Numerical polynomial homotopy continuation method and string vacua.” Advances in High Energy Physics 2011.1 (2011): 263937

    2011

  55. [64]

    Introduction to numerical continuation methods

    Allgower, Eugene L., and Kurt Georg. Introduction to numerical continuation methods. Society for Industrial and Applied Mathematics, 2003

    2003

  56. [65]

    ”PHCPACK: A general-purpose solver for polynomial systems by homotopy continuation.” Preprint (1997)

    Verschelde, Jan. ”PHCPACK: A general-purpose solver for polynomial systems by homotopy continuation.” Preprint (1997)

    1997

  57. [66]

    ”On the Ruffini–Abelian theorem.” (1896): 200-221

    Pierpont, James. ”On the Ruffini–Abelian theorem.” (1896): 200-221. THE SLIDING TILE PUZZLE, ROOTS TO POLYNOMIALS, ANDP VS. NP COMPLEXITY 29

  58. [67]

    M´ emoire sur les ´ equations alg´ ebriques, o` u on demontre l’impossibilit´ e de la r´ esolution de l’´ equation g´ en´ erale du cinqui` eme d´ egr´ e

    Abel, Niels Henrik. M´ emoire sur les ´ equations alg´ ebriques, o` u on demontre l’impossibilit´ e de la r´ esolution de l’´ equation g´ en´ erale du cinqui` eme d´ egr´ e. 1824

  59. [68]

    Sidney, et al

    Burrus, C. Sidney, et al. ”Horner’s method for evaluating and deflating polynomials.” DSP Software Notes, Rice University, Nov 26 (2003)

    2003

  60. [69]

    ”Newton’s method in practice: Finding all roots of polynomials of degree one million efficiently.” Theoretical Computer Science 681 (2017): 146-166

    Schleicher, Dierk, and Robin Stoll. ”Newton’s method in practice: Finding all roots of polynomials of degree one million efficiently.” Theoretical Computer Science 681 (2017): 146-166

    2017

  61. [70]

    E., and R

    Funderlic, R. E., and R. J. Plemmons. ”LU decomposition of M-matrices by elimination without pivoting.” Linear Algebra and its Applications 41 (1981): 99-110

    1981

  62. [71]

    ”SYSTEM OF LINEAR ALGEBRAIC EQUATIONS AND METHODS OF THEIR SO- LUTION.” Multidisciplinary Journal of Science and Technology 4.1 (2024): 39-44

    Iqboljon, Xaydarov. ”SYSTEM OF LINEAR ALGEBRAIC EQUATIONS AND METHODS OF THEIR SO- LUTION.” Multidisciplinary Journal of Science and Technology 4.1 (2024): 39-44

    2024

  63. [72]

    ”Solution of a System of Neutrosophic Linear Algebraic Equation by LU Decomposition Method.”

    Das, Indrani. ”Solution of a System of Neutrosophic Linear Algebraic Equation by LU Decomposition Method.”

  64. [73]

    Adomian, G., and R. Rach. ”On the solution of algebraic equations by the decomposition method.” Journal of mathematical analysis and applications 105.1 (1985): 141-166

    1985

  65. [74]

    ”Implicit schemes and LU decompositions.” Mathematics of Computation 37.156 (1981): 385-397

    Jameson, Antony, and Eli Turkel. ”Implicit schemes and LU decompositions.” Mathematics of Computation 37.156 (1981): 385-397

    1981

  66. [75]

    ”Distributed localization using Levenberg-Marquardt algorithm.” Eurasip journal on advances in signal processing 2021 (2021): 1-26

    Ahmadi, Shervin Parvini, Anders Hansson, and Sina Khoshfetrat Pakazad. ”Distributed localization using Levenberg-Marquardt algorithm.” Eurasip journal on advances in signal processing 2021 (2021): 1-26

    2021

  67. [76]

    ”Improved computation for Levenberg–Marquardt training.” IEEE transactions on neural networks 21.6 (2010): 930-937

    Wilamowski, Bogdan M., and Hao Yu. ”Improved computation for Levenberg–Marquardt training.” IEEE transactions on neural networks 21.6 (2010): 930-937

    2010

  68. [78]

    ”The levenberg-marquardt algorithm.” Tutoral on LM algorithm 11.1 (2004): 101-110

    Ranganathan, Ananth. ”The levenberg-marquardt algorithm.” Tutoral on LM algorithm 11.1 (2004): 101-110

    2004

  69. [79]

    ”A modified Newton method for solving non-linear algebraic equations.” Journal of Marine Science and Technology 17.3 (2009): 9

    Atluri, Satya N., Chein-Shan Liu, and Chung-Lun Kuo. ”A modified Newton method for solving non-linear algebraic equations.” Journal of Marine Science and Technology 17.3 (2009): 9

    2009

  70. [80]

    ”Numerical experience with Newton-like methods for nonlinear algebraic systems.” Computing 58.1 (1997): 69-89

    Spedicato, Emilio, and Zhijian Huang. ”Numerical experience with Newton-like methods for nonlinear algebraic systems.” Computing 58.1 (1997): 69-89

    1997

  71. [81]

    ”Practical quasi-Newton methods for solving nonlinear systems.” Journal of computa- tional and Applied Mathematics 124.1-2 (2000): 97-121

    Martınez, Jos´ e Mario. ”Practical quasi-Newton methods for solving nonlinear systems.” Journal of computa- tional and Applied Mathematics 124.1-2 (2000): 97-121

    2000

  72. [82]

    ”Thermodynamic Perspectives on Computational Complexity: Exploring the P vs

    Neukart, Florian. ”Thermodynamic Perspectives on Computational Complexity: Exploring the P vs. NP Prob- lem.” arXiv preprint arXiv:2401.08668 (2023)

    2023 arXiv

  73. [83]

    ”Thermodynamic Perspectives on Computational Complexity.” Thermodynamic Perspectives on Computational Complexity

    Neukart, Florian. ”Thermodynamic Perspectives on Computational Complexity.” Thermodynamic Perspectives on Computational Complexity

  74. [84]

    ”On computable numbers, with an application to the Entscheidungsproblem.” J

    Turing, Alan Mathison. ”On computable numbers, with an application to the Entscheidungsproblem.” J. of Math 58.345-363 (1936): 5

    1936

  75. [85]

    ”P vs NP.” (2014)

    Vega, Frank. ”P vs NP.” (2014)

    2014

  76. [86]

    ”On the P versus NP Problem.” (2024)

    Vega, Frank. ”On the P versus NP Problem.” (2024)

    2024

  77. [87]

    ”NP on Logarithmic Space.” (2023)

    Vega, Frank. ”NP on Logarithmic Space.” (2023)

    2023

  78. [88]

    ”Hard problems of algebraic geometry codes.” IEEE Transactions on Information Theory 54.1 (2008): 402-406

    Cheng, Qi. ”Hard problems of algebraic geometry codes.” IEEE Transactions on Information Theory 54.1 (2008): 402-406

    2008

  79. [89]

    ”Parallel computation for well-endowed rings and space-bounded probabilistic machines.” Information and control 58.1-3 (1983): 113-136

    Borodin, Allan, Stephen Cook, and Nicholas Pippenger. ”Parallel computation for well-endowed rings and space-bounded probabilistic machines.” Information and control 58.1-3 (1983): 113-136

    1983

  80. [90]

    P, NP, and NP-Completeness: The basics of computational complexity

    Goldreich, Oded. P, NP, and NP-Completeness: The basics of computational complexity. Cambridge University Press, 2010

    2010

  81. [91]

    ”Evaluation of polynomials by computer.” Communications of the ACM 5.12 (1962): 595-599

    Knuth, Donald E. ”Evaluation of polynomials by computer.” Communications of the ACM 5.12 (1962): 595-599

    1962

  82. [92]

    ”Another new proof of the theorem that every integral rational algebraic function of one variable can be resolved into real factors of the first or second degree.” (1983)

    Gauss, Carl Friedrich. ”Another new proof of the theorem that every integral rational algebraic function of one variable can be resolved into real factors of the first or second degree.” (1983)

    1983

  83. [93]

    ”Gaussian elimination.” Wiley Interdisciplinary Reviews: Computational Statistics 3.3 (2011): 230-238

    Higham, Nicholas J. ”Gaussian elimination.” Wiley Interdisciplinary Reviews: Computational Statistics 3.3 (2011): 230-238

    2011

  84. [94]

    ”Scaling for numerical stability in Gaussian elimination.” Journal of the ACM (JACM) 26.3 (1979): 494-526

    Skeel, Robert D. ”Scaling for numerical stability in Gaussian elimination.” Journal of the ACM (JACM) 26.3 (1979): 494-526

    1979

  85. [95]

    ”On some pivotal strategies in Gaussian elimination by sparse technique.” SIAM Journal on Numerical Analysis 17.1 (1980): 18-30

    Zlatev, Zahari. ”On some pivotal strategies in Gaussian elimination by sparse technique.” SIAM Journal on Numerical Analysis 17.1 (1980): 18-30

    1980

  86. [96]

    ”Gaussian elimination: when is scaling beneficial?.” Linear algebra and its applications 162 (1992): 309-324

    Poole, George, and Larry Neal. ”Gaussian elimination: when is scaling beneficial?.” Linear algebra and its applications 162 (1992): 309-324

    1992

Pith tools

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