
Title:
1905 What You Know  NP

Description:

And again, that is probably very familiar to you by now.

NP is is the complexity class of all problems that can

that can be solved in polynomial time

or in nondeterministic RAM.

That's what the N here stands for; now you might have found this

quiz rather easy, but actually that you're so familiar with P and NP

I think it's something special,

because I find that not many people actually understand what

P and NP stand for, and what the difference is between the two.

Now if you really want to impress a theoretical computer scientist,

of course you have to be a little bit nit picky.

First of all, P and NP formally are

defined for decision problems,

so here we said all problems, but actually,

if you're very formal, it's only for decision problems,

and the other thing is that

originally, those classes were not defined on the

RAM but rather on a computer model

known as a Turing machine,

named after the computer pioneer, Alan Turing.

Now having a precise definition doesn't really change anything about P and NP

the way that we were talking about it,

but when you get down into the details of these classes,

it might actually matter that you have a Turing machine here

instead of a RAM and that you're talking about decision problems

instead of optimization problems.

But for here, I think it's just fine to think of it as the

complexity class of all problems

that can be solved in polynomial time

on a deterministic or non deterministic RAM.