L (complexité)

En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée[1],[2]. Pour être plus précis, l'exigence sur l'espace de taille logarithmique se réfère à l'espace supplémentaire utilisable. Elle est aussi parfois notée LOGSPACE[réf. nécessaire].

Intuitivement, cette classe contient les problèmes que l'on peut décider avec un nombre constant de pointeurs[2] sur des cases mémoires de l'entrée du problème et un nombre constant de données supplémentaires (des compteurs dont les valeurs sont entre 0 et une grandeur polynomiale en la taille de l'entrée, des booléens, etc.).

Définition formelle

Si l'on appelle l'ensemble de tous les problèmes qui sont décidés par des machines de Turing déterministes utilisant un espace (en plus de l'entrée) pour une fonction en la taille de l'entrée , alors on peut définir L formellement par :

Exemples de problèmes

Exemples de langages

Le langage est dans L[3]. Voici un algorithme qui décide en espace logarithmique :

procedure M(w)
 si w vide
   accepter

 i = 0
 tant que w[i] == 0
     i := i+1

 compteurzero := i

 tant que w[i] == 1
     i := i+1

 si w[i] != ' ' (différent de la fin de mot)
     refuser

 si compteurzero == (i - compteurzero)
     accepter
 sinon
     refuser

Le mot w n'est pas modifié : c'est l'entrée et elle n'est pas comptabilisée dans le calcul de la mémoire utilisée. On ne compte que la mémoire supplémentaire, à savoir, les variables i et compteurzero qui sont des entiers positifs bornées par |w| et que l'on peut coder en espace logarithmique en |w|.

Le langage des mots généré par la grammaire algébrique suivante est dans L : S --> (S) | SS | ε[4].

Multiplication

La représentation binaire de l'entier est notée dans cette section. Le langage est dans L[5]. L'algorithme suivant reconnait en utilisant un espace en , où est la taille de son entrée. L'algorithme prend en entrée trois entiers n, m et p vérifie que la multiplication de n par m vaut bien p. Il calcule à chaque itération le ie bit du résultat de la multiplication et le compare au ie bit de p.

Les procédures suivantes sont utilisées dans la description de l'algorithme :

  • incrémenter(x), incrémente la variable x ;
  • est_un(x, i), indique si le ie bit de x est non nul, si i est plus grand que la taille de x le bit est considéré comme nul ;
  • diviser_par_deux(x), remplace x par le quotient de sa division euclidienne par 2 ; cette opération peut être implémentée comme un décalage des bits de x de un vers les bits de poids faibles.
   procedure verifierMultiplication(n, m, p)
       retenue = 0
       i = 0
       tant que i < max(|n| + |m| - 1, |p|)
           j = 0
           tant que j < i
               k = 0
               tant que k + j <= i
                   si est_un(n, j) et est_un(m, k)
                       incrémenter(retenue)
                   k := k + 1
               si p[i] != retenue[0]
                   rejeter
               diviser_par_deux(retenue)
               j := j + 1
           i := i + 1
       accepter

La valeur des compteurs i, j et k utilisés ne dépasse pas la taille de l'entrée et peuvent donc être codés en espace logarithmique en la taille de l'entrée. Les procédures introduites et les comparaisons utilisent au plus un espace logarithmique en la taille de l'entrée. Enfin, la valeur de la variable retenue ne peut pas dépasser , elle peut donc être codée sur un espace en .

Relations avec les autres classes de complexité

On connait les inclusions suivantes :

NC1 ⊆ LNLAC1NCPNPPSPACE

On sait aussi que l'inclusion de L dans PSPACE est stricte, donc l'une des inclusions ci-dessus est stricte. Il n'est pas impossible qu'elles le soient toutes[réf. nécessaire].

Classe SL et problème d'accessibilité dans un graphe non orienté

Lewis et Christos Papadimitriou ont défini en 1982 la variante "symétrique" de L : la classe SL (pour symmetric log-space en anglais). La définition originale[réf. nécessaire] utilise la notion de machine de Turing symétrique au lieu des machines de Turing déterministes classiques. De manière équivalente, SL est la classe des problèmes décidés par une machine de Turing non-déterministe en espace logarithmique, avec la contrainte de symétrie suivante :

  • Si la machine peut effectuer une transition d'une configuration A vers une configuration B, alors la machine peut aussi effectuer une transition de la configuration B vers la configuration A.

Ainsi, la classe SL est entre L et NL[réf. nécessaire]. Lewis et Papadimitriou montrèrent que le problème d'accessibilité dans un graphe non orienté est SL-complet (pour les réductions logarithmiques). Ce problème d'accessibilité prend en entrée un graphe non orienté, un sommet s et un sommet t et détermine s'il existe un chemin d'un sommet donné s à un sommet donné t (à noter que la version du problème d’accessibilité pour les graphes orientés est NL-complète).

En 2004, Omer Reingold montre que le problème d'accessibilité dans un graphe non orienté est décidé en espace logarithmique sur une machine déterministe, et donc que L=SL[6],[7]. La démonstration de Reingold utilise la notion de graphes expanseurs. Ce résultat lui a valu le prix Gödel en 2009.

Notes et références

  1. Garey et Johnson 1979, p. 177.
  2. a et b Sipser 1997, Definition 8.12, p. 295.
  3. Michael Sipser, Introduction to the Theory of Computation, International Thomson Publishing, , 396 p. (ISBN 0-534-94728-X, lire en ligne), p. 349, Example 8.18
  4. (en) Dexter C. Kozen, Theory of Computation, Homework 3. Ex. 1. p. 277
  5. Michael Sipser, Introduction to the Theory of Computation, International Thomson Publishing, , 396 p. (ISBN 0-534-94728-X, lire en ligne), p. 359, Ex. 8.20
  6. Omer Reingold, Salil Vadhan et Avi Wigderson, « Entropy waves, the zig-zag graph product, and new constant-degree expanders », Annals of Mathematics, vol. 155, no 1,‎ , p. 157–187 (DOI 10.2307/3062153, JSTOR 3062153, MR 1888797, lire en ligne)
  7. Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, no 4,‎ , p. 1–24 (lire en ligne)

Bibliographie

Liens externes

Read other articles:

For other uses, see Nabagram (disambiguation). Census Town in West Bengal, IndiaNabgramCensus TownNabgramLocation in West Bengal, IndiaShow map of West BengalNabgramNabgram (India)Show map of IndiaCoordinates: 23°40′43″N 87°14′41″E / 23.678565°N 87.244724°E / 23.678565; 87.244724Country IndiaStateWest BengalDistrictPaschim BardhamanArea • Total4.51 km2 (1.74 sq mi)Population (2011) • Total4,626 • ...

Voce principale: Parabole di Gesù. La parabola del seminatore in un'icona ortodossa, Cluj, Romania. La parabola del seminatore è una parabola di Gesù raccontata nei tre vangeli sinottici (Matteo 13,1-23[1], Marco 4,1-20[2] e Luca 8,4-15[3]) e nel Vangelo di Tommaso (Tommaso 9). Indice 1 Testo 1.1 Vangeli canonici 1.2 Vangeli apocrifi 2 Note 3 Voci correlate 4 Altri progetti Testo Pieter Bruegel il Vecchio, Paesaggio con la parabola del seminatore, 1557 Vangeli canon...

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字(Microsoftコードページ932(はしご高))が含まれています(詳細)。 Tama Art University 多摩美術大学 ラテン語: 北緯35度36分43.15秒 東経139度21分1.79秒 / 北緯35.6119861度 東経139.3504972度 / 35.6119861; 139.3504972座標: 北緯35度36分43.15秒 東経139度21分1.79秒 / 北緯35.6119861度 東経139.3504972

French chemist Joseph Louis ProustBornJoseph Louis Proust(1754-09-26)26 September 1754Angers, FranceDied5 July 1826(1826-07-05) (aged 71)Angers, FranceOccupationChemist Joseph Louis Proust (26 September 1754 – 5 July 1826) was a French chemist. He was best known for his discovery of the law of definite proportions in 1794, stating that chemical compounds always combine in constant proportions.[1] Life Joseph L. Proust was born on September 26, 1754, in Angers, France. His fathe...

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يوليو 2014) حاجب بن المفضل الأزدي معلومات شخصية الحياة العملية المهنة مُحَدِّث  تعديل مصدري - تعديل   حاجب بن المُفضل الأزدي إمام وفقيه وعالم من رواة الحديث، عاش في ا

City of Indian WellsCityBatas kota terlihat dari Palm Desert, CaliforniaJulukan: I.W.Lokasi di Riverside County dan negara bagian CaliforniaCity of Indian WellsLokasi di Amerika SerikatKoordinat: 33°43′07″N 116°18′30″W / 33.71861°N 116.30833°W / 33.71861; -116.30833Koordinat: 33°43′07″N 116°18′30″W / 33.71861°N 116.30833°W / 33.71861; -116.30833[1]NegaraAmerika SerikatNegara bagianCaliforniaCountyRiversideBer...

Kapal patroli adalah kapal angkatan laut yang relatif kecil yang umumnya dirancang untuk pertahanan pantai, perlindungan perbatasan, penegakan hukum imigrasi, tugas pencarian dan penyelamatan. Sudah banyak desain untuk kapal patroli. Mereka dapat dioperasikan oleh angkatan laut suatu negara, penjaga pantai, kepolisian atau bea cukai dan mungkin ditujukan untuk lingkungan laut (air biru) atau muara (air hijau) atau sungai (air coklat). Mereka biasanya ditemukan terlibat dalam berbagai peran pe...

Mark Indelicato (2008) Mark Indelicato (* 16. Juli 1994 in Philadelphia, Pennsylvania) ist ein US-amerikanischer Schauspieler und Sänger. Er wurde durch seine Rolle in der ABC-Comedy-Serie Ugly Betty bekannt. Biografie Mark Indelicato lebt derzeit in New York City und studiert an der Professional Performing Art School. Zusätzlich nimmt er Gesangsunterricht an der Dupree School of Music in Linwood in New Jersey. Als Achtjähriger begann er seine Schauspielkarriere im Philadelphia’s Walnut ...

Mountain in Western Australia Not to be confused with Mount Cook. Mount CookeMount CookeHighest pointElevation582 m (1,909 ft)Prominence582 m (1,909 ft)Coordinates32°25′26″S 116°18′45″E / 32.42389°S 116.31250°E / -32.42389; 116.31250GeographyMount CookeLocation in Western Australia LocationWestern AustraliaParent rangeDarling Range Mount Cooke, near the Western Australia town of Jarrahdale, is one of the highest points on the Darlin...

クリフォード・D・シマックClifford D. Simak誕生 (1904-08-03) 1904年8月3日 アメリカ合衆国 ウィスコンシン州ミルビル死没 1988年4月25日(1988-04-25)(83歳) アメリカ合衆国 ミネソタ州ミネアポリス職業 ジャーナリスト、作家ジャンル SF、ファンタジー、ポピュラー・サイエンス ウィキポータル 文学テンプレートを表示 クリフォード・ドナルド・シマック(Clifford Donald Simak, 1904年...

JumapoloKecamatanPeta lokasi Kecamatan JumapoloNegara IndonesiaProvinsiJawa TengahKabupatenKaranganyarPopulasi • Total45,264 (2.003) jiwaKode Kemendagri33.13.03 Kode BPS3313030 Luas55,67 km²Desa/kelurahan- Jumapolo adalah sebuah kecamatan di Kabupaten Karanganyar, Jawa Tengah. Kelurahan/desa Bakalan Giriwondo Jatirejo Jumantoro Jumapolo Kadipiro Karangbangun Kedawung Kwangsan Lemahbang Paseban Ploso Pendidikan Lembaga pendidikan formal di Kecamatan Jumapolo, antara lain: SD/...

Part of a series on theCulture of India Society Indians Folklore History Languages Holidays Religion Arts and literature Art Architecture Cinema Comics Dance Festivals Literature Poetry Music Painting Sculpture Theatre Others Cuisine Media Newspapers Radio Television Sports Traditional Video games Fashion Mythology Hindu Vedic Meitei Buddhist Folklore Symbols Flag State Emblem Anthem Miss India World Heritage Sites Monuments Organizations Ministry of Culture Ministry of Tourism Tourism Museum...

Musée d'État d'Art égyptien de MunichNouveau bâtiment du musée, depuis 2010.Informations généralesType Musée archéologique, musée national (d)Ouverture 1966Gestionnaire BavièreSite web aegyptisches-museum-muenchenCollectionsCollections Égypte antiqueNombre d'objets 8 000 piècesLocalisationPays  AllemagneCommune MunichAdresse Meiserstraße 1080333 MünchenCoordonnées 48° 08′ 31″ N, 11° 34′ 43″ Emodifier - modifier le code - m...

1986 Indian filmSayam SandhyaPoster designed by Gayathri AshokanDirected byJoshiyWritten byDennis JosephScreenplay byDennis JosephProduced byThiruppathi ChettiyarStarringMammoottyGeethaMonishaSuresh GopiCinematographyVipin DasEdited byK. SankunniMusic byShyamProductioncompanyEvershineDistributed byEvershineRelease date 11 November 1986 (1986-11-11) Running time126 minCountryIndiaLanguageMalayalam Sayam Sandhya is a 1986 Indian Malayalam-language film, directed by Joshiy and pro...

7º Reggimento alpiniStemma 7º Reggimento alpini Descrizione generaleAttiva1º agosto 1887 - oggi Nazione Regno d'Italia Italia Servizio Regio esercito Esercito Italiano TipoFanteria RuoloTruppe da montagna ComandoCaserma Salsa D'Angelo - Belluno MottoAd excelsa tendo Sempre più in alto Battaglie/guerrePrima guerra mondialeSeconda Guerra Mondiale Anniversari23 aprile Ricorrenza della battaglia sul fronte greco-albanese Decorazioni Parte diBrigata alpina Julia Reparti dipendenti comando...

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2016. Perdebatan agama terhadap novel Harry Potter sebagian besar bersumber dari penegasan bahwa novel Harry Potter mengandung subyek-subyek ilmu gaib atau ilmu setan. Penentangan ini datang dari berbagai aliran dalam Agama Abrahamik, beserta beberapa anggot...

Чжу Юлан朱由榔 6-й император эпохи Южная Мин Дата рождения 1623[1] Место рождения Пекин, империя Мин Дата смерти 1662[1] Место смерти Куньмин, Юньнань[d], империя Цин Время царствования 18 ноября 1646 — июнь 1662 Предшественник Чжу Юйюэ Варианты имени Посмертное имя 應天推道敏...

Artery of the neck It has been suggested that this article should be split into a new article titled dorsal scapular artery. (discuss) (June 2022) Transverse cervical arterySuperficial dissection of the right side of the neck, showing the carotid and subclavian arteries (transverse cervical artery is labeled, branching from the thyrocervical trunk)Superficial and deep branches from the transverse cervical arteryDetailsSourceThyrocervical trunkBranchesSuperficial branch Dorsal scapular artery ...

American entrepreneur Patent drawing of the C. L. Best autotractor from 1915 Clarence Leo Best (April 21, 1878 – September 22, 1951, San Francisco, California), usually known as C. L. Best, was an American manufacturing executive.[1] C. L. Best founded the C. L. Best Gas Traction Company in 1910 (later the C. L. Best Tractor Company) then merged his company with Holt Manufacturing Company to form Caterpillar Tractor Company in 1925.[1] C. L. Best was chairman of the boar...

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أغسطس 2018) Archdiocese Baghdad Archdioecesis Bagdathensis Latinorum Latin Church in BaghdadLatin Church in Baghdad الموقع البلد  العراق مطران Immediately subject to the Holy See معلومات الطقوس Latin Rite القيادة الحالية البابا فرنسي...