NP完全問題をPで解けるアルゴリズムがある(だがその方法で最適解が求まる訳では無い)、とか、Pではあるんだが、O(n^10000) とかだったらどう?