PolyL

在計算複雜度理論內，PolyL是一個決定性問題的複雜度類， 可以使用決定型圖靈機使用被某個輸入大小的多对数函数(polylogarithmic)函数所限制的空間。換句話說，polyL = DSPACE((log n)O(1))，這裡的 O(1)代表一個常數。

相對於已知包含在P內的L，我們尚且不知道是否polyL是包含於P內，或者反過來。(PolyL已知包含於QP，或說，類多項式時間(Quasi-polynomial time)之內)。 話說回來，我們知道polyL ≠ P，因為(舉例來說) polyL並沒有在多對一對數空間歸約之下的完備問題。[1] 但是P則有這類問題。PolyL沒有對數空間之下的完備問題是因為空間譜系理論(space hierarchy theory)保證了DSPACE((log n)1) ⊊ DSPACE((log n)2) ⊊ DSPACE((log n)3)…等等。如果polyL有完備問題，則這問題必然落在某個DSPACE((log n)k)內(k為某個常數)。這會令PolyL，也就是包含DSPACE((log n)k+1)以上所有空間複雜度內的問題，全部可以歸約為DSPACE((log n)k)，而違背了空間譜系理論。

參考資料

  1. ^ Complexity Zoo: polyL

Read other articles:

Russian ship Dvienadsat Apostolov (1841)

Ship of the line of the Russian Imperial Navy Not to be confused with Russian battleship Dvenadsat Apostolov. A painting of Dvienadsat Apostolov by Ivan Aivazovsky (1878) History Russian Empire NameDvienadsat Apostolov BuilderS. I. Chernyavskiy, Nikolaev Laid down4 October 1838 Launched15 July 1841 Completed1842 FateScuttled at the Siege of Sevastopol, 25 February 1854 General characteristics (as built) Class and type120-gun Dvienadsat Apostolov-class ship of the line Displacement4,790 long t...

 

Pistola

Para otros usos de este término, véase Pistola (desambiguación). Heckler & Koch USP, pistola semiautomática de fabricación alemana. SIG Sauer P226 S Sport Stock, pistola variante hecha de acero inoxidable con cañón pesado y mecanismos de puntería ajustables LPA. Una pistola es un arma de fuego corta diseñada para ser apuntada y disparada con una sola mano, o con dos, se puede utilizar para la caza dependiendo del arma[1]​[2]​ y dispara balas a corto alcance. Desarroll...

 

Venetië (provincie)

De voormalige provincie Venetië (Venezia) was gelegen in de Noord-Italiaanse regio Veneto. Als gevolg van de Wet 142/1990 op de hervorming van de lokale overheidsorganen[1], in werking getreden op 1 januari 2015[2], is de provincie vervangen door de metropolitane stad Venetië. In het noorden grenst de provincie aan de in de regio Friuli-Venezia Giulia gelegen provincie Pordenone, in het oosten de provincies Treviso en Padua en in het zuiden aan de provincie Rovigo. De provin...

Fabrizio Soccorsi

Fabrizio Soccorsi Médico personal del Papa Francisco I 2015-9 de enero de 2021 Información personalNacimiento 2 de febrero de 1942Roma,  ItaliaFallecimiento 9 de enero de 2021 (78 años)Roma, ItaliaCausa de muerte COVID-19Residencia Ciudad del VaticanoNacionalidad ItalianaReligión CatolicismoLengua materna Italiano FamiliaHijos Cristiana (f. 2017)EducaciónEducación catedrático y Doctor en Medicina Educado en Universidad La SapienzaInformación profesionalOcupación Médico, ci...

 

Libya at the 2000 Summer Olympics

Sporting event delegationLibya at the2000 Summer OlympicsIOC codeLBANOCLibyan Olympic CommitteeWebsiteolympic.ly (in Arabic)in SydneyCompetitors3 in 3 sportsFlag bearer Nizar Mohamed NaeeliMedals Gold 0 Silver 0 Bronze 0 Total 0 Summer Olympics appearances (overview)196419681972–1976198019841988199219962000200420082012201620202024 Libya competed at the 2000 Summer Olympics in Sydney, Australia. The country's participation in Sydney marked its sixth appearance at a Summer Olympics ...

 

Командування Повітряних сил США у Європі

Командування Повітряних сил США у Європі United States Air Forces in Europe – Air Forces Africa Емблема Командування Повітряних сил США у ЄвропіЕмблема Командування Повітряних сил США у АфриціНа службі 19 січня 1942 — дониніКраїна  СШАВид ПС СШАТип Головне командування ПС СШАРоль Командув...

Asia (1798 EIC ship)

For other ships with the same name, see Asia (East Indiaman) and Asia (ship). Great Britain NameAsia Owner EIC voyages 1-2:Robert Charnock EIC voyages 4-5:3-5 Henry Bonham BuilderHumble, Liverpool[1] Launched8. December 1798[1] FateWrecked 1809 General characteristics Tons burthen800, or 819[2] or 81960⁄94,[1] or 871[3](bm) Length Overall: 146 ft 1 in (44.5 m) Keel: 118 ft 7+1⁄2 in (36.2 m) Beam36 ft 3+1...

 

Biggs Army Airfield

US Army military airport located on the Fort Bliss military base in El Paso, TX Biggs Army AirfieldUSGS 1996 photo of Biggs Army AirfieldIATA: BIFICAO: KBIFFAA LID: BIFSummaryAirport typeMilitaryOwner United States ArmyLocationFort Bliss, El Paso, TexasBuilt1916In use1916–presentElevation AMSL3,946 ft / 1,203 mCoordinates31°50′56″N 106°22′01″W / 31.849°N 106.367°W / 31.849; -106.367Runways Direction Length Surface ft m 4/22 13,554 4,131 Asp...

 

Laflin & Rand Powder Company

Logotipo / bandeira. A Laflin & Rand Powder Company, foi uma empresa de manufatura Norte americana que fabricava pólvora negra, e mais tarde pólvora sem fumaça, usada nos rifles da infantaria do Exército dos Estados Unidos entre 1896 e 1908, que incluiu o período de desenvolvimento do fuzil Springfield M1903 e sua munição, a .30-06 Springfield.[1][2][3] Ruinas das instalações da Laflin & Rand Powder Company em Nova Iorque. Referências ↑ Sharpe, Philip B. Complete Guide to ...

Solidity

Programming language This article is about the programming language. For the state of matter, see Solid. This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Solidity – news · newspapers · books · scholar · JSTOR (May 2021) (Learn how and when to remove this template message) SolidityThe Solidity language logoParadigmObject-orientedDesigned byGavin Wood...

 

Прессекретар Президента Російської Федерації

Прессекретарпрезидента Російської Федерації Пресс-секретарьпрезидента Российской Федерации Загальна інформаціяКраїна РосіяДата створення 19 липня 1991Штаб-квартира Московський Кремль, Сенатський палацГолова Дмитро ПєсковПідвідомчі органи по указам президента Росій...

 

24 Hrs (film)

2010 film by Aditya Sam Abraham 24 HrsDirected byAditya Sam AbrahamWritten byAditya Sam AbrahamStarringKuldeepManoj K. JayanKomal JhaCinematographyReji V KumarEdited bySooraj E. S.Music bySayyed HishamDistributed byCinevision FilmsRelease date 3 September 2010 (2010-09-03) Running time93 minutesCountryIndiaLanguageMalayalam 24 Hrs[1] is a 2010 Malayalam action thriller film directed by debutant Aditya Sam Abraham.[2] The film stars Komal Jha, Kuldeep, and Manoj ...

Aiyai: Wrathful Soul

2020 Australian filmAiyai: Wrathful SoulFilm posterDirected byIlanthirayan Alan ArumugamScreenplay byIlanthirayan Alan ArumugamCharles BenedictMukund RamananStory byIlanthirayan Alan ArumugamStarringKabir SinghTahlia Jade HoltPennyanne LaceCinematographyDamien BeebeEdited byRoberto MerliniMusic byJason FernandezProductioncompaniesAiyai Pty LtdGVKM Elephant PicturesRelease date 28 February 2020 (2020-02-28) CountryAustraliaLanguageEnglish Aiyai: Wrathful Soul is a 2020 Australia...

 

Seremban District

This article uses bare URLs, which are uninformative and vulnerable to link rot. Please consider converting them to full citations to ensure the article remains verifiable and maintains a consistent citation style. Several templates and tools are available to assist in formatting, such as reFill (documentation) and Citation bot (documentation). (September 2022) (Learn how and when to remove this template message) District in Negeri Sembilan, MalaysiaSeremban DistrictDistrictDaerah SerembanOth...

 

The Daily Telegraph (Australia)

Untuk kegunaan lain The Telegraph, lihat The Telegraph (disambiguasi). Halaman depan The Daily Telegraph tanggal 12 Desember 2005TipeSurat kabar harianFormatTabloidPemilikNews LimitedRedaksiGary LinnellDidirikan1879Pandangan politikTengah-kananPusat2 Holt Street,Surry Hills, NSW, AustraliaSitus webwww.dailytelegraph.news.com.au The Daily Telegraph (sering disebut The Tele) adalah sebuah surat kabar tabloid Australia yang diterbitkan di Sydney, New South Wales dan negara NSW, oleh Nationwide N...

Astana Pro Team

Untuk the women's cycling team, lihat Astana BePink Womens Team. Astana Pro TeamInformasi umumKode UCIASTBasisKazakhstanDidirikan2007 (2007)StatusUCI ProTeamSepedaSpecializedPemegang jabatanManajerAlexander VinokourovRiwayat nama2007– Astana Pro Team 　 Kostum lbs Astana Pro Team (Kode tim UCI: AST) adalah sebuah tim balap sepeda jalan raya yang disponsori oleh Samruk-Kazyna, sebuah koalisi dari perusahaan milik negara dari Kazakhstan dan diberi nama sesuai dengan ibu kotanya yai...

 

Hamlet station

Train station in Hamlet, North Carolina Hamlet, NCGeneral informationLocation2 West Main StreetHamlet, North CarolinaUnited StatesCoordinates34°53′01.7″N 79°41′56.6″W / 34.883806°N 79.699056°W / 34.883806; -79.699056Owned byCity of HamletLine(s)Hamlet Terminal SubdivisionPlatforms1 side platformTracks1ConstructionStructure typeAt-gradeParkingYesAccessibleYesArchitectural styleVictorian Queen AnneOther informationStatusUnstaffedStation codeAmtrak: HAMWebsite...

 

Sonic Rivals

2006 video game 2006 video gameSonic RivalsCover artDeveloper(s)Backbone EntertainmentSega Studio USAPublisher(s)SegaDirector(s)Takashi IizukaProducer(s)Taylor MillerArtist(s)Ryan SlemkoWriter(s)Takashi IizukaComposer(s)Chris RezansonSeriesSonic the HedgehogPlatform(s)PlayStation PortableReleaseNA: November 16, 2006EU: December 1, 2006AU: December 7, 2006Genre(s)Action, racingMode(s)Single-player, multiplayer Sonic Rivals is a 2006 action-racing video game developed by Backbone Entertainment ...

Constantino Pandiani

Italian sculptor Constantino Pandiani (1837–1922) was an Italian sculptor. Pukki in Korkeasaari Zoo, Helsinki. Biography He was a resident of Milan, and born into a family of sculptors and owners of a bronze foundery. Among the many exhibitions he sent works were: 1870 in Parma, a marble bust of Springtime and a marble statue of First Flower. In 1872 Milan, he exhibited Diavoletto-maschera In 1877, in Naples, La Vendemmia; Moses tramples the Crown of the Pharaoh; a putto in marble; and a ma...

 

Leif Garrett

American actor and singer (born 1961) This article is about the singer himself. For his self-titled debut album, see Leif Garrett (album). Leif GarrettGarrett in 2017Background informationBirth nameLeif Per NervikBorn (1961-11-08) November 8, 1961 (age 62)OriginHollywood, California, U.S.GenresPop, disco (early), rock (later)Occupation(s)Actor, singer, television personalityInstrument(s)Vocals, guitarYears active1966–presentLabels20th Century, Atlantic, Scotti Brothers, Tongue and Groo...

 

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