利用者:Nayuta Ito/押韻の定式化

\( \Sigma \)をアルファベットとし、その上の言語\( L \)および\( \Sigma \)の分割\( R \)を一つ定める。

準備

\( R \)の元を\( 0 \)個以上並べたものを韻と呼ぶ。

\( L \)の長さ\( n \)の単語\( l = l_1 l_2 \cdots l_n \)が韻\( r_1 r_2 \cdots r_n \)を持つとは、\( l \)と\( r \)の長さが同じで、かつ\( l_i \in r_i \)が成り立つことである。

任意の単語は唯一つの韻を持つことに注意せよ。

\( L \)の単語\( l \)と\( l' \)が韻を踏むとは、\( l \)と\( l' \)が同じ韻を持つことである。

問題

\( \Sigma \)と\( L \)と\( R \)を固定する。このとき、次の3つの問題を考える。どの問題も答えが存在しないことが考えられ、その場合は解なしが答えになるものとする。

1. \( n \)文字の韻が一つ与えられるので、その韻を持つ\( L \)の単語を一つ答えよ。
2. \( n \)文字の\( L \)の単語が一つ与えられるので、それと韻を踏む別の\( L \)の単語を一つ答えよ。
3. 文字数\( n \)が与えられるので、\( n \)文字の韻を踏む\( L \)の単語を一組答えよ。

1.を原像問題、2.を第二原像問題、3.を衝突問題と呼ぶことにする。

未解決問題

1. \( L \)が正規言語のとき、これらの問題の\( n \)に対してどれだけの計算量を持つか?
2. \( L \)が文脈自由言語のとき、これらの問題の\( n \)に対してどれだけの計算量を持つか?
3. \( L \)が文脈依存言語のとき、これらの問題の\( n \)に対してどれだけの計算量を持つか?
4. これらの問題のうち少なくとも1つをNP完全にするためには、\( L \)にどれだけの自由度が必要か?
5. どの部分の計算量を削ることでラップバトルは成立しているのか?