0

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.

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

Community
  • 1
  • 1
Squaddy
  • 11
  • 2
  • Possible duplicate of [What are the differences between NP, NP-Complete and NP-Hard?](http://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard) – RussS Dec 01 '15 at 23:49
  • No that's not what I'm asking. I refer to that one of the answers to that question in my question written above... – Squaddy Dec 01 '15 at 23:52
  • In the context of algorithms, there is no difference between a human and a computer program (unless it is a quantum computer of course!!). The only important thing is the number of **actions**; whether performed by a human or a program. In fact, the difference between these two lies in their **speed** of performing the **actions** and the complexity theory talks about the **number** of actions but not the **speed** of them. – AliVar Feb 10 '16 at 20:22

1 Answers1

0

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

TheGreatContini
  • 6,429
  • 2
  • 27
  • 37