Pith Number

pith:4UQ3FHUE

pith:2026:4UQ3FHUEP7S7AWTF5IEGTTMTY6

not attested not anchored not stored refs pending

Information Accessibility Limits in Structured NP Search

Jing-Yuan Wei

Polynomially many local queries cannot recover sparse violating subsets in near-P-matrix families with constant probability.

arxiv:2605.00953 v4 · 2026-05-01 · cs.IT · cs.CC · math.IT · math.OC

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

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{4UQ3FHUEP7S7AWTF5IEGTTMTY6}

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

any algorithm restricted to polynomially many queries cannot recover the violating subset with constant success probability.

C2weakest assumption

The restricted interaction model in which queries provide only local information that does not capture the globally encoded location of the violating subset.

C3one line summary

In structured P-matrix families with sparse violations, the violating subset cannot be recovered with constant success probability using polynomially many local queries due to an information-theoretic bottleneck.

Cited by

1 paper in Pith

Information Redistribution Under Reductions in NP Search

Receipt and verification

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

Canonical hash

e521b29e847fe5f05a65ea0869cd93c79a452821e47c7328ce80347611c56a18

Aliases

arxiv: 2605.00953 · arxiv_version: 2605.00953v4 · doi: 10.48550/arxiv.2605.00953 · pith_short_12: 4UQ3FHUEP7S7 · pith_short_16: 4UQ3FHUEP7S7AWTF · pith_short_8: 4UQ3FHUE

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/4UQ3FHUEP7S7AWTF5IEGTTMTY6 \
  | 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: e521b29e847fe5f05a65ea0869cd93c79a452821e47c7328ce80347611c56a18

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "83596933bb8a40c4b4a72176504100a802e5e61c8bbd0b72dc63ad6aac9d6f7e",
    "cross_cats_sorted": [
      "cs.CC",
      "math.IT",
      "math.OC"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.IT",
    "submitted_at": "2026-05-01T11:43:51Z",
    "title_canon_sha256": "423140d92fcc5c9c998f826dbce7c8039908fa1bf60c996ef05b242f9ffad90c"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.00953",
    "kind": "arxiv",
    "version": 4
  }
}