# optimization – Is the problem “find the sequence of \$N\$ numbers between 1 and \$D\$ with least cost”, NP-hard?

Consider sequences $$p=(p_1,dots,p_N)$$ (the order matters) of length $$N$$, where $$p_iin{1,dots,D}$$ for fixed $$D$$. Moreover, consider a cost function $$c:{1,dots,D}^Ntomathbb{R}$$ which comply $$c(q)neq c(p), forall p,qin{1,dots,D}^N$$. The problem is to find $$pin{1,dots,D}^N$$ with least cost $$c(p)$$. I want to show that this problem is NP-hard.

In my opinion, since all costs are different, there is no other way but to check all possible ($$D^N$$) combinations to find the optimum. Should this be enough to conclude that this problem is NP-hard? If so, what is the “formal argument” under this line of reasoning?

Alternatively, is there a standard reference which state that a problem like this is NP-hard? Which other NP-hard problem can be reduced to this one?