SL (clase de complejidad)

En teoría de la complejidad computacional, la clase de complejidad SL (espacio logarítmico simétrico, del inglés Symmetric Logspace o Sym-L) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, tal que:

  1. Si la respuesta es positiva, existe uno o más cómputos de la máquina que aceptan.
  2. Si la respuesta es negativa, todos los cómputos de la máquina rechazan la entrada.
  3. Si la máquina puede hacer una transición no determinista entre una configuración A y una configuración B, también puede hacer una transición de B hacia A (condición de simetría).

En 2004 se demostró que esta clase de complejidad es equivalente a L. En otras palabras, la condición de simetría en la máquina de Turing no determinista la hace equivalente a una máquina de Turing determinista.

Referencias

  • H. R. Lewis y C. H. Papadimitriou. Symmetric space-bounded computation, Theoretical Computer Science 19:161-187, 1982.
  • O. Reingold. Undirected st-connectivity in log-space, no publicado, 2004

Read other articles:

Nièvre

Para otros usos de este término, véase Nièvre (desambiguación). Nièvre Departamento BanderaEscudo Coordenadas 47°05′00″N 3°30′00″E / 47.083333333333, 3.5Capital NeversEntidad Departamento • País  Francia • Región Borgoña-Franco Condado • Prefectura Nevers • Subprefecturas Château-ChinonClamecyCosne-Cours-sur-LoirePresidente del Consejo Patrice Joly[1]​Subdivisiones Distritos 4Cantones 32Comunas 312Superficie Puesto 22....

 

Poena cullei

Artikel atau sebagian dari artikel ini mungkin diterjemahkan dari Poena cullei di en.wikipedia.org. Isinya masih belum akurat, karena bagian yang diterjemahkan masih perlu diperhalus dan disempurnakan. Jika Anda menguasai bahasa aslinya, harap pertimbangkan untuk menelusuri referensinya dan menyempurnakan terjemahan ini. Anda juga dapat ikut bergotong royong pada ProyekWiki Perbaikan Terjemahan. (Pesan ini dapat dihapus jika terjemahan dirasa sudah cukup tepat. Lihat pula: panduan penerjemaha...

 

Condado de Río Indio

Condado de Río Indio Condado Escudo Ubicación en el estado de FloridaCoordenadas 27°42′N 80°35′O / 27.7, -80.58Sede de condado Vero BeachEntidad Condado • País  Estados Unidos • Estado  FloridaEventos históricos   • Fundación 30 de mayo de 1925Superficie   • Total 1598 km²  • Agua 294 km² (114 mi²) km²Población (2000)   • Total 112 947 hab. • Densidad 99,99 hab/km² Si...

ルナ (韓国の歌手)

この存命人物の記事には検証可能な出典が不足しています。信頼できる情報源の提供に協力をお願いします。存命人物に関する出典の無い、もしくは不完全な情報に基づいた論争の材料、特に潜在的に中傷・誹謗・名誉毀損あるいは有害となるものはすぐに除去する必要があります。出典検索?: ルナ 韓国の歌手 – ニュース · 書籍 · スカラー ...

 

Mitchell Park Football Club

Mitchell ParkNamesFull nameMitchell Park Football ClubClub detailsFounded1968; 55 years ago (1968)Colours  green   white   redCompetitionSouth Australian Amateur Football LeaguePresidentCraig Weekley[1]CoachScott WeekleyGround(s)Mitchell Park Oval, Mitchell ParkUniforms Home Other informationOfficial websitemitchellparkfc.com The Mitchell Park Football Club, nicknamed the Lions, is an Australian rules football club that was founded in 1968 by Edward Mc...

 

Philip Mechanicus (fotograaf)

Philip Mechanicus Foto: Karel A. Meijers, 1966, op de domtoren Utrecht Algemene informatie Geboren Amsterdam, 13 augustus 1936 Overleden Amsterdam, 30 juli 2005 Land Koninkrijk der Nederlanden Werk Beroep fotograaf en publicist Rechten oeuvre auteursrechtelijk beschermd RKD-profiel Media op Wikimedia Commons Portaal    Kunst & Cultuur Philip Mechanicus (Amsterdam, 13 augustus 1936 – aldaar, 30 juli 2005) was een Nederlands fotograaf en publicist. Mechanicus werd vernoemd naar ...

إيفا التمان

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أكتوبر 2019) إيفا التمان (بالألمانية: Eva Altmann)‏    معلومات شخصية الميلاد 17 ديسمبر 1903[1]  برلين  تاريخ الوفاة 1 مارس 1991 (87 سنة) [1]  مواطنة ألمانيا ألمانيا ...

 

Umberto I

Makam Umberto I Humbert I (bahasa Italia: Umberto I; skt. 980  – 1042 atau 1047 x 1048), lebih dikenal sebagai Humbert yang Bertangan Putih (Prancis: Humbert aux blanches-mains) atau Humbert Whitehand (bahasa Italia: Umberto Biancamano)[2]merupakan seorang pendiri Wangsa Savoia. Pengabdiannya kepada kaisar Jerman Heinrich II dan Konrad II dihargai dengan wilayah Maurienne dan Aosta dan wilayah di Valais, yang seluruhnya dengan biaya uskup setempat dan uskup agu...

 

ABC Unified School District

School district in California ABC Unified School DistrictLocationCerritos, CaliforniaSoutheastern Los Angeles CountyDistrict informationTypePublicGradesK-12 and Adult SchoolEstablished1965SuperintendentToan NguyenSchools30Other informationWebsitewww.abcusd.k12.ca.us The ABC Unified School District is a school district that is based in Cerritos, California, United States. ABCUSD serves the cities of Artesia, most of Cerritos, Hawaiian Gardens, the portion of Lakewood east of the San Gabriel Ri...

Poppe Damave

Dutch painter Poppe Damave (1921–1988) was a Dutch painter. He was born in Groningen, but according to the RKD his parents moved to Haarlem when he was four, where he lived the rest of his life.[1] He was a pupil of Henri Frédéric Boot and A.J. Grootens.[1] He lived for 9 years on Lange Herenstraat 9 near the Haarlem railway station and until his death in 1988, on Donkere Spaarne 54. He was married to Katherina Martin and they had 6 daughters and 4 sons.[1] He was ...

 

SENTRI

This article may rely excessively on sources too closely associated with the subject, potentially preventing the article from being verifiable and neutral. Please help improve it by replacing them with more appropriate citations to reliable, independent, third-party sources. (April 2019) (Learn how and when to remove this template message) SENTRI program logo SENTRI lanes at San Ysidro border crossing/port of entry, 2015. Tijuana, Mexico to San Diego, California. The Secure Electronic Network...

 

Dirty Linen (film)

1999 film Dirty Linen(Panni sporchi)Film posterDirected byMario MonicelliWritten bySuso Cecchi D'AmicoMario MonicelliMasolino D'AmicoMargherita D'AmicoProduced byGiovanni Di ClementeStarringPaolo BonacelliMichele PlacidoMariangela MelatoGigi ProiettiCinematographyStefano ColettaMusic byLuis Enriquez BacalovDistributed byC.D.I.Release date 29 January 1999 (1999-01-29) Running time110 minutesCountryItalyLanguageItalian Dirty Linen (Italian: Panni sporchi) is a 1999 Italian comedy...

Unitarianism

Nontrinitarian branch of Christianity This article is about the Christian theological tradition. For the doctrinal position, see Nontrinitarianism. For the liberal religious movement, see Unitarian Universalism. For its British counterpart, see General Assembly of Unitarian and Free Christian Churches. For other uses, see Unitarian. Part of a series onTheism Types of faith Agnosticism Apatheism Atheism Deism Henotheism Ietsism Ignosticism Monotheism Monism Dualism Monolatry Kathenotheism Omni...

 

Grantchester (TV series)

British detective drama GrantchesterGenreCozy mysteryPeriod dramaBased onThe Grantchester Mysteries by James RuncieDeveloped byDaisy CoulamStarring James Norton Robson Green Morven Christie Tessa Peake-Jones Al Weaver Nick Brimble Kacey Ainsworth Oliver Dimsdale Tom Brittney Melissa Johns Charlotte Ritchie ComposerJohn LunnCountry of originUnited KingdomOriginal languageEnglishNo. of series8No. of episodes51 (list of episodes)ProductionExecutive producersDiederick SanterRebecca EatonProducers...

 

Alfred Rawlinson (bishop)

British divinity scholar, Anglican bishop (1884–1960) Alfred RawlinsonBishop of DerbyChurchAnglicanDioceseDiocese of DerbyIn office1936–1959PredecessorEdmund PearceSuccessorGeoffrey AllenOther post(s)Archdeacon of Auckland, Canon of Durham, & bishop's examining chaplain (1929–1936)OrdersOrdination1909 (deacon); 1910 (priest)Consecration1936by Cosmo Gordon LangPersonal detailsBorn(1884-07-17)17 July 1884Newton-le-Willows, Lancashire, United KingdomDied17 July 1960(1960-07-17) (a...

Sooner Athletic Conference

American college athletic conference This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Sooner Athletic Conference – news · newspapers · books · scholar · JSTOR (June 2020) (Learn how and when to remove this template message) Sooner Athletic ConferenceAssociationNAIAFounded1978CommissionerJohn MartinSports fiel...

 

Erich Cohn

German chess player (1884–1918) Erich Cohn Erich Cohn (Hebrew: אריק קוהן, March 1, 1884, Berlin – August 28, 1918, France) was a German chess master.[1] He won or tied for 1st in several tournaments in Berlin (1902, 1905, 1906, 1909/10, 1914).[2] In strong tournaments, he tied for 11-12th at Berlin 1903 (Horatio Caro won). He took 10th at Coburg 1904 (the 14th DSB Congress, Hauptturnier A, Augustin Neumann won).[3] In 1905, he took 5th in Barmen (A tourn). ...

 

Panum Building

55°41′37″N 12°33′50″E / 55.69361°N 12.56389°E / 55.69361; 12.56389 The Panum Building (2012) The Panum Building (formerly referred to as the Panum Institute) is a large building complex that is part of the University of Copenhagen's North Campus in Copenhagen, Denmark. It houses the Faculty of Health and Medical Sciences. This includes the Dental School and the Faculty of Medicine as well as The School of Oral Health Care and The School for Dental Technicia...

Algoritmo de Maekawa

El algoritmo de Maekawa es un algoritmo que se emplea para crear exclusión mutua en un sistema distribuido. Para una red de N nodos, el algoritmo utilizará únicamente un total de c*√N mensajes para crear esta exclusión mutua, siendo 'c' una constante que puede variar entre los valores 3 y 5. En esta red supuesta, también se supone que todos los nodos se comunican solamente mediante mensajes y no tienen memoria compartida, así como que los mensajes se reciben en el mismo orden que han ...

 

1 карбованець «150-річчя з дня народження П. І. Чайковського»

150-річчя з дня народження П. І. Чайковського СРСРНомінал 1 карбованецьМаса 12.8 гДіаметр 31 мм ммТовщина 2.3 ммГурт гладкий з написомМетал мідно-нікелевий сплавРоки карбування 1990Аверс Опис герб СРСРРеверс Опис портрет П. І. ЧайковськогоГравер І. С. Комшилов П. І. Чай...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!