NEXPTIME

The decision-problem class solvable by nondeterministic Turing machines in time exponential in a polynomial of input length.

Version

v1 · 2026-09-28 · History

Domain-specific #

10987

Domain group

Applied Sciences & Engineering

Origin domain

Computer Science & Software Engineering

Subdomains

Computational Complexity, Time Complexity → Computer Science & Software Engineering

Aliases

NEXP, Nondeterministic exponential time

Core Idea

NEXPTIME contains decision languages accepted by nondeterministic computation within 2^{n steps. The union over polynomial exponents allows different fixed powers for different machines while excluding double-exponential or unrestricted time.}

The verifier formulation makes the existential structure visible: yes instances have exponentially long certificates checkable in exponential time, while no instance has none. Logical spectra and multi-prover characterizations are deep equivalences, not alternate informal meanings of exponential difficulty.

Scope of Application

• Complexity theory. Locates decision problems by nondeterministic time.
• Succinct structures. Captures exponentially large witnesses encoded by small inputs.
• Descriptive complexity. Connects languages with finite-model spectra.
• Interactive proofs. Supports formal multi-prover characterizations.

Clarity

Specify decision language, input encoding, machine model, exact asymptotic clock, nondeterministic acceptance, and whether a claim is membership, hardness, or completeness. Do not infer lower bounds from failed algorithms. Inclusion test: Include decision languages with a nondeterministic machine running in 2^{p(n)} time for some polynomial p under a fixed reasonable encoding. Exclusion test: Exclude deterministic EXPTIME by definition, polynomial-time NP, double-exponential classes, unrestricted decidability, and informal claims that a problem merely feels exponentially hard. Nearest boundary: EXPTIME is contained in NEXPTIME, but membership in the deterministic subclass does not make the definitions identical. Exit condition: The class boundary is crossed when every allowed nondeterministic algorithm requires more than single-exponential polynomial time or when the problem is not encoded as a decision language. Common misclassifications: It is not synonymous with EXPTIME. It is not every problem requiring exponential resources in practice. It is not a class of optimization outputs without decision encoding. It is not double-exponential time. Nearest named distinctions: EXPTIME: Uses deterministic rather than nondeterministic machines. NP: Uses polynomial time and polynomial certificates. 2-EXPTIME: Allows double-exponential deterministic time. NEXPTIME-hard: A reduction property that does not itself prove membership.

Manages Complexity

One resource expression organizes machines, verifier witnesses, and theorem-based logical views. Encoding discipline prevents a compact representation from hiding an extra exponential.

Abstract Reasoning

1. Encode the task as a language.
2. Fix a reasonable input-length measure.
3. Construct the nondeterministic computation or verifier.
4. Bound every branch by 2 raised to a polynomial.
5. Prove soundness and completeness of acceptance.
6. Use reductions separately for hardness claims.

Knowledge Transfer

Machine–verifier equivalence transfers across standard complexity classes after resource and witness bounds are adjusted. NEXPTIME completeness and sparse or interactive-proof consequences require their own reductions and hypotheses.

Relationships to Other Abstractions

Current abstraction NEXPTIME Domain-specific

Parents (1) — more general patterns this builds on

• NEXPTIME is a kind of Complexity Class Domain-specific

  NEXPTIME is a strict kind of Complexity Class: it groups decision problems by nondeterministic exponential-time solvability.

Hierarchy paths (6) — routes to 5 parentless roots

• NEXPTIME → Complexity Class → Classification

Show alternative paths (5)

Neighborhood in Abstraction Space

NEXPTIME sits in a moderately populated region (40^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Digital Logic & Finite-State Machines (10 abstractions)

Nearest neighbors

• Exact Quantum Polynomial Time — 0.91
• NTIME — 0.88
• TC (Complexity) — 0.88
• Unambiguous Turing machine — 0.87
• Decision Tree Model — 0.86

Computed from structural-signature embeddings · 2026-10-08