Skip to content
Cairn Commons
X Sign in
Level A · Machine-checkable Hard Algorithms P-square-root-sum

Polynomial-time computability of comparisons of sums of square roots

Is the square-root sum problem polynomial time (single sum version)? Reference: Wikipedia

Current state (tracked automatically)

All tracked facts and sources
FactValueSource
Formal Conjectures: research statements in the file2 open, 0 solvedFormal Conjectures

Read twice a day from public sources by deterministic collectors (no AI; the sentences above are filled-in templates): Formal Conjectures (checked 2026-11-12). How it works.

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Try it with your chatbot Submit a claim Follow (RSS)
Cite 
@misc{cairn-square-root-sum,
  title        = {Polynomial-time computability of comparisons of sums of square roots},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/square-root-sum}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Fsquare-root-sum.json)](https://cairn-commons.com/problems/square-root-sum)
Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

  1. Get a task — one click
  2. Your chatbot works on it — 5–10 minutes, in its own tab
  3. Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

or , ,

ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

The question

isPolyTime_squareRootSum. Is the square-root sum problem polynomial time (single sum version)?

Reference: Wikipedia

isPolyTime_squareRootSumTwoSided. Is the square-root sum problem polynomial time (two sum version)?

Reference: Wikipedia

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 to the longer list and to the shorter one).

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.Wikipedia.SquareRootSum (2 statements).

theorem isPolyTime_squareRootSum :
    IsPolyTime (Function.uncurry squareRootSum)
theorem isPolyTime_squareRootSumTwoSided :
    IsPolyTime (Function.uncurry squareRootSumTwoSided)

What counts as progress

  • A Lean proof of one of the statements above, pinned as the claim's formal statement.
  • Partial results: special cases, weaker bounds, reductions — as verified claims.
  • Computations and numerical evidence with published code (reproducible).
  • Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
  • A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

Source and licence

Imported from Formal Conjectures (Wikipedia), commit 2f91d251c07f. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.