多項式時間








多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。


多項式時間のアルゴリズムとは、解くべき問題の入力サイズn{displaystyle n}nに対して、処理時間の上界としてn{displaystyle n}nの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。


たとえばバブルソートの処理時間は要素数n{displaystyle n}nに対して要素の比較・交換を行う回数は高々 12n(n−1){displaystyle {frac {1}{2}}n(n-1)}{frac {1}{2}}n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO(n2){displaystyle O({n^{2}})}{displaystyle O({n^{2}})}と表される。 またクイックソートの期待計算量のオーダーはO(nlog⁡n){displaystyle O(nlog n)}O(nlog n)、最悪計算量のオーダーはO(n2){displaystyle O({n^{2}})}{displaystyle O({n^{2}})}である。




目次






  • 1 定義


    • 1.1 多項式時間アルゴリズム


    • 1.2 多項式時間アルゴリズムが存在する問題とクラスP




  • 2 関連項目





定義


多項式時間アルゴリズムと多項式時間アルゴリズムが存在する問題クラスについて、簡単に記す。



多項式時間アルゴリズム


Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは多項式時間アルゴリズムであるという


ある多項式l(k)があって、任意のkと任意のkビットのデータxに対し、Aにxを入力した時にAが停止するまでのステップ数はl(k)以下である。

なお「多項式時間アルゴリズム」と言った場合、決定的アルゴリズムのみを多項式時間アルゴリズムとして認める場合と、確率的アルゴリズムをも許す場合とがある。



多項式時間アルゴリズムが存在する問題とクラスP


決定的な多項式時間アルゴリズム（上で定義した）で解ける判定問題の集合をクラスPと呼ぶ（判定問題以外の問題はクラスPに含まれないことに注意）。



関連項目



  • 計算量理論

  • 定数時間

  • 指数関数時間

  • 多項式時間変換

  • 凖指数関数時間

  • 時間計算量




Popular posts from this blog

Can a sorcerer learn a 5th-level spell early by creating spell slots using the Font of Magic feature?

Image
28 6 $begingroup$ Per the Font of Magic feature, sorcerer can use Flexible Casting to create 5th-level spell slots at level 7, even though they are not typically available until level 9. You can transform unexpended sorcery points into one spell slot as a bonus action on your turn. The Creating Spell Slots table shows the cost of creating a spell slot of [5th level is 7] If such a sorcerer levels up while still having this 5th-level spell slot, can they choose a 5th-level spell as the spell they gain upon levelling up? The Spellcasting feature states: Additionally, when you gain a level in this class, you can choose one of the sorcerer spells you know and replace it with another spell from the sorcerer spell list, which also must be of a level for which you have spell slots.
Read more

Does disintegrating a polymorphed enemy still kill it after the 2018 errata?

Image
up vote 13 down vote favorite 1 After the 2018 errata, the disintegrate spell description now reads: A creature targeted by this spell must make a Dexterity saving throw. On a failed save, the target takes 10d6 + 40 force damage. The target is disintegrated if this damage leaves it with 0 hit points. If you were to polymorph an enemy into a rat and then disintegrate it, would the enemy be disintegrated or would it just return to its original form? I know that for Druids, it’s not an instant kill anymore, but is this the case for polymorph as well? dnd-5e spells polymorph errata share | improve this question edited 18 hours ago
Read more

A Topological Invariant for $pi_3(U(n))$

Image
3 3 $begingroup$ Recently, I saw a construction of topological invariant for $pi_3(U(n))$ with $ngeq 2$ : $$ N=frac{1}{24pi^2}int_{S^3} d^3x epsilon^{ijk} Tr[(U^{-1}partial_{x_i}U)(U^{-1}partial_{x_j}U)(U^{-1}partial_{x_k}U)] , $$ where $Uin U(n)$ depends on $boldsymbol{x}=(x_1,x_2,x_3)in S^3$ , $epsilon^{ijk}$ is the Levi-Civita symbol, $i,j,k=1,2,3$ , and the duplicated indexes are summed over. It is claimed that $N$ is an integer, but why? Update 02/02/2019 I think I got an argument for $n=2$ . In this case, $U=e^{i varphi} q$ with $qin SU(2)$ . Due to the trace and the Levi-Civita symbol in $N$ , $varphi$ does not contribute to $N$ . As $Tr[q^{dagger}partial_i q]=0$ and $(q^{dagger}partial_i q)^{dagger}=-q^{dagger}partial_i q$ , $q^{dagger}partial_i q$ in geneeral has the form $q^{dagger}partia
Read more