Wikiいけめん
217
回編集
差分
ページの作成:「\( \Sigma \)をアルファベットとし、その上の言語\( L \)および\( \Sigma \)の分割\( R \)を一つ定める。 ===準備=== \( R \)の元を\( 0 \)個…」
\( \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つの問題を考える。どの問題も答えが存在しないことが考えられ、その場合は解なしが答えになるものとする。
# \( n \)文字の韻が一つ与えられるので、その韻を持つ\( L \)の単語を一つ答えよ。
# \( n \)文字の\( L \)の単語が一つ与えられるので、それと韻を踏む別の\( L \)の単語を一つ答えよ。
# 文字数\( n \)が与えられるので、\( n \)文字の韻を踏む\( L \)の単語を一組答えよ。
1.を'''原像問題'''、2.を'''第二原像問題'''、3.を'''衝突問題'''と呼ぶことにする。
===未解決問題===
# \( L \)が正規言語のとき、これらの問題の\( n \)に対してどれだけの計算量を持つか?
# \( L \)が文脈自由言語のとき、これらの問題の\( n \)に対してどれだけの計算量を持つか?
# \( L \)が文脈依存言語のとき、これらの問題の\( n \)に対してどれだけの計算量を持つか?
# これらの問題のうち少なくとも1つをNP完全にするためには、\( L \)にどれだけの自由度が必要か?
# どの部分の計算量を削ることでラップバトルは成立しているのか?
===準備===
\( 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つの問題を考える。どの問題も答えが存在しないことが考えられ、その場合は解なしが答えになるものとする。
# \( n \)文字の韻が一つ与えられるので、その韻を持つ\( L \)の単語を一つ答えよ。
# \( n \)文字の\( L \)の単語が一つ与えられるので、それと韻を踏む別の\( L \)の単語を一つ答えよ。
# 文字数\( n \)が与えられるので、\( n \)文字の韻を踏む\( L \)の単語を一組答えよ。
1.を'''原像問題'''、2.を'''第二原像問題'''、3.を'''衝突問題'''と呼ぶことにする。
===未解決問題===
# \( L \)が正規言語のとき、これらの問題の\( n \)に対してどれだけの計算量を持つか?
# \( L \)が文脈自由言語のとき、これらの問題の\( n \)に対してどれだけの計算量を持つか?
# \( L \)が文脈依存言語のとき、これらの問題の\( n \)に対してどれだけの計算量を持つか?
# これらの問題のうち少なくとも1つをNP完全にするためには、\( L \)にどれだけの自由度が必要か?
# どの部分の計算量を削ることでラップバトルは成立しているのか?