P (Komplexitätsklasse)

In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, die alle Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der „praktisch lösbaren“ Probleme betrachtet.

Eine Verallgemeinerung von P ist die Klasse NP. Die Probleme aus NP sind zwar ebenfalls in Polynomialzeit entscheidbar, jedoch wird hierfür ein nicht realisierbares, nämlich nichtdeterministisches Maschinenmodell eingesetzt. P ist sicher eine Teilmenge von NP. Es gehört jedoch zu den wichtigsten ungelösten Fragen der theoretischen Informatik, ob P = NP gilt (siehe auch P-NP-Problem).

P ist unter Komplementbildung abgeschlossen.

Formale Definition

Notation:

  • ist die Menge der natürlichen Zahlen mit Null.
  • ist das Alphabet einer formalen Sprache, das heißt jedes Wort ist eine binäre Zeichenfolge bestehend aus und .
  • bezeichnet die Menge aller binären Wörter der Länge .
  • bezeichnet die (abzählbare) Menge aller endlich langen binären Wörter.

Ein Entscheidungsproblem kann nun als formale Sprache dargestellt werden. Jede Probleminstanz wird als Binärstring in ausgedrückt, und enthält genau die Strings, die eine Instanz darstellen, auf die die richtige Antwort „ja“ lautet.

Ein Entscheidungsproblem ist effizient-lösbar, falls ein Algorithmus in Polynomialzeit existiert, so dass für jedes gilt

Dann ist die Klasse der effizient-lösbaren Entscheidungsprobleme, das heißt[1]

Erläuterungen

Ein Algorithmus kann als deterministische Turing-Maschine aufgefasst werden.

Wir haben ein paar Vereinfachungen vorgenommen. Eigentlich meinen wir das Entscheidungsproblem von , aber häufig identifiziert man mit seinem Entscheidungsproblem. Auch den Begriff des Algorithmus haben wir vereinfacht, da korrekterweise nur die dazugehörige Funktion berechnet, wobei Fehler bedeutet (es ging etwas schief), mit der das Problem gelöst wird. Wir haben mit identifiziert aber auf den Endzustand verzichtet.

Beziehung zu anderen Komplexitätsklassen

Die folgenden Beziehungen sind bekannt:

LNLLOGCFLNC ⊆ P ⊆ NPPSPACE = NPSPACE ⊆ EXPTIMENEXPTIMEEXPSPACE = NEXPSPACE
LOGCFL PSPACE EXPSPACE
P EXPTIME

P-Vollständigkeit

Ein Entscheidungsproblem heißt P-vollständig genau dann, wenn es in der Komplexitätsklasse P liegt und wenn jedes Problem in P durch eine Berechnung mit logarithmischem Platzverbrauch auf reduziert werden kann, das heißt, wenn jede dieser Reduktionen in der Komplexitätsklasse L liegt (siehe auch: Vollständigkeit in der Komplexitätstheorie).

Ein bekanntes P-vollständiges Problem ist das Circuit-Value-Problem, bei dem bestimmt werden soll, ob das Ergebnis eines Booleschen Schaltkreises bei gegebener Eingabe einer gegebenen Ausgabe entspricht. Diese Probleme gehören zu den schwersten, noch effizient lösbaren Problemen aus der Komplexitätsklasse P. P-vollständige Probleme sind (momentan) schwer zu parallelisieren.

Bekannte Probleme in P

Sehr viele Probleme liegen in P, was im Allgemeinen nicht besonders wahrgenommen wird; in der Regel kennt man dann auch einen geeigneten Algorithmus (so das Sortierungsproblem mit z. B. Quicksort, Laufzeit usw.).

P-vollständige Probleme

Einzelnachweise

  1. Oded Goldreich: P, NP, and NP-Completeness: The Basics of Computational Complexity. Hrsg.: Cambridge University Press. 2010, ISBN 978-0-521-19248-4 (englisch).

Read other articles:

Bielsk PodlaskiPasar dan balai kota bersejarah Lambang kebesaranKoordinat: 52°46′N 23°12′E / 52.767°N 23.200°E / 52.767; 23.200Koordinat: 52°46′N 23°12′E / 52.767°N 23.200°E / 52.767; 23.200Negara PolandiaVoivodeshipPodlaskiePowiatBielskGminaBielsk Podlaski (gmina perkotaan)Didirikan12th centuryHak kota1495Pemerintahan • Wali kotaJarosław BorowskiLuas • Kota26,88 km2 (1,038 sq mi)Popul...

 

 

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Kerajaan Buol – berita · surat kabar · buku · cendekiawan · JSTOR Kerajaan Buol adalah kerajaan Suku Buol yang terletak di Kabupaten Buol. Sejarah Sejarah Buol mulai dikenal secara teratur sejak zaman pe...

 

 

Sampul Majalah Rolling Stone Indonesia Edisi #56 Desember 2009 150 Lagu Indonesia Terbaik adalah sebuah daftar yang disusun oleh majalah Rolling Stone Indonesia yang memuat lagu-lagu Indonesia terbaik sepanjang masa. Daftar ini dipublikasikan dalam Majalah Rolling Stone Indonesia edisi #56 terbitan Desember 2009.[1] Daftar lengkap # Lagu Artis Tahun Genre 1 Bongkar Swami 1989 Rock 2 Kebyar Kebyar Gombloh 1979 Rock 3 Badai Pasti Berlalu Berlian Hutauruk 1977 Soul 4 Bis Sekolah Koes Ber...

العلاقات السيراليونية الهندوراسية سيراليون هندوراس   سيراليون   هندوراس تعديل مصدري - تعديل   العلاقات السيراليونية الهندوراسية هي العلاقات الثنائية التي تجمع بين سيراليون وهندوراس.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية ل�...

 

 

Jean Informasi pribadiNama lengkap Jean Raphael Vanderlei MoreiraTanggal lahir 24 Juni 1986 (umur 37)Tempat lahir Campo Grande, BrasilTinggi 1,70 m (5 ft 7 in)Posisi bermain Gelandang bertahanInformasi klubKlub saat ini FluminenseNomor 7Karier junior2001–2002 Operário-MS2002–2005 São PauloKarier senior*Tahun Tim Tampil (Gol)2005–2012 São Paulo 114 (7)2006 → América (dipinjamkan) 2007 → Marília (dipinjamkan) 2008 → Penafiel (dipinjamkan) 2012 → Fluminens...

 

 

Ogun merupakan sebuah negara bagian di Nigeria. Letaknya di bagian baratdaya. Ibu kotanya ialah Abeokuta. Didirikan pada tahun 1976. Negara bagian ini memiliki luas wilayah 16.762 km². Dengan memiliki jumlah penduduk sebanyak 4.054.272 jiwa (2005). Pembagian administrasi Abeokuta North Abeokuta South Ado-Odo/Otta Yewa North Yewa South Ewekoro Ifo ljebu East ljebu North ljebu NorthEast Ijebu Ode Ikenne lmekoAfon lpokia ObafemiOwode Odogbolu Odeda Ogun Waterside Remo North Sagamu lbsNegara ba...

Bamileke dancers perform in Batié, West Province. Dance in Cameroon is an integral part of the tradition, religion, and socialising of the country's people. Cameroon has more than 200 traditional dances, each associated with a different event or situation. Colonial authorities and Christian missionaries discouraged native dances as threats to security and pagan holdovers. However, after Cameroon's independence, the government recognised traditional dance as part of the nation's culture and m...

 

 

NWA Worlds Heavyweight ChampionshipSabuk NWA Worlds Heavyweight Championship saat ini (1973–1986, 1994–saat ini)InformasiJuara saat iniTyrusTanggal dimenangkan12 November 2022Tanggal dibentuk14 Juli 1948PromotorNWANama lain NWA World Heavyweight Championship (1948–2016)[1] StatistikPemegang pertamaOrville BrownPemegang terbanyakRic Flair (9 kali)[2]Pemegang terlamaLou Thesz(2,300 kali)Pemegang tersingkatShane Douglas (<1 hari)Pemegang tertuaTim Storm (51 tahun, 1...

 

 

Basketball team (1970–1978) 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: Buffalo Braves – news · newspapers · books · scholar · JSTOR (March 2013) (Learn how and when to remove this message) Buffalo BravesConferenceEasternDivisionAtlanticFounded1970HistoryBuffalo Braves1970–1978San Diego Clippers1978�...

سفارة اليابان في ماليزيا اليابان ماليزيا   الإحداثيات 3°09′10″N 101°43′20″E / 3.152725°N 101.72234166667°E / 3.152725; 101.72234166667   البلد ماليزيا  المكان كوالالمبور  الاختصاص ماليزيا  الموقع الالكتروني الموقع الرسمي،  والموقع الرسمي  تعديل مصدري - تعديل   سفارة ا�...

 

 

Football derby between AEK Athens and PAOK Double-headed eagles derbyNative nameΝτέρμπι των Δικέφαλων Αετών (Greek)LocationNea Filadelfeia – Thessaloniki,GreeceTeamsAEK AthensPAOKFirst meeting8 March 1931Panhellenic ChampionshipAEK Athens 1–1 PAOKLatest meeting28th April 2024Super LeaguePAOK 3–2 AEK AthensNext meetingTBDStadiumsAgia Sophia Stadium (AEK Athens)Toumba Stadium (PAOK)StatisticsMost winsAEK Athens (83)Top scorerKostas Nestoridis (17)Largest victoryPAO...

 

 

Medieval principality in south-east Europe ZetaЗета (Serbian)Zeta (Serbian)Zeta (Albanian)1356–1421 Coat of arms Map of Zeta in the second half of the 14th centuryCapitalUlcinj, Shkodra[1]Common languagesOld Serbian (Old Slavic)Albanian (Gheg)Religion Orthodox ChristianityCatholicismGovernmentFeudal monarchyHistorical eraMedieval• Established 1356• Unification with the Serbian Despotate 1421 Preceded by Succeeded by Serbian Empire Serbian Despot...

International LGBT-affirming Protestant Christian denomination Metropolitan Community ChurchClassificationProtestantOrientationMainlinePolityCongregationalistModeratorCecilia EgglestonRegionWorldwide (divided into regions with congregations in 37 countries)FounderTroy PerryOrigin1968 Los Angeles, California, USCongregations222Official websitewww.mccchurch.org The Metropolitan Community Church (MCC), also known as the Universal Fellowship of Metropolitan Community Churches (UFMCC), is an inter...

 

 

Sound in New York City Eastchester Bay - to the left of City Island. New City Island Causeway Bridge over Eastchester Bay. Eastchester Bay is a sound between City Island and the mainland Bronx in New York City, New York.[1] Technically, it is not a bay, since it is open to larger bodies of water at both ends. The northern end connects via a narrow channel to Pelham Bay (which is also really a sound, since it, in turn, opens onto Long Island Sound). The Hutchinson River empties into Ea...

 

 

Révolution belge Épisode des journées de septembre 1830, Gustave Wappers (1834), musées royaux des Beaux-Arts de Belgique. Informations générales Date 25 août – 4 octobre 1830(1 mois et 9 jours) Lieu Royaume uni des Pays-BasGrand-duché de Luxembourg Issue Les principales puissances européennes reconnaissent l'indépendance de facto des provinces belges qui quittent le royaume uni des Pays-Bas. Belligérants  Royaume uni des Pays-Bas  Royaume de BelgiqueCorps fr...

「アッコちゃん」はこの項目へ転送されています。その他の用法については「アッコ (曖昧さ回避)」をご覧ください。 『ひみつのアッコちゃん』は、赤塚不二夫による日本の少女漫画である。1960年代から2010年代に至るまでたびたびテレビアニメ化され、人気を呼んだ。また、テレビドラマや実写映画も製作されている。東映魔女っ子シリーズである。 内容 なんでも�...

 

 

1989–1991 unification process of Germany with its full sovereignty returned For the unification of most German states in the 1800s, see Unification of Germany. Reunification of GermanyPart of the Revolutions of 1989 and the end of the Cold WarGermans stand on top of the Wall in front of the Brandenburg Gate in the days before the Wall was torn down.Native name Deutsche WiedervereinigungDie WendeDate9 November 1989 – 15 March 1991 (1989-11-09 – 199...

 

 

Questa voce o sezione sull'argomento società calcistiche portoghesi 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. Caldas Sport ClubeCalcio Segni distintiviUniformi di gara Casa Trasferta Colori sociali Bianco, nero Dati societariCittàCaldas da Rainha Nazione Portogallo ConfederazioneUEFA Federazione FPF CampionatoTerceira Liga Fondazione1916 Pre...

English footballer Jay Simpson Warming up for Philadelphia Union in 2017Personal informationFull name Jay-Alistaire Frederick Simpson[1]Date of birth (1988-12-01) 1 December 1988 (age 35)[2]Place of birth Enfield, EnglandHeight 5 ft 11 in (1.80 m)[3]Position(s) ForwardYouth career1996–1997 Norwich City1997–2007 ArsenalSenior career*Years Team Apps (Gls)2007–2010 Arsenal 0 (0)2007–2008 → Millwall (loan) 41 (6)2009 → West Bromwich Albion (...

 

 

Questa voce sugli argomenti allenatori di pallacanestro statunitensi e cestisti statunitensi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti dei progetti di riferimento 1, 2. Stacey KingNazionalità Stati Uniti Altezza211 cm Peso104 kg Pallacanestro RuoloCentroAllenatore Termine carriera1999 - giocatore2003 - allenatore CarrieraGiovanili Lawton High School1985-1989 Oklahoma Sooners114 (2.008) Squadre di club 1989-1994...