The extensional ESO NP-intermediate problem conjecture
The extensional ESO NP-intermediate problem conjecture
An extensional ESO sentence defines a decision problem by asking whether the sentence holds on the input structure. Extensional ESO NP-intermediate conjecture. There is an extensional ESO sentence such that deciding is NP-intermediate. The surrounding discussion points to examples polynomial-time equivalent to Graph Isomorphism and to the complement of Monotone Dualization, but does not establish the existence of an NP-intermediate problem; this conjecture remains open.
Sources & referencesView supporting material
Primary source
Manuel Bodirsky and Santiago Guzmán Pro, “On the Computational Power of Extensional ESO”, arXiv:2511.08515 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.