このサイトはお使いのブラウザでは正常に動作しません。Google Chromeなど、別のブラウザを使用してください。
ある問題がP問題かどうかの証明
ある問題がクラスPに属するかどうか証明したい時に、何か典型的な証明方法などはありますか？例えば、 nのk乗を求める問題はP問題である。（それぞれの乗算は単位時間でできるものする）
という証明問題があったとき、この問題をO(log n)で解けるアルゴリズムを提示したら、それで証明できていることになるでしょうか？
このサイトはお使いのブラウザでは正常に動作しません。Google Chromeなど、別のブラウザを使用してください。