{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R812",
  "content_hash": null,
  "slug": "twnfa-attempt-superpolynomial-escalation-boundary",
  "type": "attempt",
  "title": "The fixed-alphabet transfer stops at a quadratic lower bound",
  "summary": "The binary macro encoding removes the growing-alphabet mismatch at constant-factor deterministic cost, while its imported lower bound is quadratic. The route therefore supplies no superpolynomial separation.",
  "relevance": "For Polynomial determinization of two-way finite automata, record twnfa-attempt-superpolynomial-escalation-boundary (“The fixed-alphabet transfer stops at a quadratic lower bound”) documents a concrete method, search boundary, or failed route. The record states: The binary macro encoding removes the growing-alphabet mismatch at constant-factor deterministic cost, while its imported lower bound is quadratic.",
  "relevance_source": "recorded",
  "body": "The attempted escalation had two parts. First, preserve the one-way-liveness lower bound while replacing \\(\\Sigma_h\\), whose size is \\(2^{h^2}\\), by one alphabet independent of \\(h\\). Second, compare the resulting lower bound with the state count of the encoded 1NFA.\n\nThe four-symbol construction uses \\(3h\\) source states. Its uniform binary decoder uses at most \\(9h\\) states. In either case, a hypothetical \\(s\\)-state 2DFA for the encoded language yields a \\((2s+2)\\)-state 2DFA for \\(\\operatorname{owl}_h\\). Substitution into the July 2026 theorem gives a lower bound of order \\(h^2\\), hence order \\(n^2\\) in either source-state normalization.\n\nA quadratic lower bound fits the polynomial alternative in the canonical question. The encoding cannot amplify the imported exponent because every state transformation costs a constant factor. A superpolynomial conclusion from this route would require a superpolynomial source lower bound for one-way liveness or another hard family. Neither appears in the checked sources. Another run of the same encoding with larger finite \\(h\\) cannot cross this boundary.",
  "status": "blocked",
  "evidence_grade": "self_reported",
  "scope": {
    "kind": "conditional",
    "statement": "conclusions obtainable by the recorded constant-factor encoding from the current h(h+1)/4 one-way-liveness theorem",
    "conditions": [
      "twnfa-claim-one-way-liveness-quadratic-bound",
      "twnfa-claim-fixed-binary-quadratic-transfer"
    ]
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "attempt",
    "citation": {
      "url": "https://arxiv.org/abs/2602.24279",
      "locator": "Method boundary derived 2026-07-28 from the fixed-alphabet macro reduction and Adeogun and Kapoutsis's Theorem 1"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/2602.24279",
    "locator": "Method boundary derived 2026-07-28 from the fixed-alphabet macro reduction and Adeogun and Kapoutsis's Theorem 1"
  },
  "relations": [
    {
      "slug": "R816",
      "title": "The one-way-liveness bound transfers to a fixed binary alphabet",
      "object_type": "claim",
      "relation": "depends_on",
      "direction": "outgoing"
    },
    {
      "slug": "R815",
      "title": "The fixed-alphabet determinization question remains open",
      "object_type": "claim",
      "relation": "constrains",
      "direction": "outgoing"
    },
    {
      "slug": "two-way-nfa-polynomial-determinization",
      "title": "two way nfa polynomial determinization",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}