Định lý cấp bậc thời gian

Trong lý thuyết độ phức tạp tính toán, các định lý cấp bậc thời gian là các mệnh đề quan trọng về tính toán trong thời gian giới hạn trên máy Turing. Nói một cách đơn giản, các định lý này cho thấy với nhiều thời gian hơn, máy Turing có thể giải được nhiều bài toán hơn. Ví dụ, có bài toán có thể giải trong thời gian n2 nhưng không thể giải trong thời gian n.

Định lý cấp bậc thời gian cho máy Turing đơn định nhiều băng được chứng minh bởi Richard Stearns và Juris Hartmanis năm 1965.[1] Một năm sau, chứng minh được cải tiến sau khi F.C. Hennie và Richard Stearns nâng cao được hiệu quả của máy Turing vạn năng.[2] Định lý cấp bậc thời gian cho máy Turing đơn định khẳng định rằng với mọi hàm tính được trong giới hạn thời gian f(n),

Định lý cấp bậc thời gian cho máy Turing không đơn định được chứng minh đầu tiên bởi Stephen Cook năm 1972.[3] Nó được cải tiến thành dạng hiện nay bởi một chứng minh phức tạp của Joel Seiferas, Michael Fischer, and Albert Meyer năm 1978.[4] Cuối cùng năm 1983, Stanislav Žác đã chứng minh được cùng kết quả đó với một chứng minh đơn giản được sử dụng trong giảng dạy hiện nay.[5] Định lý cấp bậc thời gian cho máy Turing không đơn định khẳng định rằng nếu g(n) là một hàm tính được trong giới hạn thời gian, và f(n+1) = o(g(n)), thì

.

Các định lý tương tự cho bộ nhớ là các định lý cấp bậc bộ nhớ. Hiện vẫn chưa có định lý tương tự cho các lớp độ phức tạp xác suất với giới hạn thời gian trừ phi các lớp đó có trợ giúp.[6]

Ghi chú

  1. ^ Hartmanis, J.; Stearns, R. E. (ngày 1 tháng 5 năm 1965). “On the computational complexity of algorithms”. Transactions of the American Mathematical Society. American Mathematical Society. 117: 285–306. doi:10.2307/1994208. ISSN 0002-9947. JSTOR 1994208. MR 0170805. Đã định rõ hơn một tham số trong |first1= và |first= (trợ giúp)
  2. ^ Hennie, F. C.; Stearns, R. E. (1966). “Two-Tape Simulation of Multitape Turing Machines”. J. ACM. New York, NY, USA: ACM. 13 (4): 533–546. doi:10.1145/321356.321362. ISSN 0004-5411.
  3. ^ Cook, Stephen A. (1972). “A hierarchy for nondeterministic time complexity”. Proceedings of the fourth annual ACM symposium on Theory of computing. STOC '72. Denver, Colorado, United States: ACM. tr. 187–192. doi:10.1145/800152.804913.
  4. ^ Seiferas, Joel I.; Fischer, Michael J.; Meyer, Albert R. (1978). “Separating Nondeterministic Time Complexity Classes”. J. ACM. New York, NY, USA: ACM. 25 (1): 146–167. doi:10.1145/322047.322061. ISSN 0004-5411.
  5. ^ Stanislav, Žác (1983). “A Turing machine time hierarchy”. Theoretical Computer Science. Elsevier Science B.V. 26 (3): 327–333. doi:10.1016/0304-3975(83)90015-4.
  6. ^ Fortnow, L.; Santhanam, R. (2004). “Hierarchy Theorems for Probabilistic Polynomial Time”: 316. doi:10.1109/FOCS.2004.33. Chú thích journal cần |journal= (trợ giúp)

Tham khảo

Read other articles:

List of chancellors of Germany

Top left: Otto von Bismarck was the first chancellor of Germany with the creation of the North German Confederation and later the German Empire.Top right: Konrad Adenauer was the first chancellor of the Federal Republic of Germany.Bottom left: Helmut Kohl was chancellor during the period of German reunification in 1990.Bottom right: Angela Merkel was the first female chancellor of Germany. The chancellor of Germany[1] is the political leader of Germany and the head of the federal gov...

 

Daftar kecamatan dan kelurahan di Kabupaten Buton Utara

Peta Kabupaten Buton Utara di Sulawesi Tenggara Berikut adalah daftar kecamatan dan kelurahan di Kabupaten Buton Utara, Provinsi Sulawesi Tenggara, Indonesia. Kabupaten Buton Utara terdiri dari 6 kecamatan, 12 kelurahan dan 78 desa dengan luas wilayah 1.864,91 km² dan jumlah penduduk sebesar 62.197 jiwa (2017) dengan sebaran penduduk 33 jiwa/km².[1][2] Daftar kecamatan dan kelurahan di Kabupaten Buton Utara, adalah sebagai berikut: Kode Kemendagri Kecamatan Jumlah Kelurahan ...

 

Daftar rumah sakit di Afrika

Lihat pula: Daftar rumah sakit Rumah sakit Princess Marina, Gaborone, Botswana Rumah sakit N'Gaoundere, Cameroon Rumah sakit Addis Ababa Fistula, Ethiopia Rumah sakit The Solar Hospital, Tangiers Rumah sakit Bombo, Tanzania Berikut adalah daftar rumah sakit untuk setiap negara di Afrika. Negara berdaulat Pada tahun 2018, Nigeria menjadi negara yang memiliki jumlah rumah sakit terbesar di sub-Sahara Afrika, dengan 879. Negara lain di kawasan ini dengan jumlah rumah sakit yang besar termasuk Re...

Dancing mania

Medieval social phenomena This article is about the social phenomenon sometimes formerly called St. Vitus' dance. For the infection resulting in jerking movements more often called by that name, see Sydenham's chorea. Dancing mania on a pilgrimage to the church at Sint-Jans-Molenbeek, a 1642 engraving by Hendrick Hondius after a 1564 drawing by Pieter Brueghel the Elder Dancing mania (also known as dancing plague, choreomania, St. John's Dance, tarantism and St. Vitus' Dance) was a social phe...

 

Kent County, Maryland

Kent County, MarylandPengadilan Kent County di Chestertown BenderaSealLokasi di negara bagian MarylandLokasi negara bagian Maryland di Amerika SerikatDidirikan1642Asal namaKentSeatChestertowntown terbesarChestertownWilayah • Keseluruhan41.431 sq mi (107.306 km2) • Daratan27.943 sq mi (72.372 km2) • Perairan13.487 sq mi (34.931 km2), 32.55%Populasi • (2010)20.197 • Kepadatan72/sq mi (2...

 

Sepulveda Pass

Mountain pass in Los Angeles County, California, United States Sepulveda PassPaseo de SépulvedaI-405 in the Sepulveda PassElevation1,130 ft (344 m)Traversed by I-405LocationLos Angeles, California, United StatesRangeSanta Monica MountainsCoordinates34°07′38″N 118°28′30″W / 34.12712°N 118.47489°W / 34.12712; -118.47489 Sepulveda Pass (elevation 1,130 feet (344 m)) is a low mountain pass through the Santa Monica Mountains in Los Angeles. It is named aft...

Vitaliy Buts

Cet article est une ébauche concernant un coureur cycliste ukrainien. Vous pouvez partager vos connaissances en l’améliorant (comment ?). Pour plus d’informations, voyez le projet cyclisme. Vitaliy ButsVitaliy Buts à l’arrivée de la 5e étape du Critérium du Dauphiné 2010 à Grenoble.InformationsNom court Виталий БуцNaissance 24 octobre 1986 (37 ans)MykolaïvNationalité ukrainienneÉquipe actuelle Sakarya BBÉquipes amateurs 2006Feralpi2007-2008Pagnoncel...

 

Gustavsbergs IF

Ice hockey team in Gustavsberg, SwedenGustavsbergs IFCityGustavsberg, SwedenLeagueAllsvenskanFounded1906; 118 years ago (1906)Home arenaEkvallen Gustavsbergs IF wears red playing bandy. Gustavsbergs Idrottsförening, Gustavsbergs IF, is a multi-sport club in Värmdö Municipality in Sweden, founded in 1906.[1] The bandy team of the club has regularly been playing in Allsvenskan, the second level league of bandy in Sweden, since the inauguration of the modern Allsvens...

 

Level of support for evolution

Variation in support for the theory of evolution For the scientific evidence supporting evolution, see Evidence of common descent. Part of a series onEvolutionary biologyDarwin's finches by John Gould Index Introduction Main Outline Glossary Evidence History Processes and outcomes Population genetics Variation Diversity Mutation Natural selection Adaptation Polymorphism Genetic drift Gene flow Speciation Adaptive radiation Co-operation Coevolution Coextinction Divergence Convergence Parallel ...

2021

Cette page concerne l'année 2021 du calendrier grégorien. Chronologies De haut en bas et de gauche à droite : chute de Kaboul, coup d'État au Soudan, obstruction du canal de Suez, James Webb, coup d'État en Birmanie, assaut du Capitole, Ingenuity, Tianhe, tempête en Amérique du Nord/crise énergétique au Texas, séisme en Haïti, Jeux olympiques d'été, effondrement d'un immeuble de Surfside, canicule dans l'Ouest de l'Amérique du Nord, inondations en Europe, assassinat de Jov...

 

1895 United Kingdom general election

1895 United Kingdom general election ← 1892 13 July – 7 August 1895 (1895-07-13 – 1895-08-07) 1900 → ← outgoing memberselected members →All 670 seats in the House of Commons336 seats needed for a majorityTurnout78.4%   First party Second party Third party   Leader Marquess of Salisbury Earl of Rosebery John Dillon Party Conservative and Liberal Unionist Liberal Irish National Federation Leader since ...

 

The Daily Wire

American news and opinion website The Daily WireType of siteNews, opinion, and mediaHeadquartersNashville, Tennessee, U.S.OwnerBentkey Ventures, LLCCreated byBen ShapiroJeremy BoreingKey peopleBen Shapiro (editor emeritus)Jeremy Boreing (co-CEO)Caleb Robinson (co-CEO)John Bickley (editor-in-chief)Employees115 (full-time)[1]SubsidiariesBentkeyURLdailywire.comLaunchedSeptember 21, 2015; 8 years ago (2015-09-21)Current statusActive This article is part of...

コルク

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: コルク – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2017年4月） コルクを打ち抜いて作った瓶の栓 コルク（木栓、�...

 

Il testimone (film 1978)

Questa voce sull'argomento film thriller è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Il testimoneAlberto Sordi e Philippe Noiret in una scena del filmTitolo originaleLe Témoin Lingua originalefrancese Paese di produzioneFrancia, Italia Anno1978 Durata106 min Generethriller, drammatico, commedia RegiaJean-Pierre Mocky SoggettoHarrison Judd (romanzo Shadow of a Doubt) SceneggiaturaAugust...

 

Le Superchicche - Il film

Le Superchicche - Il filmProfessore Utonium (a destra) assieme a Dolly, Lolly e Molly in una scena del filmTitolo originaleThe Powerpuff Girls Movie Paese di produzioneStati Uniti d'America Anno2002 Durata75 min Genereanimazione, azione, commedia, fantastico, avventura, drammatico RegiaCraig McCracken SoggettoCraig McCracken SceneggiaturaCraig McCracken, Amy Rogers, Charlie Bean, Lauren Faust, Paul Rudish, Don Shank Doppiatori originali Cathy Cavadini: Lolly (Blossom) Tara...

Bank QNB Indonesia

Bank QNB IndonesiaJenisJasa keuangan/publik (IDX: BKSW)Didirikan1913KantorpusatDistrict 8 SCBD, Jakarta, IndonesiaTokohkunciStewart Donald Hall (Presiden Direktur)PendapatanRp 302 miliar (2018), Rp 421 miliar (2019) Laba bersihRp 14 miliar (2018), Rp 5 miliar (2019) IndukQatar National BankSitus webqnb.co.id Bank QNB Indonesia adalah perusahaan yang bergerak di bidang perbankan. Bank ini didirikan pada tahun 1913 dan berkantor pusat di Jakarta. Sejarah 1913: Khoe Tjin Tek dan Ouw Tjoei Eng me...

 

Wildfires in 2022

Wildfires on multiple continents 2022 wildfire seasonDate(s)January–December 2022Season← 2021 2023 → The 2022 wildfire season involves wildfires on multiple continents. Below is a partial list of articles on wildfires from around the world in the year 2022. Africa 2022 Moroccan wildfires Asia 2022 Kazakh wildfires 2022 Mongolian wildfires 2022 Khyber Pakhtunkhwa wildfires, Pakistan 2022 Siberian wildfires[1] Europe 2022 European and Mediterranean wildfires North Americ...

 

الخالدون المئة (كتاب)

الخالدون المائةغلاف الكتابمعلومات عامةالمؤلف مايكل هارتاللغة الإنجليزيةالعنوان الأصلي The 100: A Ranking of the Most Influential Persons in Historyالنوع الأدبي غير روائي الناشر Citadel; Revised editionتاريخ الإصدار 1978التقديمعدد الصفحات 556القياسات 178x38x254 ممالوزن 1134 غالترجمةالمترجم أنيس منصور (النسخة الأول�...

Blot-Sweyn

Swedish king of disputed historicity The Norsta Runestone (U 861) on the drive of Wik Castle outside Uppsala was probably made by Sweyn and his family, as it mentions two people called Sweyn and Mær (mentioned in the accusative form Møy). It is the only existing mention of a woman named Mær (maiden) besides the mention of Sweyn's sister Mær in Hervarar saga, and it is contemporary with Sweyn.[1] Blot-Sweyn (Swedish: Blot-Sven) was a Swedish king c. 1080,[2] of disputed his...

 

Daniel Adams

Daniel Adams Daniel R. Adams adalah sutradara film berkebangsaan Amerika Serikat. Namanya dikenal melalui penyutradaraan dan penulisan skenario film The Lightkeepers, yang dibintangi oleh Richard Dreyfuss dan Blythe Danner, serta The Golden Boys, yang dibintangi oleh David Carradine, Bruce Dern, Rip Torn, Charles Durning, dan Mariel Hemingway. Adams tumbuh di daerah Boston, menempuh pendidikan di University of Vermont selama dua tahun, dari 1980 sampai dengan 1981, dan juga Harvard Extension ...