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?
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 &quot;easy&quot; (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.)