形式言語・形式文法
■ このスレッドは過去ログ倉庫に格納されています
0020名無しさん@お腹いっぱい。
2007/03/11(日) 11:36:53ID:DE3dwANy0例えば、もしNP完全な言語が一つでもPに含まれることが証明されたら、P=NPになるんですよね?
それで今、文法の言語族がNPに含まれていて、なおかつNP完全な言語を生成できることまで証明されています。
これはこの文法の言語族がNPとイコールになるということではないのでしょうか?
(もしイコールだったら、定理としてそのように書くような気がするんですけど、そういう風には書いていないので疑問に思いました)
■ このスレッドは過去ログ倉庫に格納されています