# What does NEXP mean in Computing?

NEXPTIME

## Translation

#### Find a translation for NEXPTIME in other languages:

Select another language:

• - Select -
• 简体中文 (Chinese - Simplified)
• Español (Spanish)
• Esperanto (Esperanto)
• 日本語 (Japanese)
• Português (Portuguese)
• Deutsch (German)
• العربية (Arabic)
• Français (French)
• Русский (Russian)
• 한국어 (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 »

## 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>.

### Quiz

#### The ultimate acronym test

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