Return to Answer

Here are some examples of problems which I believe have a reasonable claim of being "natural" (at least, they can be stated concisely) which (when phrased as decision problems) do not appear to be known in P nor known NP-complete. So if you want a dichotomy theorem you either need to be more precise about what you mean by "natural" in a way that excludes examples like these, or you need to look for more precisely defined subclasses of the natural problems (e.g. MSO formulas with the second-order quantification restricted to be existential and outside everything else) for which there might be more hope of a dichotomy.

I've made this community wiki because I think it could be a large list.

• Are there evenly many perfect matchings? (Should be $\oplus P$-complete)
• Who wins at strings-and-coins? (Might be PSPACE-complete)
• What is its list coloring or list edge coloring number? (Might be $\Pi^p_2$-complete)
• Is it a unit disk graph? A unit distance graph? (Might be $\exists \mathbb{R}$-complete)
• Given two cubic Halin graphs with the same labeled outer face, how few steps does it take to convert one to the other by alternatingly contracting an interior edge and then uncontracting it the other way? (Equivalent to the open problem of computing rotation distance on binary search trees; might also be interesting for broader classes of cubic graphs)

Here are some examples of problems which I believe have a reasonable claim of being "natural" (at least, they can be stated concisely) which (when phrased as decision problems) do not appear to be known in P nor known NP-complete. So if you want a dichotomy theorem you either need to be more precise about what you mean by "natural" in a way that excludes examples like these, or you need to look for more precisely defined subclasses of the natural problems (e.g. MSO formulas with the second-order quantification restricted to be existential and outside everything else) for which there might be more hope of a dichotomy.

I've made this community wiki because I think it could be a large list.

• Are there evenly many 3-edge-colorings? (Should be $\oplus P$-complete)
• Who wins at strings-and-coins? (Might be PSPACE-complete)
• What is its list coloring or list edge coloring number? (Might be $\Pi^p_2$-complete)
• Is it a unit disk graph? A unit distance graph? (Might be $\exists \mathbb{R}$-complete)
• Given two cubic Halin graphs with the same labeled outer face, how few steps does it take to convert one to the other by alternatingly contracting an interior edge and then uncontracting it the other way? (Equivalent to the open problem of computing rotation distance on binary search trees; might also be interesting for broader classes of cubic graphs)

Here are some examples of problems which I believe have a reasonable claim of being "natural" (at least, they can be stated concisely) which (when phrased as decision problems) do not appear to be known in P nor known NP-complete. So if you want a dichotomy theorem you either need to be more precise about what you mean by "natural" in a way that excludes examples like these, or you need to look for more precisely defined subclasses of the natural problems (e.g. MSO formulas with the second-order quantification restricted to be existential and outside everything else) for which there might be more hope of a dichotomy.

I've made this community wiki because I think it could be a large list.

• Are there evenly many perfect matchings? (Should be $\oplus P$-complete)
• Who wins at strings-and-coins? (Might be PSPACE-complete)
• What is its list coloring or list edge coloring number? (Might be $\Pi^p_2$-complete)
• Is it a unit disk graph? A unit distance graph? (Might be $\exists \mathbb{R}$-complete)

Here are some examples of problems which I believe have a reasonable claim of being "natural" (at least, they can be stated concisely) which (when phrased as decision problems) do not appear to be known in P nor known NP-complete. So if you want a dichotomy theorem you either need to be more precise about what you mean by "natural" in a way that excludes examples like these, or you need to look for more precisely defined subclasses of the natural problems (e.g. MSO formulas with the second-order quantification restricted to be existential and outside everything else) for which there might be more hope of a dichotomy.

I've made this community wiki because I think it could be a large list.

• Are there evenly many perfect matchings? (Should be $\oplus P$-complete)
• Who wins at strings-and-coins? (Might be PSPACE-complete)
• What is its list coloring or list edge coloring number? (Might be $\Pi^p_2$-complete)
• Is it a unit disk graph? A unit distance graph? (Might be $\exists \mathbb{R}$-complete)
• Given two cubic Halin graphs with the same labeled outer face, how few steps does it take to convert one to the other by alternatingly contracting an interior edge and then uncontracting it the other way? (Equivalent to the open problem of computing rotation distance on binary search trees; might also be interesting for broader classes of cubic graphs)

Here are some examples of problems which I believe have a reasonable claim of being "natural" (at least, they can be stated concisely) which (when phrased as decision problems) do not appear to be known in P nor known NP-complete. So if you want a dichotomy theorem you either need to be more precise about what you mean by "natural" in a way that excludes examples like these, or you need to look for more precisely defined subclasses of the natural problems (e.g. MSO formulas with the second-order quantification restricted to be existential and outside everything else) for which there might be more hope of a dichotomy.

I've made this community wiki because I think it could be a large list.

• Are all nontrivial biconnected components isomorphic? (Should be GI-complete)
• Are there evenly many perfect matchings? (Should be $\oplus P$-complete)
• Who wins at strings-and-coins? (Might be PSPACE-complete)
• What is its list coloring or list edge coloring number? (Might be $\Pi^p_2$-complete)
• Is it a unit disk graph? A unit distance graph? (Might be $\exists \mathbb{R}$-complete)

Here are some examples of problems which I believe have a reasonable claim of being "natural" (at least, they can be stated concisely) which (when phrased as decision problems) do not appear to be known in P nor known NP-complete. So if you want a dichotomy theorem you either need to be more precise about what you mean by "natural" in a way that excludes examples like these, or you need to look for more precisely defined subclasses of the natural problems (e.g. MSO formulas with the second-order quantification restricted to be existential and outside everything else) for which there might be more hope of a dichotomy.

I've made this community wiki because I think it could be a large list.

• Are there evenly many perfect matchings? (Should be $\oplus P$-complete)
• Who wins at strings-and-coins? (Might be PSPACE-complete)
• What is its list coloring or list edge coloring number? (Might be $\Pi^p_2$-complete)
• Is it a unit disk graph? A unit distance graph? (Might be $\exists \mathbb{R}$-complete)