Théorème de Savitch

Le théorème de Savitch est un théorème de théorie de la complexité, un domaine de l'informatique théorique. Il a été prouvé par Walter Savitch en 1970 et donne une relation entre les classes de complexité en espace, déterministes et non-déterministes. Une conséquence importante est que NPSPACE = PSPACE, c'est-à-dire, tout problème décidable sur une machine non-déterministe en espace polynomial, l'est aussi sur une machine déterministe en espace polynomial.

Histoire

Walter Savitch a démontré ce théorème dans sa thèse de master sous la direction de Stephen Cook^[1]. Il a été publié dans un article de recherche dans le Journal of Computer and System Sciences en 1972^[2]. Des idées de la preuve étaient déjà présentes dans un article de Philip Lewis, Juris Hartmanis et Richard Stearns publié en 1965^[1].

Énoncé du théorème

Le théorème stipule que pour toute fonction ƒ(n) ≥ log(n),

{\text{NSPACE}}\left(f\left(n\right)\right)\subseteq {\text{DSPACE}}\left(f^{2}\left(n\right)\right).

En d'autres termes, tout problème décidable sur une machine de Turing non-déterministe en espace ƒ(n), l'est également sur une machine de Turing déterministe en espace ƒ²(n).

Démonstration

Considérons un problème décidable par une machine de Turing M non-déterministe en espace ƒ(n). La démonstration consiste à se ramener un problème d'accessibilité dans le graphe des configurations de la machine M. On donne ensuite un algorithme récursif basé sur diviser pour régner qui utilise un espace ƒ²(n) pour le résoudre^[3].

Égalités de classes en espace

Un corollaire important est l'égalité des classes polynomiales en espace : PSPACE = NPSPACE. Il en va de même pour les classes exponentielles en espace : EXPSPACE = NEXPSPACE.

Bibliographie

Walter Savitch, « Relationships between nondeterministic and deterministic tape complexities », Journal of Computer and System Sciences, vol. 4, n^o 2,‎ 1972
(en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 4 (« Space complexity »)

Notes et références

↑ ^{a et b} Richard J. Lipton, « Savitch’s Theorem », sur Gödel's Lost Letter.
↑ Walter Savitch, « Relationships between nondeterministic and deterministic tape complexities », Journal of Computer and System Sciences, vol. 4, n^o 2,‎ 1972
↑ Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.5 (« Théorème de Savitch »).

v · m

Théorie de la complexité (informatique théorique)

Classes de complexité
(liste)

Classes classiques	L NL P NP NP-complet co-NP co-NP-complet NP-facile PSPACE E EXPTIME NE NEXPTIME EXPSPACE
Classes randomisées et quantiques	RP ZPP BPP EQP BQP QMA IP Protocole Arthur-Merlin PP BPL RL
Autres	P/poly NC APX AC⁰ UP
Classes de fonctions calculables	#-P #-P-complet
Hiérarchies	Hiérarchie polynomiale PH Hiérarchie booléenne
Familles de classes	DTIME NTIME DSPACE NSPACE

Théorèmes et outils

Théorèmes structurels	Théorème de Savitch Théorème d'Immerman-Szelepcsényi Théorème PCP Théorème de Karp-Lipton Théorème de Sipser-Gács-Lautemann Théorème de Toda
Outils et réductions	Théorème d'accélération linéaire Théorème de Cook Réduction polynomiale Kernelisation

Approches non-standard

Portail de l'informatique théorique

Read other articles:

Jean-Claude Pascal

Makam keluarga Jean-Claude Pascal di pemakaman Montparnasse, Paris Jean-Claude Pascal (24 Oktober 1927 – 5 Mei 1992), nama lahir Jean-Claude Villeminot, adalah seorang komedian dan penyanyi asal Prancis. Pascal memenangkan Kontes Lagu Eurovision 1961 mewakili Luxembourg dengan lagu Nous les amoureux. Pranala luar Jean-Claude Pascal di IMDb (dalam bahasa Inggris) lbsDaftar pemenang Kontes Lagu EurovisionNegara pemenang1950-an Swiss Belanda Prancis Belanda 1960-an Prancis Luxemb...

Hioki, Kagoshima

City in Kyushu, JapanHioki 日置市CityHioki CityIjūin city from the Joyama Park in 2020 FlagEmblemLocation of Hioki in Kagoshima PrefectureHiokiLocation in JapanCoordinates: 31°36′42″N 130°22′23″E / 31.61167°N 130.37306°E / 31.61167; 130.37306CountryJapanRegionKyushuPrefectureKagoshima PrefectureGovernment • MayorTakamitsu MiyajiArea • Total253.06 km2 (97.71 sq mi)Population (May 1, 2010) • Total51,...

Ha v New South Wales

1997 High Court of Australia case This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (November 2017) (Learn how and when to remove this template message) Ha v New South WalesCourtHigh Court of AustraliaFull case nameHa & anor v State of New South Wales & Ors Decided5 August 1997Citation(s)[1997] HCA 34, (1997) 189 CLR 465Court membe...

Margaret Ward

English Catholic martyr (1550–1588) For other uses, see Margaret Ward (disambiguation). SaintMargaret WardStatue of St Margaret Ward in St Etheldreda's Church, London.MartyrBornin the 1550sCongleton, Cheshire, EnglandDied(1588-08-30)30 August 1588Tyburn, London, EnglandVenerated inRoman Catholic ChurchAnglican CommunionBeatified15 December 1929 by Pope Pius XICanonized25 October 1970 by Pope Paul VIFeast25 October (in England), 4 MayAttributesbasket, rope Margaret Ward (c. 1550-30 Augu...

قصر أمينة هانم إلهامي

ساريا أمينة هانم إلهاميشعر الفندق مفتاح الحياةقصر الاميرة أمينة إلهامي علي اليسار فندق توفيق بالاسالتسميةأسماء سابقة قصر الخديوي توفيقأسماء بديلة فندق توفيق بلاس، سراي أمينة هانمنسبة الاسم إلى أمينة إلهاميمعلومات عامةالحالة مدرسةنوع المبنى فندق مدرسةالمكان حلوان �...

Rete pegs

Skin epithelium (purple) with lamina propria (underlying connective tissue) (pink) -- the epithelium exhibits rete pegs. Rete pegs protect the tissue from shearing.[1] Rete pegs (also known as rete processes or rete ridges) are the epithelial extensions that project into the underlying connective tissue in both skin and mucous membranes. In the epithelium of the mouth, the attached gingiva exhibit rete pegs, while the sulcular[2] and junctional epithelia do not.[3] Sca...

Jaguar XJS

Jaguar XJ-SInformasiProdusenJaguar CarsMasa produksi1975–1996PerakitanCoventry, InggrisBodi & rangkaKelasGrand tourerTata letakFR layoutKronologiPendahuluJaguar E-TypePenerusJaguar XK8 Jaguar XJ-S (atau Jaguar XJS) adalah grand tourer mewah yang diproduksi oleh produsen Inggris Jaguar tahun 1975 sampai 1996. XJ-S menggantikan E-Type (atau XK-E) bulan September 1975, dan basisnya diambil dari Jaguar XJ. XJS terakhir diproduksi tanggal 4 April 1996 dan terjual sebanyak 115.413 unit. Model...

Ski de fond aux Jeux olympiques de 2006

Pour des articles plus généraux, voir Ski de fond aux Jeux olympiques et Jeux olympiques d'hiver de 2006. Cet article est une ébauche concernant le ski de fond. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Ski de fond aux Jeux olympiques de 2006 Généralités Sport Ski de fond Éditions 20e Lieu(x) Turin Palmarès Plus titré(s) Estonie (3) et Suède (3) Plus médaillés Russie&...

Huiyang railway station

Railway station in Guangdong Province, China 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: Huiyang railway station – news · newspapers · books · scholar · JSTOR (April 2023) (Learn how and when to remove this message) You can help expand this article with text translated from the corresponding article in C...

Do You (Ne-Yo song)

2007 single by Ne-YoDo YouSingle by Ne-Yofrom the album Because of You ReleasedJuly 31, 2007Recorded2007GenreR&BLength3:48LabelDef JamSongwriter(s)Shaffer SmithMelvin SparkmanMarcus AllenMary J. Blige (remix)Producer(s)The Heavy WeightsNe-Yo singles chronology Because of You (2007) Do You (2007) Can We Chill (2007) Utada singles chronology Beautiful World(2007) Do You(2007) Stay Gold(2008) Mary J. Blige singles chronology Runaway Love(2006) Do You(2007) Just Fine(2007) Do You is a...

Vietnam del Nord

Vietnam del Nord (dettagli) (dettagli) Motto: (VI) Độc lập - Tự do - Hạnh phúc(IT) Indipendenza - Libertà - Felicità Vietnam del Nord - Localizzazione Dati amministrativiNome completoRepubblica Democratica del Vietnam Nome ufficialeViệt Nam Dân Chủ Cộng Hòa Lingue ufficialivietnamita InnoTiến Quân Ca CapitaleHanoi PoliticaForma di StatoStato socialista Forma di governoRepubblica monopartitica Capo di StatoPresidente del Vietnam del Nord Nascita2 settembre 1945(proclamaz...

مدلاين بلس

مدلاين بلسالشعارمعلومات عامةموقع الويب medlineplus.gov (الإنجليزية) نوع الموقع موقع ويب — قاعدة بيانات طبية الجوانب التقنيةاللغة الإنجليزية أهم الشخصياتالمالك المكتبة الوطنية لعلم الطب تعديل - تعديل مصدري - تعديل ويكي بيانات مدلاين بلس (بالإنجليزية: Medline Plus)‏ هو موقع متخصص بالأ�...

سفارة دولة فلسطين لدى هولندا

سفارة دولة فلسطين لدى هولندا فلسطين هولندا الإحداثيات 52°06′08″N 4°17′54″E / 52.1021°N 4.2982°E / 52.1021; 4.2982 البلد مملكة هولندا المكان لاهاي الاختصاص هولندا السَفير روان أبو يوسف الموقع الالكتروني الموقع الرسمي تعديل مصدري - تعديل سفارة دولة فلسطين لدى هولند...

Domagoj Pavičić

Questa voce sull'argomento calciatori croati è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Domagoj PavičićNazionalità Croazia Altezza178 cm Peso72 kg Calcio RuoloCentrocampista Squadra Arīs Salonicco CarrieraGiovanili 2009-2013 Dinamo Zagabria Squadre di club1 2012-2013→ Lokomotiva Zagabria18 (1)2014 Dinamo Zagabria10 (1)2014-2015→ Lokomotiva Zagabria21 (8)2015...

Religious skepticism

Type of skepticism relating to religion Religious skepticism is a type of skepticism relating to religion. Religious skeptics question religious authority and are not necessarily anti-religious but rather are skeptical of either specific or all religious beliefs and/or practices. Socrates was one of the most prominent and first religious skeptics of whom there are records; he questioned the legitimacy of the beliefs of his time in the existence of the Greek gods. Religious skepticism is not t...

Aldo Sensibile

Aldo SensibileSensibile alla Roma negli anni '60Nazionalità Italia Altezza175 cm Peso72 kg Calcio RuoloAllenatore (ex difensore) Termine carriera1975 - giocatore 2003 - allenatore CarrieraGiovanili 1960-1964 Lecce Squadre di club1 1964-1965 Lecce12 (0)1965-1967 Roma30 (0)1967-1969 Lecco43 (1)[1]1969-1975 Brindisi179 (4) Carriera da allenatore 1975-1976 LecceVice1976-1979 AscoliVice1979-1980 Civitanovese1980-1981 SambenedetteseVice1983...

آن كولير

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أبريل 2019) آن كولير معلومات شخصية الميلاد سنة 1970 (العمر 53–54 سنة)[1][2][3] لوس أنجلوس[4] مواطنة الولايات المتحدة[5] الحياة العملية المدرسة ال...

Тарас Шевченко-Грушівський: Хроніка його життя

«Тарас Шевченко-Грушівський: Хроніка його життя»АвторОлександр КониськийКраїнаУкраїнаМоваукраїнськаВидавництво«Дніпро»Видано1991Сторінок702ISBN5-308-01054-4Попередній твір1-й том 1898 р., 2-й том 1901 р.(Львів) Тарас Шевченко-Грушівський: Хроніка його життя - книга українського пис�...

Kai Bardal

Kai BardalNazionalità Norvegia Altezza167[1] cm Peso70[1] kg Calcio a 5 RuoloAllenatore Squadra Utleira CarrieraCarriera da allenatore 2008-2015 Vegakameratene2015- Utleira Calcio RuoloAllenatore CarrieraCarriera da allenatore 2007-2013 Kvik2014 Strindheim 1 I due numeri indicano le presenze e le reti segnate, per le sole partite di campionato.Il simbolo → indica un trasferimento in prestito. Statistiche aggiornate al 6 dicembre 2017 Modifi...

Leeds Tramways Company

Leeds Tramways CompanyTrams on BriggateOperationLocaleLeedsOpen16 September 1871Close2 February 1894StatusClosedInfrastructureTrack gauge4 ft 8+1⁄2 in (1,435 mm)Propulsion system(s)Horse and steamStatisticsRoute length14.16 miles (22.79 km) Leeds Tramways Company operated a tramway service in Leeds between 1871 and 1894.[1] History The Leeds Tramways Order 1871 authorised the Leeds Tramways Company to construct tramway lines in Leeds. The first route op...