P NP and NP complete clarfication?

this is an answer I found on stack overflow

"NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time.

This means that if someone gives us an instance of the problem and a certificate (sometimes called a witness) to the answer being yes, we can check that it is correct in polynomial time." -jason

My question is who is the "we" that checks to see if the soloution is correct in polynomial time? Is it a program or does it literally mean a human sitting down and working it out on paper?

This probably a dumb question but please bare with me.

---

In the classical definition, it is a Turing machine. I believe it has been shown that the computers we use today are more-or-less the same to Turing machines in the complexity theory sense (polynomial time on one is polynomial time on the other), see: https://en.wikipedia.org/wiki/Turing_machine#Comparison_with_real_machines

链接地址: http://www.djcxy.com/p/40006.html

上一篇: O八岁？

下一篇: P NP和NP完全分类？