What to consider while proving NP-completeness? Suppose that a problem $P$ is known to be NP-hard.
The input to the problem is a set of $k$ lines in 2D, a set of $n$ points, and $m &lt; n$ pairwise distances among the points.
The goal is to place each point on one of $k$ lines, satisfying the given pairwise distances.
Disclaimer This problem might not be an NP-hard problem, but for the sake of simplicity, suppose that it is.

Since the problem is assumed to be NP-hard, having a polynomial time solution checking algorithm is sufficient to show NP-completeness.

At first sight, it seems trivial
Step 1: check whether the pairwise distances are satisfied [takes $O(m)$ time].
Step 2: check for each point whether the point is on a given line. [takes $O(n*k)$ time].

However, if one of the coordinates has exponentially many bits with respect to the input, then is this considered as a exponential-time checking? Or it is still polynomial-time with respect to the length of the solution?
However, if one of the coordinates has exponentially many bits with respect to the input, then is this considered as a exponential-time checking? Or it is still polynomial-time with respect to the length of the solution?


The length of the solution/certificate must be polynomial in the size of the original instance. Therefore, if the certificate/solution can be exponential in the size of the input (due to the numbers needing exponential representation) then you do not have a valid proof of membership in $NP$. The problem might be $\exists \mathbb{R}$-hard.