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?