適切な複雑性関数

適切な複雑性関数とは、自然数を自然数に写像する関数f であり、以下の条件を満たすものです。

• fは非減少関数である。
• 任意の長さnの入力に対して、O( n + f ( n )) ステップ後に停止し、O( f ( n ))の空間を使用し、f ( n ) 個の連続する空白を出力するk文字列チューリングマシンMが存在する。

fとgが2つの適切な複雑性関数である場合、f  + g、fg、および2f^もまた適切な複雑性関数である。 

同様の概念としては、正直関数、空間構成可能関数、時間構成可能関数などがある。

ミャシュニコフ、アレクセイ；シュピルレイン、ウラジミール；ウシャコフ、ウラジミール（2008）。グループベース暗号。ビルクハウザー。p.  28。ISBN 978-3-7643-8826-3。