Klasa złożoności

Klasa złożoności – zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej. Najbardziej pospolitą definicją klasy złożoności jest:

Zbiór problemów, które mogą być rozwiązane na maszynie abstrakcyjnej M przy użyciu O(f(n)) zasobu R, gdzie n jest rozmiarem wejścia.

Na przykład klasa P to zbiór problemów decyzyjnych, które można rozwiązać na maszynie Turinga w czasie wielomianowym natomiast klasa NP to zbiór problemów decyzyjnych, które można rozwiązać na niedeterministycznej maszynie Turinga w czasie wielomianowym.

Z kolei klasa NC to zbiór problemów decyzyjnych, które można rozwiązać na równoległej maszynie RAM (maszynie PRAM) w czasie polilogarytmicznym przy użyciu wielomianowej liczby procesorów, a RP to klasa problemów, dla których istnieje probabilistyczna maszyna Turinga działająca w czasie wielomianowym, która zwraca „nie” zawsze, kiedy prawidłową odpowiedzią jest „nie”, i zwraca „tak” (z prawdopodobieństwem, które dla żadnych danych nie spada poniżej pewnej wartości) lub „nie”, kiedy prawidłową odpowiedzią jest „tak”

Ważne klasy złożoności

Wiele ważnych klas złożoności można zdefiniować przez ograniczenie czasu lub miejsca, na które zapotrzebowanie ma algorytm. Należą do nich:

Klasa złożoności Model obliczeń Ograniczenie zasobów
DTIME(f(n)) Deterministyczna maszyna Turinga Czas f(n)
P Deterministyczna maszyna Turinga Czas poly(n)
EXPTIME Deterministyczna maszyna Turinga Czas 2poly(n)
NTIME(f(n)) Niedeterministyczna maszyna Turinga Czas f(n)
NP Niedeterministyczna maszyna Turinga Czas poly(n)
NEXPTIME Niedeterministyczna maszyna Turinga Czas 2poly(n)
DSPACE(f(n)) Deterministyczna maszyna Turinga Miejsce f(n)
L Deterministyczna maszyna Turinga Miejsce O(log n)
PSPACE Deterministyczna maszyna Turinga Miejsce poly(n)
EXPSPACE Deterministyczna maszyna Turinga Miejsce 2poly(n)
NSPACE(f(n)) Niedeterministyczna maszyna Turinga Miejsce f(n)
NL Niedeterministyczna maszyna Turinga Miejsce O(log n)
NPSPACE Niedeterministyczna maszyna Turinga Miejsce poly(n)
NEXPSPACE Niedeterministyczna maszyna Turinga Miejsce 2poly(n)

Z twierdzenia Savitcha wynika, że PSPACE = NPSPACE i EXPSPACE = NEXPSPACE.

Klasa NP

Do tej klasy należą wszystkie problemy decyzyjne, które rozwiązuje niedeterministyczny algorytm wielomianowy (ang. non-deterministic polynomial).

Niedeterministyczny algorytm to taki, który zawiera instrukcję: choice. Działa ona w sposób losowy, a mianowicie zwraca losowo 0 bądź 1. Tak więc można powiedzieć, że instrukcja choice odgaduje rozwiązanie. Algorytm przerywa działanie, jeżeli odgadnięte rozwiązanie będzie prawidłowe i zwraca wartość success.

Przykładem problemu klasy NP jest pytanie „czy dana liczba jest złożona”. Algorytm niedeterministyczny dla tego problemu odgaduje kolejne bity dzielnika danej liczby. Kolejnym krokiem jest sprawdzenie, czy otrzymany w sposób niedeterministyczny dzielnik faktycznie dzieli daną liczbę.

Klasa Co-NP

Do tej klasy co-NP należą wszystkie problemy, których rozwiązania negatywne, razem z odpowiednim certyfikatem można potwierdzić w czasie wielomianowym.

Jeśli problem X należy do NP, to problem NIE-X należy do Co-NP.

Przykładowym problemem klasy Co-NP może być pytanie „czy dana liczba jest pierwsza”. Rozwiązanie negatywne, którego certyfikatem jest dzielnik, może być łatwo sprawdzone.

Zobacz też

Ważne klasy złożoności
Uważane za wykonalne
Podejrzewane o niewykonalność
Uważane za niewykonalne
Hierarchie klas
Rodziny klas

Read other articles:

Rubin Carter

Untuk pemain American Football dengan nama yang sama, lihat Rubin Carter (pemain American football). Rubin CarterRubin Carter pada 2011 di Bunker Hill Community CollegeStatistikNama panggilanHurricaneDinilai padaKelas ringanTinggi567 ft 7 in (173 m)KebangsaanKanadaLahir(1937-05-06)6 Mei 1937Clifton, New Jersey, ASMeninggal20 April 2014(2014-04-20) (umur 76)Toronto, Ontario, KanadaSikapOrtodoksCatatan tinjuTotal perkelahian40Menang27Menang oleh KO19Kalah12Imbang1Tanpa konte...

 

Sengkang (kota)

Pusat Kota Sengkang Salo Lompo (Sungai Lompo) di Sengkang Kota Sengkang adalah ibu kota Kabupaten Wajo merupakan salah satu kota kecil yang terletak di Provinsi Sulawesi Selatan dan berada di antara 3039’ – 4016’ Lintang Selatan dan 119053’ – 120027’ Bujur Timur. Luas wilayah kota Sengkang secara keseluruhan adalah 38,27 km2 yang meliputi satu kecamatan yaitu Kecamatan Tempe atau terdiri dari 16 kelurahan. Iklim Kota Sengkang memiliki iklim hutan hujan tropis (Af) dengan curah huj...

 

Andrew Tate

Artikel atau sebagian dari artikel ini mungkin diterjemahkan dari Andrew Tate di en.wikipedia.org. Isinya masih belum akurat, karena bagian yang diterjemahkan masih perlu diperhalus dan disempurnakan. Jika Anda menguasai bahasa aslinya, harap pertimbangkan untuk menelusuri referensinya dan menyempurnakan terjemahan ini. Anda juga dapat ikut bergotong royong pada ProyekWiki Perbaikan Terjemahan. (Pesan ini dapat dihapus jika terjemahan dirasa sudah cukup tepat. Lihat pula: panduan penerjemahan...

Gletang

Wikispecies mempunyai informasi mengenai Gletang. Gletang Gletang di Majalengka Klasifikasi ilmiah Kerajaan: Plantae (tanpa takson): Angiospermae (tanpa takson): Eudikotil (tanpa takson): Asteridae Ordo: Asterales Famili: Asteraceae Tribus: Heliantheae Genus: Tridax Spesies: T. procumbens Nama binomial Tridax procumbensL. Gletang (Tridax procumbens) adalah sejenis tumbuhan, kebanyakan ditemukan liar sebagai gulma, anggota suku Asteraceae. Berasal dari Amerika tropis, gletang biasa dijum...

 

2023 Newcastle 500

2023 Newcastle 500Event InformationRound 1 of 12 in the 2023 Supercars ChampionshipDate10–12 March 2023LocationNewcastle East, New South WalesVenueNewcastle Street CircuitResultsRace 1Distance 95 laps 250.895 kmPole position Brodie KosteckiErebus Motorsport 1:11.3217Winner Cameron WatersTickford Racing 1:58:33.2312Race 2Distance 89 laps 235.049 kmPole position David ReynoldsGrove Racing 1:12.0813Winner Shane van GisbergenTriple Eight Race Engineering 2:11:50.4825 The 2023 Newcastle 500 (co...

 

The Italian (film 1915)

The ItalianPamflet kontemporer untuk film tersebutSutradaraReginald BarkerProduserThomas H. InceDitulis olehThomas H. InceC. Gardner SullivanPemeranGeorge BebanClara WilliamsPenata musikVictor Schertzinger (tak disebutkan)SinematograferJoseph H. AugustPerusahaanproduksiNew York Motion Picture Corp.DistributorParamount PicturesTanggal rilis 1 Januari 1915 (1915-01-01) Durasi78 menitNegaraAmerika SerikatBahasaAntarjudul Inggris George Beban dalam The Italian The Italian The Italian a...

I'm Still Here (Juliana Kanyomozi song)

2017 single by Juliana KanyomoziI'm Still HereSingle by Juliana Kanyomozifrom the album Bits and Pieces ReleasedMarch 30, 2017RecordedMichael Fingerz, (South Africa)Genre R&B reggae Length3:16LabelMasters MusicSongwriter(s)Esther NabaasaProducer(s)Michael FingerzJuliana Kanyomozi singles chronology Woman (2015) I'm Still Here (2017) Right Here (2017) Music videoI'm Still Here on YouTube I'm Still Here is an R&B-reggae single by Ugandan singer and actress Juliana Kanyomozi. It was ...

 

1956 United States Senate election in Arizona

1956 United States Senate election in Arizona ← 1950 November 6, 1956 1962 →   Nominee Carl Hayden Ross F. Jones Party Democratic Republican Popular vote 170,816 107,447 Percentage 61.39% 38.61% County resultsHayden:      50–60%      60–70%      70–80%      80–90% U.S. senator before election Carl Hayden Democratic Elected U.S. Senator Carl Hayden Democr...

 

Malmö University

Malmö UniversityMalmö universitetMottoDär mångfald gör skillnad TypePublicEstablished1998 / 2018Vice ChancellorProf. Kerstin ThamAdministrative staff2,200 total (2021)[1]Students12,700 (FTE, 2021)[2] 260 doctoral students (2021)LocationMalmö, Scania, SwedenCampusUrbanWebsitewww.mau.se/en Library of Malmö University Malmö University (Swedish: Malmö universitet) is a public university located in Malmö, Sweden.[3] With more than 24,000 students and about 1,600 e...

Ranveer Ching Returns

Ranveer Ching ReturnsPosterSutradaraRohit ShettyProduserRanveer Singh George CameronDitulis olehRajesh NarasimhanPemeranRanveer SinghRajesh AnandanTamannaahPenata musikShankar–Ehsaan–LoyPenyuntingBunty NagiDistributorCapital FoodTanggal rilis19 Agustus 2016Durasi5 menitNegaraIndiaBahasaHindi Ranveer Ching Returns adalah sebuah film pendek berbahasa Hindi India tahun 2016 garapan Rohit Shetty.[1] Film tersebut dibintangi oleh Ranveer Singh dan Tamannaah dalam peran-peran utam...

 

Министерство природных ресурсов и экологии Российской Федерации

Министерство природных ресурсов и экологии Российской Федерациисокращённо: Минприроды России Общая информация Страна  Россия Юрисдикция Россия Дата создания 12 мая 2008 Предшественники Министерство природных ресурсов Российской Федерации (1996—1998)Министерство охраны...

 

Pangeran Petros dari Yunani dan Denmark

Pangeran PetrosPangeran Petros tahun 1964Kelahiran(1908-12-03)3 Desember 1908Paris, PrancisKematian15 Oktober 1980(1980-10-15) (umur 71)London, InggrisPemakaman5 September 1981Lille Bernstorff, DenmarkWangsaSchleswig-Holstein-Sonderburg-GlücksburgAyahPangeran George dari Yunani dan DenmarkIbuPutri Marie BonapartePasanganIrina Aleksandrovna Ovtchinnikova ​ ​(m. 1939)​ Pangeran Petros dari Yunani dan Denmark (Yunani: Πρίγκιψ Πέτρος τη�...

Outgrow

OUTGROWAlbum studio karya BoADirilis15 Februari 2006Direkam2005-2006GenrePopDurasi? Labelavex traxProduserLee Soo ManKronologi BoA Girls on Top(2005)Girls on Top2005 OUTGROW(2006) MADE IN TWENTY (20)(2007)MADE IN TWENTY (20)2007 OUTGROW adalah album Jepang original ke-4 BoA. Di dalam album ini terdapat singel DO THE MOTION, make a secret, 抱きしめる (Dakishimeru), dan Everlasting. Di dalam album ini juga terdapat lagu First snow dari singel digital spesial BoA, Merry Christmas from B...

 

Anggika Bölsterli

Anggika BölsterliS.I.Kom.LahirAnggika Sri Bölsterli21 Juni 1995 (umur 28)Jakarta, IndonesiaAlmamaterInstitut Komunikasi dan Bisnis LSPRPekerjaanPemeranmodelTahun aktif2013—sekarangTanda tangan Anggika Sri Bölsterli (lahir 21 Juni 1995) adalah pemeran dan model Indonesia. Ia dikenal luas berkat perannya dalam serial Putri Duyung. Kehidupan awal Anggika lahir dengan nama Anggika Sri Bölsterli pada 21 Juni 1995 di Jakarta, Indonesia.[1] Ia merupakan anak pertama dari dua...

 

Mollie Burke

American politician For the Canadian YouTube personality and motivational speaker, see Molly Burke. Mollie BurkeMember of the Vermont House of RepresentativesIncumbentAssumed office 2009Preceded byDaryl Pillsbury (Windham-2-2)ConstituencyWindham-2-2 (2009-2011) Windham-3-2 (2011-present) Personal detailsPolitical partyVermont ProgressiveOther politicalaffiliationsDemocraticSpousePeter GouldChildren3EducationMarymount Manhattan College (BA) Goddard College (MFA) Mollie S. Burke is an Ameri...

Global Mall Taoyuan A19

Shopping mall in Taoyuan City, TaiwanGlobal Mall Taoyuan A19環球購物中心桃園A19LocationNo. 352, Section 2, Gaotie South Road, Zhongli District, Taoyuan City, TaiwanCoordinates25°00′08″N 121°12′09″E / 25.002122835966095°N 121.2024422975567°E / 25.002122835966095; 121.2024422975567Opening dateSeptember 30, 2021Total retail floor area24,000 m2 (260,000 sq ft)No. of floors7 floors above ground 1 floor below groundPublic transit accessTaoy...

 

Cotignola

Questa voce o sezione sull'argomento centri abitati dell'Emilia-Romagna non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Cotignolacomune Cotignola – Veduta LocalizzazioneStato Italia Regione Emilia-Romagna Provincia Ravenna AmministrazioneSindacoFederico Settembrini (PD) dal 10-06-2024 TerritorioCoordinate44°23′N 11°56′E44...

 

Pinhole Cave Man

Upper Paleolithic engraving of a human figure The rib bone, with the carving at the bottom Pin Hole Cave The Pinhole Cave Man or Pin Hole Cave Man is the common name for an engraving of a human figure on a woolly rhinoceros rib bone dating to the Upper Paleolithic that is now in the British Museum (cataloged as Palart 854). In the 1920s, a woolly rhinoceros rib (Coelodonta antiquitatis) that was broken at both ends was found in Pin Hole Cave, Creswell Crags, Derbyshire, England. Description T...

Knight

Honorary title awarded for service to a church or state Knights redirects here. For the Roman social class also known as knights, see Equites. For other uses, see Knight (disambiguation) and Knights (disambiguation). A 14th-century depiction of the 13th-century German knight Hartmann von Aue, from the Codex Manesse Part of a series onImperial, royal, noble,gentry and chivalric ranks in Europe Emperor, Empress dowager Tsar, Tsarina High king, High queen King consort dowager Queen regnant conso...

 

羅馬陸軍

  此条目页的主題是古罗马的陆军。关于古罗马陆军和海军的总体介绍，請見「古罗马军事」。 古羅馬軍事 前753年−476年 结构史 陆军 陆军单位与职阶 装饰与惩罚（英语：Roman military decorations and punishments） 军团（英语：List of Roman legions） 辅军（英语：Auxilia） 将军（英语：List of Roman generals） 海军 舰队 海军司令 战役史 战争与战役（英语：List of Roman wars and battles） ...