What was already known
Hamilton paths in unrestricted grid graphs are NP-complete. The prior solid-grid results and Sheffield height-function method address Hamiltonian cycles.
AI involvement
The author reports Claude did nearly all the mathematical work after the author supplied the problem and guidance.
- Hamiltonian s–t paths in solid grid graphs are decided in polynomial time: an algorithm with a Lean 4 proofHamiltonian s–t paths in solid grid graphs are decided in polynomial time: an algorithm with a Lean 4 proof
- SolidGridGraphHamPathSolidGridGraphHamPath
Importance
Extends polynomial solvability from solid-grid cycles to paths with prescribed endpoints.
Technical verification
Lean checks correctness under the repository’s explicit solidity predicate and the stated polynomial step bound. The author reports checking the cost model against the algorithm by inspection and cross-checking the solidity predicate on finite grids. The checked bound counts finite-set primitives and does not certify a Turing-machine runtime.
Formal checking
Lean checks correctness under the repository’s explicit solidity predicate and the stated polynomial step bound. The author reports checking the cost model against the algorithm by inspection and cross-checking the solidity predicate on finite grids. The checked bound counts finite-set primitives and does not certify a Turing-machine runtime.
- Checker
- Author-side Lean and Comparator workflow
- Scope
- Correctness of decideHamPath and the accompanying step bound in the repository’s cost model
- Basis
- Reported by the linked checker
Human understanding
The reviewed sources do not document a human explanation of the assessed contribution.
Correction and publication history
Historical curation based on the cited claim, AI attribution and checking scope.
Read this published revision