P (計算複雑性理論)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/12/30 05:42 UTC 版)
計算量理論における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であるかどうかは未解決である。まとめると次のような関係がある:
一覧・
カテゴリ
「P (計算複雑性理論)」の例文・使い方・用例・文例
- 米国のCongressは英国のParliamentに相当する
- LP盤
- 辞書でPHの項を引いてごらん
- また、明日は休みを取ると思うので、その場合はあなたにPutnam自動車のLyle氏に朝一番で電話をかけて、11:00 の訪問の予定を延期してもらいたいです。
- 家庭用品小売業のPatio社は昨日、住宅設計と建設事業へ参入することを発表した。
- Patio社は、外国で作られた家庭用品や家具、装飾用品を輸入する小さな貿易会社として20 年前に創業した。
- 同社には、都会の環境に田舎の生活を取り入れたいと思う中流階級の都会人の間に数多くの支持者がおり、最高経営責任者のByron Coxによると、「住宅設計や建設は弊社のような企業にとって当然の結果だ。弊社のお客様は、彼らが所有するPatioの商品と調和する建物を求めている」とのことだ。
- Patio初の主要な建設プロジェクトはGolden Bayを見下ろす20戸の分譲マンションになるだろう。
- 今年の1 月まで、「Premiumアイスクリーム」で知られるErnesto Dairyの副社長だったCarla Starkが、4 月20 日付けでHolman Health社の会長に就任することが今日発表された。
- Holman Healthの株主は、StarkがErnestoに行ったのと同じ魔法をかけてくれることを大いに期待していると報じられている。Starkは、Ernestoがグルメアイス市場において驚くべき20%というシェアを獲得することになった「Premiumアイスクリーム」のブランドを作り上げた人物である。
- Colby KentがHeidi Petersに連絡をした理由
- Pennbrook社が販売している商品の種類
- 11月21日にHolyoke Bar and Grillで、Pete Laurenの退職パーティーが開かれることをお知らせします。11 月10 日までにお返事をください。
- 食事は午後6時から7時の間に出され、そのあとでPeteが20 年に及ぶ勤務の中で会社に多大な貢献をしてくれたことを称える短いセレモニーを行います。
- 会社からPeteに記念の盾と退職記念品が贈られますが、素晴らしい指導者であり手本となってくれたPeteに、私たち全員から贈り物をするために寄付を募ります。
- 開会の辞:Dotty Powers(議長)が午後6 時30 分に会議を開始し、新会計係のClaire Hudsonを紹介した。
- ビルの改修:建設委員会のPetit 氏は、裏口のスロープの工事が予定通り1 月10 日に始まると報告した。
- さまざまな事業:Powersさんは、センターの青少年バスケットボールプログラムがBrookville Inquirer の記事内で最近、賞賛されたと知らせた。
- 会議は、Powersさんによって午後7時30分に一時休会とされた。
- 技術部のPhil Powersが、先週後半に異動の辞令を受け、来月末にDunkirk工場へ転勤することになりました。
- P_(計算複雑性理論)のページへのリンク