形式言語・形式文法
■ このスレッドは過去ログ倉庫に格納されています
0023名無しさん@お腹いっぱい。
2007/03/16(金) 15:01:39ID:HKGVHllY0文法の言語クラス自体は、ある時間(または領域)以内に解けるとか解けないとかそういう意味は含んでいない。
NP-completeなものを1つその文法で記述できたとしても、他のNP-completeなものまで記述できるとは限らない。
一方でPのほうは、DTMで多項式時間内に受理できることを保証するクラス。
NP-completeなものが1つでもPに属するなら、全てのNP-completeな問題も還元によって、DTMで多項式時間内に解けないとおかしい(ほとんどありえないだろうけどね)。
■ このスレッドは過去ログ倉庫に格納されています