計算理論などにおける一進法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/06 13:56 UTC 版)
「一進法」の記事における「計算理論などにおける一進法」の解説
一進法には、計算理論において計算量を「人工的に」減らすため、などといった応用がある。例として、自然数の素因数分解問題は入力が二進法で与えられる場合には、入力長 n の多項式時間では実行不可能だと考えられている（素因数分解仮定）。しかし、入力が一進法で与えられるならば、入力長の多項式時間で実行するのは容易である（エラトステネスの篩で十分）。二進法での入力長 n は入力の数 N の対数 log N に比例するが、一進法での入力長は入力の数 N それ自身に比例するからである。 他にもコンピュータ科学などには多くの応用がある。たとえば、チューリングマシンの初歩的な例題などでは、テープ上に数字を並べてそれを位取り記数法で扱うのは相当に煩雑であるが、一進法であれば「右に進んでいって1があれば0に書き換えて、今度は左に進む」といったような手順で簡単に扱うことができる。
※この「計算理論などにおける一進法」の解説は、「一進法」の解説の一部です。
「計算理論などにおける一進法」を含む「一進法」の記事については、「一進法」の概要を参照ください。
ウィキペディア小見出し辞書の「計算理論などにおける一進法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 計算理論などにおける一進法のページへのリンク
