関係ない定義[]
\( \Sigma \)を文字の有限集合とし、\( T \)を\( \Sigma \)上の文字列全体の集合の部分集合とする。
\( \alpha \in T \)に対し、\( |\alpha| \)で\( \alpha \)の長さを表すことにし、\( 1 \leq n \leq |\alpha| \)を満たす自然数\( n \)に対して\( \alpha_n \)で\( \alpha \)の\( n \)文字目を表すことにする。最初の文字は\( 1 \)文字目とみなす。
\( []: T \times \mathbb{N} \rightarrow T \)が線形計算可能であるとは、それが\( O(N) \)で計算可能であることである。正確には、以下のYes-No questionが時間計算量\( O(N) \)で解けることを意味する。
- \( s \in T, N \in \mathbb{N}, a \in \{n \in \mathbb{N} \mid 1 \leq n \leq |\alpha| \}, \sigma \in \Sigma \)が与えられる。\( s[N]_a = \sigma \)であるか?