# Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP?

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?

• 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.
– Juho
Apr 24 at 18:47
• Or, you could scan the array once, keeping track of which of the elements $1$ to $n$ you've seen. Apr 24 at 19:03