The extensional ESO NP-intermediate problem conjecture

An extensional ESO sentence Φ\Phi 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 Φ\Phi such that deciding Φ\Phi 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.