o(n^2)

計算量って、o(log n)とか、o(exp n)とか、いろいろありますが...

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 な問題な気がする。