2 papers
cond-mat.stat-mech2026
Detecting the finer structure of the P vs NP problem with statistical mechanics: the case of the Wang tiling problem
Fabrizio Canfora, Marco Cedeno
We introduce the idea that the P vs NP problem can have a finer structure. Given the NP complete problem of interest, the configurations space of the problem can be divided in (at…
cond-mat.stat-mech2025
Partial decidability protocol for the Wang tiling problem from statistical mechanics and chaotic mapping
Fabrizio Canfora, Marco Cedeno
We introduce a partial decidability protocol for the Wang tiling problem (which is the prototype of undecidable problems in combinatorics and statistical physics) by constructing a…