What does NEXP mean in Computing?

This page is about the meanings of the acronym/abbreviation/shorthand NEXP in the field in general and in the Computing terminology in particular.

NEXPTIME

Computing

Translation

Find a translation for NEXPTIME in other languages:

Select another language:

  • - Select -
  • 简体中文 (Chinese - Simplified)
  • 繁體中文 (Chinese - Traditional)
  • Español (Spanish)
  • Esperanto (Esperanto)
  • 日本語 (Japanese)
  • Português (Portuguese)
  • Deutsch (German)
  • العربية (Arabic)
  • Français (French)
  • Русский (Russian)
  • ಕನ್ನಡ (Kannada)
  • 한국어 (Korean)
  • עברית (Hebrew)
  • Gaeilge (Irish)
  • Українська (Ukrainian)
  • اردو (Urdu)
  • Magyar (Hungarian)
  • मानक हिन्दी (Hindi)
  • Indonesia (Indonesian)
  • Italiano (Italian)
  • தமிழ் (Tamil)
  • Türkçe (Turkish)
  • తెలుగు (Telugu)
  • ภาษาไทย (Thai)
  • Tiếng Việt (Vietnamese)
  • Čeština (Czech)
  • Polski (Polish)
  • Bahasa Indonesia (Indonesian)
  • Românește (Romanian)
  • Nederlands (Dutch)
  • Ελληνικά (Greek)
  • Latinum (Latin)
  • Svenska (Swedish)
  • Dansk (Danish)
  • Suomi (Finnish)
  • فارسی (Persian)
  • ייִדיש (Yiddish)
  • հայերեն (Armenian)
  • Norsk (Norwegian)
  • English (English)

Definition

What does NEXP mean?

NEXPTIME
In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2 n O ( 1 ) {\displaystyle 2^{n^{O(1)}}} . In terms of NTIME, N E X P T I M E = ⋃ k ∈ N N T I M E ( 2 n k ) {\displaystyle {\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})} Alternatively, NEXPTIME can be defined using deterministic Turing machines as verifiers. A language L is in NEXPTIME if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that For all x and y, the machine M runs in time 2 p ( | x | ) {\displaystyle 2^{p(|x|)}} on input ( x , y ) {\displaystyle (x,y)} For all x in L, there exists a string y of length 2 q ( | x | ) {\displaystyle 2^{q(|x|)}} such that M ( x , y ) = 1 {\displaystyle M(x,y)=1} For all x not in L and all strings y of length 2 q ( | x | ) {\displaystyle 2^{q(|x|)}} , M ( x , y ) = 0 {\displaystyle M(x,y)=0} We know P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIMEand also, by the time hierarchy theorem, that NP ⊊ NEXPTIMEIf P = NP, then NEXPTIME = EXPTIME (padding argument); more precisely, E ≠ NE if and only if there exist sparse languages in NP that are not in P.

see more »

Embed

Citation

Use the citation below to add this abbreviation to your bibliography:

Style:MLAChicagoAPA

"NEXP." Abbreviations.com. STANDS4 LLC, 2021. Web. 11 Apr. 2021. <https://www.abbreviations.com/term/1841850>.

Discuss this NEXP abbreviation with the community:

0 Comments

    Quiz

    The ultimate acronym test

    »
    ICU
    • A. Incremental Cost-Utility
    • B. Idiopathic Cystitis Ultrasound
    • C. Idiopathic Care Unit
    • D. Intensive Care Unit

    Browse Abbreviations.com

    Free, no signup required:

    Add to Chrome

    Get instant explanation for any acronym or abbreviation that hits you anywhere on the web!

    Free, no signup required:

    Add to Firefox

    Get instant explanation for any acronym or abbreviation that hits you anywhere on the web!