The extensional ESO NP-intermediate problem conjecture
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.