平成30年度 第6回 Q&A - イベント - 国立情報学研究所 / National Institute of Informatics

第6回 2018年12月11日（火） 計算の理論と現実 －難しいはずの計算が実はいとも？簡単に－ 岩田 陽一 平成30年度 第6回市民講座 講演当日に頂いたご質問への回答（全33件） ※回答が可能な質問のみ掲載しています。 多項式時間、指数時間は具体的にどのように使われているか。本講演の中での多項式時間の位置付け、指数時間の位置付け、どのように測定/算出するのか、の説明を具体的にお願いしたい。 どんな長さnの入力に対しても、T(n)という計算時間でアルゴリズムが動作することを証明できたとします。T(n)が多項式関数であればnに対する多項式時間、指数関数であれば指数時間と呼びます。アルゴリズムから自動的に導かれるものではなく、計算時間を証明する作業が必要になります。 帰着について再度説明をお願いいたします。 問題Aの入力を問題Bの入力に変換し、それに対する問題Bの答えを問題Aの答えに変換する