NSPACE

In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. It is the non-deterministic counterpart of DSPACE.

Complexity classes

The measure NSPACE is used to define the complexity class whose solutions can be determined by a non-deterministic Turing machine. The complexity class NSPACE(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine, M, using space O(f(n)), where n is the length of the input.^[1]

Several important complexity classes can be defined in terms of NSPACE. These include:

REG = DSPACE(O(1)) = NSPACE(O(1)), where REG is the class of regular languages (nondeterminism does not add power in constant space).
NL = NSPACE(O(log n))
CSL = NSPACE(O(n)), where CSL is the class of context-sensitive languages.
PSPACE = NPSPACE = $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$
EXPSPACE = NEXPSPACE = $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$

The Immerman–Szelepcsényi theorem states that NSPACE(s(n)) is closed under complement for every function $s (n) \geq log n .$

A further generalization is ASPACE, defined with alternating Turing machines.

Relation with other complexity classes

DSPACE

NSPACE is the non-deterministic counterpart of DSPACE, the class of memory space on a deterministic Turing machine. First by definition, then by Savitch's theorem, we have that:

${\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2}].$

Time

NSPACE can also be used to determine the time complexity of a deterministic Turing machine by the following theorem:

If a language L is decided in space S(n) (where S(n) ≥ log n) by a non-deterministic TM, then there exists a constant C such that L is decided in time O(C^S(n)) by a deterministic one.^[2]

Limitations

The measure of space complexity in terms of DSPACE is useful because it represents the total amount of memory that an actual computer would need to solve a given computational problem with a given algorithm. The reason is that DSPACE describes the space complexity used by deterministic Turing machines, which can represent actual computers. On the other hand, NSPACE describes the space complexity of non-deterministic Turing machines, which are not useful when trying to represent actual computers. For this reason, NSPACE is limited in its usefulness to real-world applications.

References

^ Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Course Technology. pp. 303–304. ISBN 978-0-534-95097-2.
^ Goddard, Wayne (2008). Introducing the Theory of Computation. Jones and Bartlett Publishers, Inc. p. 183. ISBN 978-0-7637-4125-9.

External links

Complexity Zoo: NSPACE(f(n)).

v t e Complexity classes
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL FL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete TFNP FNP AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system
List of complexity classes

Read other articles:

Zain Al Rafeea

Zain Al RafeeaAl Rafeea di Festival Film Cannes 2018Lahir10 Oktober 2004 (umur 19)Daraa, SuriahKebangsaanOrang Suriah di NorwegiaPekerjaanAktor Zain Al Rafeea (bahasa Arab: زين الرافعي, lahir 10 Oktober 2004)[1] adalah aktor asal Suriah. Ia terkenal atas perannya sebagai Zain dalam film Lebanon berjudul Capernaum, yang mengantarkannya sebagai pemenang dari the Jury Prize di Film Festival Cannes 2018. Kehidupan dan karier Al Rafeea lahir di Daraa, Suriah pada 2004 s...

Fransium

87FrFransiumBatu ini, mineral torit, mungkin mengandung beberapa atom fransium pada satu waktu Sifat umumNama, lambangfransium, FrPengucapan/fransium/[1] Fransium dalam tabel periodik 87Fr Hidrogen Helium Lithium Berilium Boron Karbon Nitrogen Oksigen Fluor Neon Natrium Magnesium Aluminium Silikon Fosfor Sulfur Clor Argon Potasium Kalsium Skandium Titanium Vanadium Chromium Mangan Besi Cobalt Nikel Tembaga Seng Gallium Germanium Arsen Selen Bromin Kripton Rubidium Strontium Yttri...

Victoria Eugenia Fernández de Córdoba, 18th Duchess of Medinaceli

Spanish noblewoman The Most ExcellentVictoria Eugenia Fernández de CórdobaGrandee of Spain (more...)Duchess of MedinaceliReign13 July 1956 – 18 August 2013PredecessorLuis Fernández de Córdoba, 17th Duke of MedinaceliSuccessorPrince Marco of Hohenlohe-Langenburg, 19th Duke of Medinaceli[1] Full nameMaría Victoria Eugenia Fernández de Córdoba, Fernández de Henestrosa, Salabert y Gayoso de los CobosBorn(1917-04-16)16 April 1917Medinaceli Palace, Madrid, SpainDied(2013-08-18...

Gary Woodland

American professional golfer Gary WoodlandWoodland with the 2019 U.S. Open trophyPersonal informationFull nameGary Lynn WoodlandBorn (1984-05-21) May 21, 1984 (age 39)Topeka, Kansas, U.S.Height6 ft 1 in (1.85 m)Weight190 lb (86 kg; 14 st)Sporting nationality United StatesResidenceDelray Beach, FloridaSpouseGabby GranadoChildren4CareerCollegeWashburn UniversityUniversity of KansasTurned professional2007Current tour(s)PGA TourFormer tour(s)Nationwide Tour...

Tamil Nadu Information Commission

Statutory body in Tamil Nadu, India This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Tamil Nadu Information Commission – news · newspapers · books · scholar · JSTOR (December 2019) (Learn how and when to remove this template message) Tamil Nadu Information Commission is a statutory body in the state of Tamil Nadu, India. It was created in pursuance of th...

Tao-Klarjeti (historical region)

For a historical Georgian monarchy, see Kingdom of the Iberians. This article contains translated text and the factual accuracy of the translation should be checked by someone fluent in Georgian and English. Historical region in Western Asia, CaucasusTao-KlarjetiHistorical regionMap of modern Tao-Klarjeti, region Georgia lost in 1921AreaCaucasusRegionWestern Asia Map of Tao-Klarjeti with historical subregions Tao-Klarjeti (Georgian: ტაო-კლარჯეთი, romanized: t'ao-k'la...

Danny Vranes

Questa voce sull'argomento cestisti statunitensi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Danny Vranes Vranes in azione con la maglia della Teorematour Arese Nazionalità Stati Uniti Altezza 201 cm Peso 95 kg Pallacanestro Ruolo Ala grande Termine carriera 1992 Carriera Giovanili Skyline High School1977-1981 Utah Utes Squadre di club 1981-1986 Seattle S.Sonics395 (2.352)1986-1988...

Expédit de Mélitène

Saint ExpéditStatue de saint Expédit à Varsovie.BiographieNaissance MélitèneDécès 303MélitèneÉpoque Empire romainActivité Domaine militaireAutres informationsÉtape de canonisation SaintUnité Legio XII Fulminata (?)Grade militaire CenturionFête 19 avrilmodifier - modifier le code - modifier Wikidata Selon le Martyrologium Hieronymianum, saint Expédit (Սուրբ Էքսպեդիտ en arménien) est un soldat romain d’Arménie, peut-être commandant, converti au christianisme et ...

Skikda

City in AlgeriaSkikda سكيكدةCityLocation of Skikda in the Skikda ProvinceSkikdaLocation within AlgeriaCoordinates: 36°52′N 6°54′E / 36.867°N 6.900°E / 36.867; 6.900Country AlgeriaProvinceSkikdaDistrictSkikda DistrictFounded1200 BCArea • Total52 km2 (20 sq mi)Elevation18 m (59 ft)Population (2008 census) • Total182,903 • Density3,500/km2 (9,100/sq mi)Time zoneUTC+1 (CET)Postal cod...

Composizioni di Leonard Bernstein

Voce principale: Leonard Bernstein. Leonard Bernstein, ca. 1950s. Questa è una lista di composizioni del compositore americano Leonard Bernstein. Indice 1 Balletto 2 Opera 3 Musical 4 Musiche di scena ed altro teatro 5 Musica da film 6 Orchestra 7 Coro 8 Musica da camera 9 Musica vocale 10 Musica per pianoforte 11 Altra musica 12 Note 13 Bibliografia Balletto Fancy Free (in seguito ha fornito materiale per On the Town e West Side Story) (1944) Facsimile, Saggio coreografico per orchestra (1...

Mount Rearguard

Mountain in the state of Montana Mount RearguardSoutheast aspect, from Beartooth HighwayHighest pointElevation12,209 ft (3,721 m)[1]Prominence1,044 ft (318 m)[1]Coordinates45°02′54″N 109°31′35″W / 45.04833°N 109.52639°W / 45.04833; -109.52639[2]GeographyMount RearguardLocation in MontanaShow map of MontanaMount RearguardLocation in the United StatesShow map of the United States LocationCarbon County, Montana,...

مطبخ إفريقيا

لمعانٍ أخرى، طالع أفريقي (توضيح). المطبخ الأفريقي يعكس تقاليد الطبخ الشعبية الإفريقية التقليدية وما نتج من أنواع طعام جديدة بتأثير من الأوروبيين والآسيويين الذين استوطنوا بعض المناطق الإفريقية.[1][2][3] وبما أن مساحة القارة الإفريقية هي ثاني أكبر مساحة قا...

Joey Badass

American rapper and actor from New York (born 1995) Joey BadassBadass performing in 2017Background informationBirth nameJo-Vaughn Virginie ScottAlso known asJayOhVeeJozif BadmonJoey BBorn (1995-01-20) January 20, 1995 (age 29)Brooklyn, New York City, U.S.GenresEast Coast hip hopprogressive rap[1]Occupation(s) Rapper singer songwriter actor DiscographyJoey Badass discographyYears active2010–present[2]Labels Pro Era Cinematic RED Columbia[3] Relentless[4] ...

豪栄道豪太郎

豪栄道豪太郎場所入りする豪栄道基礎情報四股名澤井豪太郎→豪栄道豪太郎本名澤井豪太郎愛称ゴウタロウ、豪ちゃん、GAD[1][2]生年月日 (1986-04-06) 1986年4月6日（38歳）出身大阪府寝屋川市身長 183cm体重 160kgBMI 47.26所属部屋境川部屋得意技右四つ・出し投げ・切り返し・外掛け・首投げ・右下手投げ成績現在の番付引退最高位東大関生涯戦歴 696勝493敗...

IAI Heron

Long-endurance unmanned aerial vehicle Heron IAI Heron 1 UAV in flight Role Unmanned surveillance and reconnaissance aerial vehicleType of aircraft National origin Israel Manufacturer Israel Aerospace Industries First flight 1994 Introduction 2005 Status Active, in production Primary users Israeli Defence ForceIndian Air Force Brazilian Federal Police Turkish Air Force Variants EADS Harfang IAI Eitan Avionics Services Caçador IAI Heron on display at the Paris Air Show 2009 IAI Super Her...

Scottish Church College

Public college in Kolkata, West Bengal, India Scottish Church CollegeEmblem of the Scottish Church CollegeLatin: Collegium Ecclesiae ScoticaeFormer names1830: General Assembly's Institution1843: Free Church Institution1863: Duff College1908: Scottish Churches College1929: Scottish Church CollegeMottoNec Tamen Consumebatur[1] (Latin)Motto in EnglishThe bush burns, but is not consumedTypePublicEstablished13 July 1830; 193 years ago (13 July 1830)FounderAlexander DuffRe...

North-Western Territory

Region of British North America (1670–1870) This article is about an early territory of British North America. For the 18th-century U.S. territory, see Northwest Territory. For the extant Canadian territory, see Northwest Territories. For other geographical names that use the term Northwestern, see Northwestern (disambiguation). North-Western TerritoryTerritory of British North America1670–1870 The generic red British colonial ensignMap of North-Western Territory, including more of Rupert...

Cheers

American television sitcom (1982–1993) This article is about the American TV series. For other uses, see Cheers (disambiguation). CheersGenreSitcomCreated by Glen and Les Charles James Burrows Directed by James Burrows Various (seasons 6–11) Starring Ted Danson Shelley Long Nicholas Colasanto Rhea Perlman George Wendt John Ratzenberger Kelsey Grammer Woody Harrelson Kirstie Alley Bebe Neuwirth Theme music composer Gary Portnoy Judy Hart Angelo Opening themeWhere Everybody Knows Your Name ...

Steppin' Out (Jack McDuff album)

1969 studio album by Jack McDuffSteppin' OutStudio album by Jack McDuffReleased1969RecordedJuly 14, 1961, January 8, 1963, July, 1964, early 1965 and February 1966New Jersey and New York CityGenreJazzLength35:29LabelPrestigePR 7666ProducerLew FuttermanJack McDuff chronology I Got a Woman(1964–66) Steppin' Out(1969) A Change is Gonna Come(1966) Professional ratingsReview scoresSourceRatingAllmusic[1]The Rolling Stone Jazz Record Guide[2] Steppin' Out is an album by or...

Genomslående tunga

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2018-12) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. En genomslående tunga, också kallad fritunga och frisvängande tunga, är på vissa blåsinstrument en tonalstrande tunga som vibrerar fritt genom det hål den sitter fästad över, och som den bara nästan täcker. S�...