SC (複雜度)

在計算複雜度理論內，SC (Steve's Class，以史蒂芬·库克命名)[1]是一個複雜度類，包含了使用圖靈機，在多項式時間(P複雜度類)以及多項式對數空間(PolyL複雜度類) (也就是，O(logk n)空間，k是某個常數)。我們也可以稱呼這個複雜度類為DTISP(poly, polylog)，這裡DTISP代表確定性時間與空間(deterministic time and space)。這裡的SC是P PolyL的嚴格子集，因為對前者，他需要存在一個解決問題的演算法同時滿足多項式時間以及多項式對數空間兩個條件；而對後者這個聯集來說，他只需要兩個各自的演算法，其中一個是多項式時間，另一個是多項式對數空間即可以滿足。

DCFL，這個複雜度類是上下文無關語言的子集，使用確定下推自動機來驗證。DCFL已知是包含在SC內的，由Cook在1979年證明。[2]

RL和BPL是能夠以概率圖靈機在多項式時間和多項式對數空間解決的複雜度類。Nisan在1992年證明了一個較弱的去隨機化，因此可以證明這兩個複雜度類都在SC裡面。[3]換句話說，給出一個多項式對數空間，我們可以用一個確定型的圖靈機來模擬 對數空間的機率演算法。

參考資料

  1. ^ Complexity Zoo: SC
  2. ^ S. A. Cook. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space. Proceedings of ACM STOC'79, pp. 338–345. 1979.
  3. ^ N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.


Read other articles:

Telefónica

Telefónica S.A.JenisSociedad AnónimaKode emitenBMAD: TEFEuronext: TFANYSE: TEFLSE: TDEFWB: TNE5TYO: 9481Templat:BVLTemplat:BCBAIndustriTelekomunikasiPendahuluCompañía Telefónica Nacional de España (CTNE)Didirikan19 April 1924 (1924-04-19) (CTNE)KantorpusatMadrid, SpanyolWilayah operasiSeduniaTokohkunciCésar Alierta (Ketua dan CEO)ProdukJaringan tetap dan telepon genggam, layanan internet, televisi digitalPendapatan € 062,356 milyar (2012)[1]Laba opera...

 

Bill's Gamblin' Hall and Saloon

Bill's Gamblin' Hall and Saloon Fakta dan statistik Alamat 3595 Las Vegas Blvd South Las Vegas, NV 89109Tanggal pembukaan 1979Nama sebelumnya Barbary Coast Hotel and CasinoJenis kasino TanahTema San Francisco 1890-anPemilik Harrah's EntertainmentJumlah kamar 197Luas perjudian 30,000 square feetAcara permanen Hiburan lounge bebasAtraksi menarik Big Elvis, replika Elvis Presley seberat 500 ponRestoran terkenal Drai'sThe Steakhouse at Bill’s The Victorian Ro...

 

Slender-tailed dunnart

Species of marsupial Slender-tailed dunnart Conservation status Least Concern (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Mammalia Infraclass: Marsupialia Order: Dasyuromorphia Family: Dasyuridae Genus: Sminthopsis Species: S. murina Binomial name Sminthopsis murina(Waterhouse, 1838) Slender-tailed dunnart range The slender-tailed dunnart (Sminthopsis murina), also known as the common dunnart in Australia, is a dasyurid...

Two Black Cadillacs

Two Black Cadillacssingolo discograficoScreenshot tratto dal video del branoArtistaCarrie Underwood Pubblicazione18 novembre 2012 Durata4:59 Album di provenienzaBlown Away GenereCountryCountry pop EtichettaArista Nashville ProduttoreMark Bright FormatiDownload digitale CertificazioniDischi di platino1 (RIAA)[1] Carrie Underwood - cronologiaSingolo precedenteBlown Away(2012)Singolo successivoSee You Again(2013) Two Black Cadillacs è un singolo della cantante statunitense Car...

 

Nokia 6822

Nokia 6822 adalah produk telepon genggam yang dirilis oleh perusahaan Nokia. Telepon genggam ini memiliki dimensi 106 x 46 x 21 mm dengan berat 100 gram. Fitur Kamera digital VGA, 640x480 pixels SMS MMS Email Instant Messaging Tombol QWERTY Permainan Radio FM Internet GPRS Inframerah Java MIDP 2.0 Bluetooth Perekam video Lihat pula Daftar produk Nokia Pranala luar informasi di GSM Arena lbsNokiaAnak usaha Nokia Bell Labs Nokia Networks Nokia Technologies Unit lain NGP Capital Nuage Netwo...

 

Dikasteri untuk Para Uskup

Dikasteri untuk Para UskupLambang Takhta SuciPalazzo delle Congregazioni di Piazza Pio XII (di depan Lapangan Santo Petrus) adalah tempat kerja sebagian besar jemaat Kuria RomaInformasi DikasteriDibentuk22 Januari 1588; 436 tahun lalu (1588-01-22)Nomenklatur sebelumnyaKongregasi untuk Pendirian Gereja dan Ketentuan KonsistorialKongregasi untuk Para UskupJenisDikasteriKantor pusatPalazzo delle Congregazioni, Piazza Pio XII, Roma, ItaliaDikasteri eksekutifRobert Francis Prevost, PrefekIlso...

Bács-Bodrog County

County of the Kingdom of Hungary 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: Bács-Bodrog County – news · newspapers · books · scholar · JSTOR (April 2009) (Learn how and when to remove this template message) Bács-Bodrog CountyComitatus Bacsiensis et Bodrogiensis (Latin)Bács-Bodrog vármegye ...

 

List of buildings in Laredo, Texas

The San Agustin CathedralThis is a list of the tallest and largest buildings in Laredo, Texas. Laredo is the county seat and most populated city in Webb County, Texas. The city has over 230,000 residents and there are over 730,000 residents in the Laredo-Nuevo Laredo Metropolitan Area. Tallest buildings Hamilton Hotel Rio Grande Plaza Hotel The Holiday Inn The Laredo Medical Center Walker Plaza Mall del Norte Today a part of the Republic of the Rio Grande's Capitol building is used as a muse...

 

Delta 0100

Delta seri 0100, juga Delta 100, 0300 atau seri 300, adalah sistem peluncuran expendable (sekali pakai) Amerika yang dilakukan meluncurkan orbital antara 1968 dan 1972. Itu adalah anggota keluarga roket Delta, dan yang pertama yang akan ditunjuk menggunakan kode empat digit numerik. Dua varian diterbangkan, individual ditunjuk Delta 0300 dan Delta 0900. Referensi Wade, Mark. Delta. Encyclopedia Astronautica. Diakses tanggal 2009-02-11.  Krebs, Gunter. Thor family. Gunter's Space Page. D...

Écury-le-Repos

Écury-le-ReposcomuneÉcury-le-Repos – Veduta LocalizzazioneStato Francia RegioneGrand Est Dipartimento Marna ArrondissementChâlons-en-Champagne CantoneVertus-Plaine Champenoise TerritorioCoordinate48°48′N 4°02′E / 48.8°N 4.033333°E48.8; 4.033333 (Écury-le-Repos)Coordinate: 48°48′N 4°02′E / 48.8°N 4.033333°E48.8; 4.033333 (Écury-le-Repos) Superficie9,75 km² Abitanti66[1] (2009) Densità6,77 ab./km² Altre informa...

 

José Fajardo

Questa voce sull'argomento calciatori panamensi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. José Fajardo Nazionalità  Panama Altezza 180 cm Peso 67 kg Calcio Ruolo Attaccante Squadra  Universidad Católica CarrieraGiovanili  Indep. La ChorreraSquadre di club1 2018-2020 Indep. La Chorrera26 (10)2021 Nueve de Octubre27 (12)2022-2023 Cusco37 (20)2023 D.C. United7 (...

 

Сибирский горный козёл

Сибирский горный козёл Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:СинапсидыКла�...

1991 NCAA men's volleyball tournament

Football tournament season 1991 NCAA men's volleyball tournamentTournament detailsDatesMay 1991Teams4Final positionsChampionsLong Beach State (1st title)Runner-upUSC (10th title match)Tournament statisticsMatches played4Attendance5,184 (1,296 per match)Best playerBrent Hilliard (Long Beach State)← 19901992 → The 1991 NCAA men's volleyball tournament was the 22nd annual tournament to determine the national champion of NCAA men's collegiate volleyball. The tourn...

 

Jones Point (Virginia)

For other Jones Points, see Jones Point (disambiguation). 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: Jones Point Virginia – news · newspapers · books · scholar · JSTOR (January 2020) (Learn how and when to remove this message) Jones PointThe park on Jones PointLocation within Alexandria, VirginiaLo...

 

Felice Borel

Felice Borel 1930s - FBC JuventusInformasi pribadiNama lengkap Felice Placido Borel IITanggal lahir April 5, 1914Tempat lahir Nizza Monferrato, ItalyTinggi 1,75 m (5 ft 9 in)Posisi bermain ForwardKarier senior*Tahun Tim Tampil (Gol)1932-41 Juventus 206 (118)1941-42 Torino 25 (7)1942-46 Juventus 27 (10)1946-47 Alessandria 1 (0)1948-49 Napoli 1 (0)Tim nasional1933- Italy 3 (1)Kepelatihan1942-1946 Juventus1946-1947 Alessandria1948-1949 Napoli * Penampilan dan gol di klub senior h...

الخدمة العمومية للتشغيل في الجزائر

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يوليو 2021) الخدمة العمومية للتشغيل في الجزائرالخدمة العمومية لتشغيل في الجزائرمعلومات عامةالبلد  الجزائر النوع public employment service (en) المقر الرئيسي الجزائر العاصمة -  ...

 

Romesh Ranganathan

English comedian Not to be confused with Ramesh Ranganathan. Romesh RanganathanRanganathan in October 2013BornJonathan Romesh Ranganathan (1978-03-27) 27 March 1978 (age 46)Crawley, EnglandEducationBirkbeck, University of London (BSc)OccupationsComedianpresenteractorYears active2013–presentSpouseLeesa RanganathanChildren3Websiteromeshranganathan.co.uk Jonathan Romesh Ranganathan (born 27 March 1978) is a British comedian, presenter, and actor. His style of comedy is deadpan and of...

 

Northumberland, Pennsylvania

Borough in Pennsylvania, United StatesNorthumberland, PennsylvaniaBoroughView of NorthumberlandNickname: NorryLocation of Northumberland in Northumberland County, Pennsylvania.NorthumberlandLocation on Northumberland in PennsylvaniaShow map of PennsylvaniaNorthumberlandNorthumberland (the United States)Show map of the United StatesCoordinates: 40°53′38″N 76°47′46″W / 40.89389°N 76.79611°W / 40.89389; -76.79611CountryUnited StatesStatePennsylvaniaCount...

Lago di Cignana

Questa voce sugli argomenti laghi d'Italia e Valle d'Aosta è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Lago di CignanaLac de TsignanazStato Italia Regione Valle d'Aosta ComuneValtournenche Coordinate45°52′52.8″N 7°35′22.25″E45°52′52.8″N, 7°35′22.25″E Altitudine2.149 m s.l.m. DimensioniSuperficie0,72[1] km² Profondità massima50,9[1] ...

 

Клавдии

Клавдиилат. Claudiiлат. gens Claudia Ветви рода Крассы, Инрегиллены Сабины, Пульхры, Центоны, Марцеллы, Нероны, Канины, Юлии-Клавдии и др. Подданство Древний Рим Гражданская деятельность более 30 консулов, 6 диктаторов, 6 Императоров, Децемвиры, Риторы, Цензоры, Преторы, Квесторы...