/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilPolynomial-time computability of comparisons of sums of square roots
This file formalizes the "Square-root sum problem" which asks if one can decide in polynomial time on a Turing machine whether the sum of the square roots of a list of naturals is at most a cutoff (or alternatively, at most another such sum).
This problem is relevant to questions in computational geometry (for example, in determining which of two polygonal paths in Euclidean space is longer).
Wikipedia states the problem for positive integers, an integer threshold, and lists of equal length. The versions here allow zeros, a natural-number threshold, and lists of any length. This slightly more general formulation can be reduced to the fixed length form (by removing zeros and introducing copies of $\sqrt{4}$ to the longer list and $\sqrt{1} + \sqrt{1}$ to the shorter one).
References:
@[expose] public sectionnamespace PolyTimeopen ComplexityTheory RealThe square-root sum problem (single sum version)
A decision problem that asks, of a list of natural numbers and a threshold, whether the sum of the square roots of the elements of the list is at most that threshold.
Reference: Wikipedia
noncomputable def squareRootSum (l : List ℕ) (t : ℕ) : Bool :=
decide ((l.map fun n => √(n : ℝ)).sum ≤ t)Is the square-root sum problem polynomial time (single sum version)?
Reference: Wikipedia
@[category research open, question, AMS 68]
theorem isPolyTime_squareRootSum :
IsPolyTime (Function.uncurry squareRootSum) := ⊢ IsPolyTime (Function.uncurry squareRootSum)
All goals completed! 🐙The square-root sum problem (two sum version)
A decision problem that asks, of two lists of natural numbers, whether the sum of the square roots of the elements of the first list is at most the corresponding sum for the second list.
Reference: Wikipedia
noncomputable def squareRootSumTwoSided (l₁ l₂ : List ℕ) : Bool :=
decide ((l₁.map fun n => √(n : ℝ)).sum ≤ (l₂.map fun n => √(n : ℝ)).sum)Is the square-root sum problem polynomial time (two sum version)?
Reference: Wikipedia
@[category research open, question, AMS 68]
theorem isPolyTime_squareRootSumTwoSided :
IsPolyTime (Function.uncurry squareRootSumTwoSided) := ⊢ IsPolyTime (Function.uncurry squareRootSumTwoSided)
All goals completed! 🐙end PolyTime