Pith Number

pith:PDHPN4QW

pith:2025:PDHPN4QW3JP6Y4VDYD6WV4SZIL

not attested not anchored not stored refs pending

Satisfiability in {\L}ukasiewicz logic and its unbounded relative

Filip Jankovec, Zuzana Hanikov\'a

The existential theory of the additive ℓ-group on the reals with -1 is NP-complete.

arxiv:2601.00817 v2 · 2025-12-22 · math.LO · 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{PDHPN4QW3JP6Y4VDYD6WV4SZIL}

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

We show that the existential theory of this structure is NP-complete. This provides a complexity upper bound for the set of theorems and the finite consequence relation of unbounded Łukasiewicz logic.

C2weakest assumption

The reduction from the existential theory of the unbounded Łukasiewicz structure (additive ℓ-group on reals with -1) to the existential theory of the standard MV-algebra on the reals is polynomial-time and preserves satisfiability.

C3one line summary

The existential theory of the real additive ℓ-group with -1 is NP-complete, providing a complexity bound for satisfiability in unbounded Łukasiewicz logic via reduction to the MV-algebra.

Receipt and verification

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

Canonical hash

78cef6f216da5fec72a3c0fd6af25942ea0796bbce5b331b4e78bb37f5f549a2

Aliases

arxiv: 2601.00817 · arxiv_version: 2601.00817v2 · doi: 10.48550/arxiv.2601.00817 · pith_short_12: PDHPN4QW3JP6 · pith_short_16: PDHPN4QW3JP6Y4VD · pith_short_8: PDHPN4QW

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/PDHPN4QW3JP6Y4VDYD6WV4SZIL \
  | 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: 78cef6f216da5fec72a3c0fd6af25942ea0796bbce5b331b4e78bb37f5f549a2

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "d4e3ae2f25423f7b7155b0ad0df22b99a43d01061c207c6b203147a00b1807b8",
    "cross_cats_sorted": [
      "cs.LO"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "math.LO",
    "submitted_at": "2025-12-22T19:57:02Z",
    "title_canon_sha256": "c2651d1bc9bf74f484ca1411c504518809a0cb722ebb9307ae9cbbeca123f028"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2601.00817",
    "kind": "arxiv",
    "version": 2
  }
}