この記事では、数値を含む判定問題に関係する 強 NP 完全性（強 NP 困難性）、弱 NP 完全性（弱 NP 困難性）、擬多項式時間アルゴリズム、弱多項式時間アルゴリズム、強多項式時間アルゴリズム について、次の論文の内容に沿って紹介する。 [1] M. R. Garey …

問題. 面の数 3次元ユークリッド空間中に 2 つの平面 と がある。 実数列 と が与えられる。平面 に頂点の内角が原点から見て反時計周り順にそれぞれ となるように凸多角形を構成して、それら2 つの凸多角形を含む 個の頂点からなる凸多面体の面の数としてあ…

大昔（2016年11月22日）に書いた 記事 が読めなくなっていたので移植しました。 1. 概要 これは Competitive Programming （その2） Advent Calendar 2016 - Adventar の22日目の記事です．今年のACM-ICPC 2016アジア地区つくば大会のK問題で組合せゲーム理…