What does nexptime mean?
Definitions for nexptime
nex·p·time
This dictionary definitions page includes all the possible meanings, example usage and translations of the word nexptime.
Wikipedia
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.
Numerology
Chaldean Numerology
The numerical value of nexptime in Chaldean Numerology is: 1
Pythagorean Numerology
The numerical value of nexptime in Pythagorean Numerology is: 7
References
Translation
Find a translation for the nexptime definition 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)
Word of the Day
Would you like us to send you a FREE new word definition delivered to your inbox daily?
Citation
Use the citation below to add this definition to your bibliography:
Style:MLAChicagoAPA
"nexptime." Definitions.net. STANDS4 LLC, 2024. Web. 29 Apr. 2024. <https://www.definitions.net/definition/nexptime>.
Discuss these nexptime definitions with the community:
Report Comment
We're doing our best to make sure our content is useful, accurate and safe.
If by any chance you spot an inappropriate comment while navigating through our website please use this form to let us know, and we'll take care of it shortly.
Attachment
You need to be logged in to favorite.
Log In