Is guessing person's name an NP problem example? Say you want to guess someone's name. It is easy to check if their name is "Sarah" since you can ask them. However, if you are guessing from big enough set of names, you might spend eternity until you pick the right one. To me this seems close to NP definition but I have not seen this or similar example anywhere. Could this be a simple explanation of NP or am I wrong here?
Thank you in advance!
 A: P, NP and computational complexity in general is measured in run-time (number of steps) depending on the length of the input. In this case there is no input (except "start guessing") and you will always have to guess the same number of names (all of them). This means that, in fact, the algorithm for guessing a persons name requires a constant amount of time. It always takes the same (worst-case) time, which is the time it takes to ask the person all names that your database knows.
A: This is not an explanation or example of NP. You can guess the correct name from a finite set of $n$ possible names by checking them one at a time. That's a procedure that works in time proportional to $n$. NP problems take time longer than any polynomial expression in $n$, the size of the input.
If you had $n$ names and $n$ people and you had to match each person with their name you might have to try all $n!$ possible matchings. Since $n!$ grows faster than any polynomial in $n$, that's an NP problem.
"Eternity" doesn't enter the discussion.
