How to reconcile time complexity terms between problems

Question

The $\mathbf{P}$ vs $\mathbf{NP}$ problem asks whether it’s possible to find an algorithm for an $\mathbf{NP}$ problem that runs with a time complexity of $O(n^k)$. Separately, the Clique decision problem asks whether, given a graph of $n$ vertices and $m$ edges, it’s possible to find a clique of size $k$.

I’ve been playing with various algorithms trying to understand these problems and their time complexity, but the feedback I was getting led me to believe I was misunderstanding something fundamental. So I had two questions whose answers are as follows.

1. Are the two $n$’s and $k$’s above equivalent? No.
   The statement of the $\mathbf{P}$ vs $\mathbf{NP}$ problem is a different context from the statement of any particular problem or an expression of its time complexity. So for any given problem with a time complexity of (for instance) $O(n^k)$, $k$ can be absolutely any constant that isn’t an input to the problem. However, in expressions of time complexity, $n$ is still the complexity of the input. So if our $O(n^k)$ described an algorithm for solving the Traveling Salesman problem, for instnace, $n$ would represent the cities and/or distances used in the solution.

2. What does it mean for something to be “complex/polynomial/factorial/etc. in” some variable $n$ or $k$ or $\dots$? This is basically short for “in terms of” or “with respect to” the input variable.
   This can be most easily explained with an example. The Traveling Salesman problem, for instance, asks what is the most efficient route to visit a certain number of cities, $c$, all at various distances, $d$ from each other. Such a problem with multiple inputs might have an algorithm with a time complexity that requires $O(c^2)$ time to solve. That’s “polynomial in $c$”. But if that “$c^2$” comes from the fact that there are $c \choose d$ routes, then when $d = \lfloor c/2 \rfloor$, the time complexity of the same algorithm could be stated as $O(d!)$, which is “factorial in $d$.”

Answer 1

An algorithm runs in polynomial time if there exists an absolute constant $k$ such that the algorithm halts in at most $O(n^k)$ steps. Here, $n$ is the size of the input.

So for the Clique problem, if a family of graphs has bounded clique size, we can solve the Clique problem for that family in polynomial time. This does not imply that we can solve the Clique problem in general graphs in polynomial time.

Does this clarify?

Edit: The Clique problem is formally defined as the following language:

$$L = \{ \langle G, c \rangle : G \text{ has a clique of size } c \}$$

Now $L$ is NP-complete, and so is unlikely to admit a polynomial time algorithm. That is, we think there does not exist an algorithm $A$ and an absolute constant $k$ such that $A$ can decide whether a pair $\langle G, c \rangle$ belongs to $L$ in time $O(n^{k})$.

Now consider the following subset of $L$:

$$L_{3} = \{ \langle G, 3 \rangle : G \text{ has a clique of size } 3 \}.$$

Now $L_{3}$ belongs to P. You can enumerate all possible $3$-element subsets of the vertices in time $O(n^{3})$. Replace $3$ with your favorite constant, and the same holds.

The difference between $L$ and $L_{3}$ is a bit subtle. Do you see the difference between fixing $3$ and allowing $c$ to be specified as part of the input?