Pith Number

pith:6OZKQ4EB

pith:2026:6OZKQ4EBPFTD6LMSNUAX5FK42P

not attested not anchored not stored refs pending

Exact Structural Abstraction and Tractability Limits

Tristan Simas

Orbit gaps prevent any exact structural classification of tractability on the full binary pairwise domain.

arxiv:2604.07349 v8 · 2026-04-08 · cs.CC · cs.AI · cs.LO

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{6OZKQ4EBPFTD6LMSNUAX5FK42P}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

Across four natural candidate structural tractability criteria, a uniform pair-targeted affine witness produces same-orbit disagreements and rules out exact structural classification on the full binary pairwise domain. Because that witness class already sits inside the universal semantic framework, the same obstruction applies to any universal exact-certification characterization over rigorously specified problems.

C2weakest assumption

That the pair-targeted affine witness is admissible within the universal exact-semantics framework and that the four candidate criteria adequately represent possible structural tractability predicates.

C3one line summary

Orbit gaps prevent exact classification of tractable problems by closure-invariant structural predicates on the full binary pairwise domain, blocking universal exact-certification characterizations.

Receipt and verification

First computed	2026-05-21T01:04:25.484877Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

f3b2a8708179663f2d926d017e955cd3e5698430cae0e4de9cf4cbf115212b76

Aliases

arxiv: 2604.07349 · arxiv_version: 2604.07349v8 · doi: 10.48550/arxiv.2604.07349 · pith_short_12: 6OZKQ4EBPFTD · pith_short_16: 6OZKQ4EBPFTD6LMS · pith_short_8: 6OZKQ4EB

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/6OZKQ4EBPFTD6LMSNUAX5FK42P \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: f3b2a8708179663f2d926d017e955cd3e5698430cae0e4de9cf4cbf115212b76

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "172da56f6dfb92739f796868b76480052b74334d3e94d20cedb215c16426f7ff",
    "cross_cats_sorted": [
      "cs.AI",
      "cs.LO"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.CC",
    "submitted_at": "2026-04-08T17:59:47Z",
    "title_canon_sha256": "a9bf5fde06946714089c784406be0f52ed1d982a2f7fd399c64946a7d3d19c7f"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2604.07349",
    "kind": "arxiv",
    "version": 8
  }
}