矛盾(Contradiction) 恒真式(Tautology) 論理積(Conjunction) 否定論理積(Alternative Denial) 非含意(Material non implication) 含意(Material implication) 命題P(Proposition P) 否定P(Negation of P) 逆非合意(Converse non implication) 逆合意(Conver…

論理結合子

P：入力のサイズの多項式で表せる時間で解決できる問題。 証拠：問題に対する解。 NP：入力のサイズと証拠のサイズの多項式で表せる時間で証拠が解であることを確かめることのできる問題。 NP困難：その問題を多項式時間に解決できるアルゴリズムがあれば、N…

巡回せぇるすまん

関数fがあったときに、 すべての場合において、入力のサイズnに比例して実行時間が変化する場合 実行時間は f(n) = Θ(n) と表される。 入力の中身によってはオーダーに差がでるとき、 これ以上は実行時間が大きくならないオーダーがnであれば f(n) = Ω(n) と…

実行時間のオーダーの表記法