Paperlane

no. 17 · Wednesday 18 November 2026

Hilbert's Tenth problem and NP-completeness of Boolean Syllogistic with unordered cartesian product

Domenico Cantone and Pietro Ursino

math.LO · v3

Abstract

We relate the decidability problem for BS with unordered cartesian product with Hilbert's Tenth problem and prove that BS with unordered cartesian product is NP-complete.

comments
One of the announced result is false
fields
Logic, Combinatorics
pdf ↗ page arXiv:2101.00198 ↗