0
$\begingroup$

Here’s the decision problem:

Suppose I have N positive integers encoded in base-2 (as oppose to unary)

Are these integers precisely the integers 1-N in some order?

This is related to the Hamiltonian path problem which is NP-complete

Given a graph with N vertices you can nondeterministically walk a path of length N

If you could decide whether or not the sequence is precisely the integers 1-N in some order then you could decide whether or not the path is Hamiltonian

Hence the decision problem is related to the Hamiltonian path problem

What then is the relationship to NP?

Is it NP hard?

Is it NP complete?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Sounds easy - sort the integers, iterate over and check whether you have 1 to n? Or, slightly slower, iterate over 1 to n and check whether each element is in your input set. Both methods are efficient. $\endgroup$
    – Juho
    Apr 24, 2021 at 18:47
  • $\begingroup$ Or, you could scan the array once, keeping track of which of the elements $1$ to $n$ you've seen. $\endgroup$
    – Yuval Filmus
    Apr 24, 2021 at 19:03

1 Answer 1

Reset to default
2
$\begingroup$

Recognizing that a path is a Hamiltonian path is easy. Finding one in the first place may be hard (the number of candidates is large).

The defining property of problems in NP is that verifying a solution is "easy" (in P). Your problem is one part of verifying a solution of a Hamiltonian path problem. (You also have to verify that the path is a subgraph of the input graph.)

Improve this answer
$\endgroup$

Your Answer

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

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