  Degree sequence (DS) problems are around for at least hundred twenty years,
and with the advent of network science, more and more complicated, structured
DS problems were invented. Interestingly enough all those problems so far are
computationally easy. It is clear, however, that we will find soon
computationally hard DS problems. In this paper we want to find such hard DS
problems with relatively simple definition.
  For a vertex $v$ in the simple graph $G$ denote $d_i(v)$ the number of
vertices at distance exactly $i$ from $v$. Then $d_1(v)$ is the usual degree of
vertex $v.$ The vector $\mathbf{d}^2(G)=( (d_1(v_1), d_2(v_1)), \ldots,$
$(d_1(v_n), d_2(v_n))$ is the {\bf second order degree sequence} of the graph
$G$. In this note we show that the problem to decide whether a sequence of
natural numbers $((i_1,j_1),\ldots (i_n,j_n))$ is a second order degree
sequence of a simple undirected graph $G$ is strongly NP-complete. Then we will
discuss some further NP-complete DS problems.
