o(exp n) は許す。そうでないと、NPは解けないので。命題論理式の証明がNPだから必須。
なんだが、o(n^2)は許せない。許せないです。
唯一実用的な計算量は線形 o(n) だと思う。NPみたいな難しいことやっているなら、ともかく、実用的なものは o(n) で書くべきだろ?
何が許せないかって、o(n)で出来ると知りつつ、手抜きのプログラミングで o(n^2) になる場合。
それでも、n が小さいなら許す。今は、100ぐらいまでバレナイ。o(exp n)は、100でも破綻するが、o(n^2)だと、結構、動く。動くが「遅い」。遅いよ。遅いです。1000越えると、n^2 は、100万なのでごまかせません。
逆に言えば、100 までは、o(n^2)でも別に問題ないってことなんだよな。
自分では、NPよりも、PSPACE を扱っていることが多い。NP!=PSPACE も、証明されてません。P=NP は証明不可能なんだろうと予想してますが、ってことは、ほぼ、P=NPだろうと思ってますが、P==PSPACE はどうでしょう。
命題論式の証明も、入力を真理値表にするとo(n)に落ちるので、(ただし、入力は巨大、
つまり、式のexp) だったりするので、P=NP は、どうも、ill-defined な問題な気がする。
No comments:
Post a Comment