{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R38",
  "content_hash": null,
  "slug": "asser-claim-current-status",
  "type": "claim",
  "title": "Asser's complement problem remains open",
  "summary": "Current sources leave closure of all first-order spectra under complement open. It is enough to settle three-variable sentences whose finite models are undirected bipartite graphs. The two-variable counting fragment is already closed.",
  "relevance": "For Asser's complement problem for first-order spectra, record asser-claim-current-status (“Asser's complement problem remains open”) records a bound, answer, status fact, or structural consequence. The record states: Current sources leave closure of all first-order spectra under complement open.",
  "relevance_source": "recorded",
  "body": "A source and later-work search performed on 2026-07-28 found no proof or counterexample for the general complement question. Durand, Jones, Makowsky, and More state the problem as open and identify the complexity-theoretic equivalence\n\\[\n\\mathrm{Spec}=\\mathrm{coSpec}\\quad\\Longleftrightarrow\\quad \\mathrm{NE}=\\mathrm{coNE}.\n\\]\nKopczyński and Tan prove that the full question can be reduced to first-order sentences with three variables and one symmetric binary relation, under the semantic restriction that every finite model is an undirected bipartite graph. Their earlier two-variable result gives a boundary on the other side: spectra of two-variable logic with counting are exactly the semilinear sets and are closed under complement.\n\nThe fixed finite unary-vocabulary calculation in this packet supplies a complete fragment result and an exact quantifier-rank cost. It leaves the three-variable binary-relation frontier untouched. The unresolved remainder is the full statement: construct a first-order spectrum for every complement, or prove that one complement is outside the class of first-order spectra.",
  "status": "reported",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "universal",
    "statement": "first-order spectra over arbitrary finite relational vocabularies, with complementation inside the positive integers"
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://doi.org/10.23638/LMCS-14(2:4)2018",
      "locator": "Kopczyński and Tan, Corollary 1.2, pp. 2 and 13–14"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.23638/LMCS-14(2:4)2018",
    "locator": "Kopczyński and Tan, Corollary 1.2, pp. 2 and 13–14"
  },
  "relations": [
    {
      "slug": "R40",
      "title": "Three-variable bipartite graph sentences suffice",
      "object_type": "claim",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R37",
      "title": "The two-variable counting fragment is closed under complement",
      "object_type": "claim",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R39",
      "title": "Every fixed monadic vocabulary needs at most one extra rank",
      "object_type": "claim",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "R36",
      "title": "Sentence negation does not complement the spectrum",
      "object_type": "attempt",
      "relation": "constrains",
      "direction": "incoming"
    },
    {
      "slug": "R34",
      "title": "Dated source and duplicate audit",
      "object_type": "attempt",
      "relation": "evidences",
      "direction": "incoming"
    },
    {
      "slug": "R35",
      "title": "Mechanize the three-variable bipartite reduction",
      "object_type": "attempt",
      "relation": "addresses",
      "direction": "incoming"
    },
    {
      "slug": "R1813",
      "title": "Asser's complement problem remains open",
      "object_type": "claim",
      "relation": "supersedes",
      "direction": "incoming"
    },
    {
      "slug": "first-order-spectra-complement-closure",
      "title": "first order spectra complement closure",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}