Given　a　positive　integer　k　and　a　directed　graph　G　with　a　real　number　cost　on　each　edge,　the　k-length　negative　cost　cycle　(k　LNCC)　problem　that　first　emerged　in　deadlock　avoidance　in　synchronized　streaming　computing　network　[14]　is　to　determine　whether　G　contains　a　negative　cost　cycle　of　at　least　k　edges.　The　paper　first　shows　a　related　problem　of　k　LNCC,　namely　the　fixed-point　trail　with　k-length　negative　cost　cycle　(FPT　k　LNCC)　problem　which　is　to　determine　whether　there　exists　a　negative　closed　trail　enrouting　a　given　vertex　as　the　fixed　point　and　containing　only　cycles　with　at　least　k　edges,　is　NP-complete　in　multigraphs　even　when　k=　3　by　reducing　from　the　3SAT　problem.　Then　as　the　main　result,　we　prove　the　NP　-completeness　of　k　LNCC　by　giving　a　more　sophisticated　reduction　from　the　3　Occurrence　3-Satisfiability　(3O3SAT)　problem,　a　known　NP　-complete　special　case　of　3SAT　in　which　a　variable　occurs　at　most　three　times.　The　complexity　result　is　surprising,　since　polynomial　time　algorithms　are　known　for　both　2LNCC　(essentially　no　restriction　on　the　value　of　k)　and　the　k-cycle　problem　with　k　being　fixed　which　is　to　determine　whether　there　exists　a　cycle　of　at　least　length　k　in　a　given　graph.　This　closes　the　open　problem　proposed　by　Li　et　al.　in　[14,　15]　whether　k　LNCC　admits　polynomial-time　algorithms.　©　Springer　International　Publishing　AG　2017.