Though for the specific problem P vs. NP, it is vital that the definition of input size be (essentially equivalent to the one) in terms of the number of bits to specify the input.

Anyway, for the OP: most pop-mathematical explanations of **P** vs. **NP** are really explanations of **FP** vs. **FNP**. That’s alright; **P** = **NP** if and only if **FP** = **FNP** (and is equivalent to a million other more and less interesting things as well). But it does tend to confuse the introductory discussions to not keep the notions clear and distinct. Let’s try and spell out what they all amount to:

A predicate (also called a relation) is any sort of yes/no question you might ask with various input slots; e.g. “Is N a prime number”, “Is the number X a nontrivial factor of the number Y”, “Is there a path in the graph G of length D with starting node X and ending node Y”, and so on.

Notation: In general, we use notation like “R(X, Y)” to introduce a relation named R with input slots named X and Y, and then write “R(thing1, thing2)” to mean either YES or NO, according as to the answer to the question R when thing1 is substituted in the X slot and thing2 is substituted in the Y slot. [And similarly for relations with any number of input slots]. If we want to refer to the relation itself, we can use either “R” or “R(X, Y)”, depending on whether we want to emphasize the input slots or not. [This is all just notation, but it makes life easier]

A binary relation is just a relation with two input slots. Let’s suppose we’re interested in a binary relation R(X, Y). There are various associated computational tasks we can ask about.

For example, we might consider the problem “Given X and Y as input, output the yes/no value of R(X, Y)”. This is what we might call the check-problem (or verify-problem) associated with R. R is said to be in **FNP** if there is a computer program which does this, whose running time is running time (measured by number of computational steps) is never more than some fixed polynomial of the size of the input X alone (measured by number of bits to specify X alone).

Or, we might consider the problem “Given an X as input, either output a particular Y such that R(X, Y) = YES or output an error code indicating that there is no such Y”. This is what we might call the search-problem associated with R. R is said to be in **FP** if A) there is a computer program which does this, whose running time is never more than some fixed polynomial of the size of the input X, and B) R is also in **FNP**.

By definition, every binary relation in **FP** is also in **FNP**. However, it’s not known whether the converses hold; that is, it’s not known if condition A) above is redundant. That’s the big question.

What about **P** and **NP**?

A predicate Q(X) with just one input slot is said to be in **NP** if there’s some R(X, Y) in **FNP** such that the answer to Q(X) is always the same as the answer to the question “Does there exist a Y such that R(X, Y) = YES?”. (Note that there may be more than one such R; as long as there’s *any* way to cast Q into this form, then Q is in **NP**)

Finally, a predicate Q(X) with just one input slot is said to be in **P** if there is a computer program which, given an input X, will output the yes/no answer to Q(X) in a running time bounded by some polynomial of X’s size.

It’s easy to see that every predicate in **P** is also in **NP**. However, it’s not known whether the converse holds. That’s the big question. In fact, as I said at the top, it’s the same big question from before; it’s fairly easy to show that **P** = **NP** if and only if **FP** = **FNP**.

How does any of this apply to the problems in the OP? Well, I’ll put that in the next post.