0
$\begingroup$

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 < 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?

$\endgroup$
5
  • $\begingroup$ If the co-ordinates you're referring to are those of the set of $n$ points specified in the input, I don't understand how they could have exponentially many bits with respect to the input since, well, they are part of the input. $\endgroup$
    – mhum
    Oct 24, 2019 at 18:39
  • $\begingroup$ @mhum the ccordinates of the points are a part of the solution, not the input. $\endgroup$
    – padawan
    Oct 24, 2019 at 23:08
  • $\begingroup$ Oh, I guess I was confused by the wording of: "The input to the problem is a set of $k$ lines in 2D, a set of $n$ points, and $m<n$ pairwise distances among the points." which to me sounded like the lines, the points and the distances were all part of the input of the problem. If the points are not part of the input, which things are the actual input? $\endgroup$
    – mhum
    Oct 24, 2019 at 23:21
  • $\begingroup$ the input consists of the lines and some of the pairwise distances. $\endgroup$
    – padawan
    Oct 24, 2019 at 23:23
  • $\begingroup$ Ah, okay. That's much more clear. $\endgroup$
    – mhum
    Oct 24, 2019 at 23:30

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ A solution can be exponential w.r.t. the size of the input, but not necessarily. I mean, instead of having (1,1), I can have (1.000...001, 1) which is exponential, but not forced. Does this count? $\endgroup$
    – padawan
    Oct 24, 2019 at 14:53
  • 1
    $\begingroup$ If $(1,1)$ is also a valid solution then it "counts". You must show that any instance has a polynomial certificate, but this does not rule out that exponential certificates also exist. $\endgroup$ Oct 24, 2019 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.