Detecting the finer structure of the P vs NP problem with statistical mechanics: the case of the Wang tiling problem
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 least) two regions. In one region, polynomial algorithms to solve the NP complete problem of interest are available (and we discuss one possible realization inspire by the games of chess and go). In the second region the problem to find polynomial time algorithms is very similar to the problem to find polynomial time algorithms to determine the asymptotic behavior of discrete dynamical systems in the chaotic…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.18968
curl -X POST /api/v1/records/arxiv/2601.18968/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.18968/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'