P (計算複雑性理論)

計算量理論におけるPとは、多項式時間（polynomial time）で解ける判定問題の集合である。

定義

判定問題のうち、ある決定性チューリング機械によって多項式時間で解かれるものの全体をPで表す。

意義

Pはしばしば、「効率的に解ける」問題のクラスとして扱われる。しかしながら、RPやBPPといった乱択で解けるクラスも、Pより大きいかもしれないが「効率的に解ける」と考えることもできる。逆にPに属しても実際には扱うことが困難である問題もある。例えば、入力のサイズnに対してn1000000の時間を必要とする問題も、定義からはPに属する。

Pに属する問題のうち対数領域還元に関して最大なものはP完全であるという。

他の問題クラスとの関係

非決定性チューリング機械によって多項式時間で解かれる判定問題のクラスをNPという。PがNPに含まれることは自明である。多くの研究者がPはNPの真部分集合であると信じているが、証明されていない（P≠NP予想）。

対数領域の決定性チューリング機械で判定可能な問題のクラスであるLはPに含まれるが、L = Pかどうかは未解決である。対数領域の交替性チューリング機械によって解ける問題のクラスALOGSPACEはPに等しい。PはPSPACEの部分集合であるが、P = PSPACEであるかどうかは未解決である。まとめると次のような関係がある:

ここで、EXPTIMEは指数時間で解ける問題のクラスである。PはEXPTIMEの真部分集合であるから、Pよりも右の包含関係のうち少なくとも一つは真部分集合である（実際には上に示された包含がみな真の包含であると広く予想されている）。

関連するクラス

  • クラス NP - 提出された答えの検算がクラス P になる決定問題のクラス。
  • クラス FP - クラス P と類似した概念ではあるが、クラス P とは違い解を出力することができる問題のクラス。
  • クラス RP - 答えが no のときは必ず no で返すが、答えが yes のときはある確率で no と答えることがある乱択算法によって解かれる判定問題のクラス。モンテカルロ法などの手法を計算理論上で解析するために生まれた。
  • 多項式階層
実用的な時間で解けるクラス
実用的な時間で解けないと疑われているクラス
実用的な時間では解けないクラス
クラス階層
クラスの族
一覧記事 一覧・カテゴリ カテゴリ

Read other articles:

Faugli Mawa

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. Faugli MawaDesaFaugli MawaLokasi di Punjab, IndiaTampilkan peta PunjabFaugli MawaFaugli Mawa (India)Tampilkan peta IndiaKoordinat: 31°11′50″N 76°27′49″E / 31.19722°N 76.46361°E / 31.19722; 76.46361Negara IndiaNe...

 

Eva González

Nama ini menggunakan cara penamaan Spanyol: nama keluarga pertama atau paternalnya adalah González dan nama keluarga kedua atau maternalnya adalah Fernández. Eva GonzálezLahirEva Maria González Fernández5 November 1980 (umur 43)Seville, SpainPemenang kontes kecantikanGelarMiss Spanyol 2003Warna rambutCoklatWarna mataHijau Eva María González Fernández (lahir 5 November 1980) adalah seorang aktris, presenter televisi dan pemenang kontes kecantikan yang mewakili Spanyol di kont...

 

Turbo Pascal

Turbo Pascal Layar pembuka Turbo Pascal 4.0 (1987).Tipebahasa pemrograman, Lingkungan pengembangan terpadu dan bahasa pemrograman berorientasi obyek Versi pertama20 November 1983 GenreIntegrated Development EnvironmentKarakteristik teknisSistem operasiDOS, CP/M, CP/M-86 (en), Windows 3.x dan Classic Mac OS Bahasa pemrogramanBahasa rakitan Format berkasDaftarTurbo Pascal Desktop (en), Turbo Pascal configuration (en), Borland Turbo Pascal 5.5 compiled Unit (en), Borland Turbo Pascal 6.0 compile...

Boeing X-37

Reusable robotic spaceplane X-37 The sixth X-37B mission with a Service module placed inside its payload fairing Role Uncrewed spaceplaneType of aircraft National origin United States Manufacturer Boeing First flight 7 April 2006 (first drop test) Introduction 22 April 2010 (first spaceflight) Status In service 6 spaceflights completed 7th spaceflight underway Primary user X-37A: NASA/DARPA X-37B: United States Space Force/​Department of the Air Force Rapid Capabilities Office[...

 

Daisuki (website)

Defunct Japanese anime streaming website DaisukiType of siteVideo streaming serviceDissolved11:59:+09:00, October 31, 2017 (2017-10-31T11:59:+09:00)HeadquartersTokyo, JapanArea servedWorldwideIndustryAnimeVideo on DemandParentAnime Consortium JapanBandai Namco HoldingsURLDaisuki.net (Archived)RegistrationOptionalLaunchedMay 16, 2013; 10 years ago (2013-05-16)Current statusInactive Daisuki (株式会社ダイスキ, Kabushiki-gashia Da...

 

Washington University in St. Louis

Private university in Missouri, US Washington University redirects here. Not to be confused with the University of Washington. It has been suggested that George Warren Brown School of Social Work be merged into this article. (Discuss) Proposed since April 2024. Washington University in St. LouisLatin: Universitas WashingtonianaFormer nameEliot Seminary (1853–1854)Washington Institute (1854–1856)Washington University (1856–1976)MottoPer veritatem vis (Latin)Motto in EnglishStrength ...

Dean Zimmerman (philosopher)

American philosopher Dean ZimmermanAlma materMankato State UniversityBrown UniversityEra21st-century philosophyRegionWestern philosophySchoolAnalytical philosophyInstitutionsRutgers UniversityMain interestsMetaphysicsphilosophy of mindphilosophy of religion Dean W. Zimmerman is an American professor of philosophy at Rutgers University[1] specializing in metaphysics and philosophy of religion. Education and career Zimmerman received his bachelor's degree from Mankato State Univers...

 

Hypoxia (environmental)

Low oxygen conditions or levelsGlobal map of low and declining oxygen levels in the open ocean and coastal waters, 2009.[1] The map indicates coastal sites where anthropogenic nutrients have exacerbated or caused oxygen declines to <2 mg/L (<63 μmol/L) (red dots), as well as ocean oxygen minimum zones at 300 m (blue shaded regions).[2] Part of a series onPollutionAir pollution from a factory Air Air quality index Atmospheric dispersion modeling Chlorofluorocarbon Combus...

 

Человек прямоходящий

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

Aparon

Filipino dessert made from unconsecrated communion wafers AparonTypeWaferPlace of originPhilippines Aparon are Filipino wafers drizzled with caramelized sugar and optionally, sesame seeds. They are uniquely made from unconsecrated hostia (communion wafers). They were first manufactured by a religious order who baked communion wafers for the Catholic Church, but needed a way to make use of extra and discarded wafers.[1][2] See also Christmas wafer Kiping Barquillo References ^ ...

 

The Hotspur

British boys' paper This article is about the comic series. For other uses, see Hotspur. HotspurIssue 1 of Hotspur (1933)Publication informationPublisherD. C. Thomson & Co.Publication date(story paper) 2 September 1933–17 October 1959(comic book) October 1959–January 1981No. of issues1197 (vol. 1)1110 (vol. 2) The Hotspur was a British boys' paper published by D. C. Thomson & Co. From 1933 to 1959, it was a boys' story paper; it was relaunched as a comic in October 1959, initially...

 

Storia della scienza

L'uomo vitruviano di Leonardo da Vinci, un esempio di fusione tra arte e scienza durante il Rinascimento La storia della scienza riguarda le vicende, i personaggi e le scoperte che hanno contribuito al progresso scientifico. Essa ha prodotto quella che oggi è considerata la scienza moderna, ossia un corpo di conoscenze empiricamente controllabile, una comunità di studiosi e una serie di tecniche per investigare l'universo note come metodo scientifico, che si è evoluto a partire dai loro pr...

King of Kotha

2023 Indian Malayalam action thriller film by Abhilash Joshiy King of KothaTheatrical release posterDirected byAbhilash JoshiyWritten byAbhilash N. ChandranProduced byDulquer SalmaanZee StudiosStarringDulquer SalmaanShabeer KallarakkalPrasannaGokul SureshAishwarya LekshmiNyla UshaChemban Vinod JoseNarrated byMohanlalCinematographyNimish RaviEdited byShyam SasidharanMusic bySongs:Jakes BejoyShaan RahmanScore:Jakes BejoyProductioncompaniesWayfarer FilmsZee StudiosRelease date 24 August...

 

Horley railway station

Railway station in Surrey, England Not to be confused with Horsley railway station. Horley HorleyLocation of Horley in SurreyLocationHorleyLocal authorityReigate and BansteadGrid referenceTQ286426Managed bySouthernStation codeHORDfT categoryDNumber of platforms4AccessibleYes[1]Fare zoneDNational Rail annual entry and exit2018–19 0.970 million[2]2019–20 1.010 million[2]2020–21 0.278 million[2]2021–22 0.800 million[2]2022–23 1.034 million[2&...

 

Madurai R. Muralidaran

Madurai R. MuralidaranOccupations Dance Guru (teacher) Composer choreographer dancer playwright director Years active1978–present Kalaimamani Shri Guru Madurai R. Muralidaran is an acclaimed dance Guru (teacher), composer, dancer, choreographer, lyricist, playwright and director best known for his large body of modern compositions for Bharatanatyam dancers and his many elaborate dance musical productions. His works explore the complexities of Bharathanatyam theory and rhythms while rem...

Psyche (album)

1994 studio album by PJ & DuncanPsycheStudio album by PJ & DuncanReleased4 November 1994 20 September 1995 (Japan)Recorded1993–94Genre pop rap teen pop Length43:02LabelTelstar RecordsProducer Nicky Graham Deni Lew Mike Olton PJ & Duncan chronology Psyche(1994) Top Katz(1995) Singles from Psyche Tonight I'm FreeReleased: 6 December 1993 Why Me?Released: 11 April 1994 Let's Get Ready to RhumbleReleased: 11 July 1994 If I Give You My NumberReleased: 26 September 1994 Etern...

 

Alexander Keith Marshall

American politician Alexander Keith MarshallGelatin Photograph of MarshallMember of the U.S. House of Representativesfrom Kentucky's 8th districtIn officeMarch 4, 1855 – March 3, 1857Preceded byJohn C. BreckinridgeSucceeded byJames Brown Clay Personal detailsBorn(1808-02-11)February 11, 1808Buck Pond, Versailles, Kentucky, U.S.DiedApril 28, 1884(1884-04-28) (aged 76)Montreal, Quebec, CanadaResting placeLexington Cemetery, Fayette County, KentuckyPolitical partyAmer...

 

Frederick Rawson

English footballer and religious figure Frederick RawsonPersonal informationFull name Frederick Lawrence RawsonDate of birth (1859-07-27)27 July 1859Place of birth the High SeasDate of death 10 November 1923(1923-11-10) (aged 64)Place of death New York CityPosition(s) WingerYouth career1874–76 Westminster SchoolSenior career*Years Team Apps (Gls)1875–80 Clapham Rovers *Club domestic league appearances and goals Frederick Rawson was a footballer who played in the 1879 FA Cup final, wh...

Nathaniel Davis

American diplomat (1925–2011) For the former U.S. ambassador to Costa Rica and minister to Hungary, see Nathaniel Penistone Davis. For other people named Nathaniel Davis, see Nathaniel Davis (disambiguation). Nathaniel DavisUnited States Ambassador to SwitzerlandIn officeNovember 20, 1976 (1976-11-20) – July 31, 1977 (1977-07-31)PresidentGerald Ford Jimmy CarterPreceded byPeter H. DominickSucceeded byMarvin L. Warner6th Assistant Secretary of State f...

 

Gedung Pabean, Shanghai

Gedung Pabean Shanghai dilihat dari Sungai Huangpu Gedung HSBC (kiri) dan Gedung Pabean Shanghai Gedung Pabean Shanghai atau Gedung Bea Cukai Jiang (Hanzi: 江海關大樓) adalah bangunan delapan lantai di the Bund, Jalan Zhongshan Timur No.13, Shanghai, Tiongkok. Bersama dengan tetangganya Gedung HSBC, Gedung Pabean Shanghai menjadi salah satu simbol the Bund dan Shanghai. Pertama kali dibangun pada tahun 1846, kemudian direnovasi pada tahun 1925-1927 dengan bentuknya yang seperti sekar...