Let　G　be　a　directed　graph　with　an　integral　cost　on　each　edge.　For　a　given　positive　integer　k,　the　k-length　negative　cost　cycle　(kLNCC)　problem　is　to　determine　whether　G　contains　a　negative　cost　cycle　with　at　least　k　edges.　Because　of　its　applications　in　deadlock　avoidance　in　synchronized　streaming　computing　network,　kLNCC　was　first　studied　in　paper　(Li　et　al.　in　Proceedings　of　the　22nd　ACM　symposium　on　parallelism　in　algorithms　and　architectures,　pp　243-252,　2010),　but　remains　open　whether　the　problem　is　NP\documentclass[12pt]{minimal}　\usepackage{amsmath}　\usepackage{wasysym}　\usepackage{amsfonts}　\usepackage{amssymb}　\usepackage{amsbsy}　\usepackage{mathrsfs}　\usepackage{upgreek}　\setlength{\oddsidemargin}{-69pt}　\begin{document}$${\mathcal{NP}}$$\end{document}-hard.　In　this　paper,　we　first　show　that　an　even　harder　problem,　the　fixed-point　k-length　negative　cost　cycle　trail　(FPkLNCCT)　problem　that　is　to　determine　whether　G　contains　a　negative　closed　trail　enrouting　a　given　vertex　(as　the　fixed　point)　and　containing　only　cycles　with　at　least　k　edges,　isNP\documentclass[12pt]{minimal}　\usepackage{amsmath}　\usepackage{wasysym}　\usepackage{amsfonts}　\usepackage{amssymb}　\usepackage{amsbsy}　\usepackage{mathrsfs}　\usepackage{upgreek}　\setlength{\oddsidemargin}{-69pt}　\begin{document}$${\mathcal{NP}}$$\end{document}-complete　in　a　multigraph　even　when　k=3\documentclass[12pt]{minimal}　\usepackage{amsmath}　\usepackage{wasysym}　\usepackage{amsfonts}　\usepackage{amssymb}　\usepackage{amsbsy}　\usepackage{mathrsfs}　\usepackage{upgreek}　\setlength{\oddsidemargin}{-69pt}　\begin{document}$$k=3$$\end{document}　by　reducing　from　the　3SAT　problem.　Then,　we　prove　the　NP\documentclass[12pt]{minimal}　\usepackage{amsmath}　\usepackage{wasysym}　\usepackage{amsfonts}　\usepackage{amssymb}　\usepackage{amsbsy}　\usepackage{mathrsfs}　\usepackage{upgreek}　\setlength{\oddsidemargin}{-69pt}　\begin{document}$${\mathcal{NP}}$$\end{document}-completeness　of　kLNCC　by　giving　a　more　sophisticated　reduction　from　the　3　occurrence　3-satisfiability　(3O3SAT)　problem　which　is　known　NP\documentclass[12pt]{minimal}　\usepackage{amsmath}　\usepackage{wasysym}　\usepackage{amsfonts}　\usepackage{amssymb}　\usepackage{amsbsy}　\usepackage{mathrsfs}　\usepackage{upgreek}　\setlength{\oddsidemargin}{-69pt}　\begin{document}$${\mathcal{NP}}$$\end{document}-complete.　The　complexity　result　for　kLNCC　is　interesting　since　polynomial-time　algorithms　are　known　for　both　2LNCC,　which　is　actually　equivalent　to　negative　cycle　detection,　and　the　k-cycle　problem,　which　is　to　determine　whether　G　contains　a　cycle　with　of　length　at　least　k.　Thus,　this　paper　closes　the　open　problem　proposed　by　Li　et　al.　(2010)　whether　kLNCC　admits　polynomial-time　algorithms.　Last　but　not　the　least,　we　present　for　3LNCC　a　randomized　algorithm　that,　if　G　contains　a　negative　cycle　of　length　at　most　L,　can　find　a　solution　with　a　probability　1-epsilon\documentclass[12pt]{minimal}　\usepackage{amsmath}　\usepackage{wasysym}　\usepackage{amsfonts}　\usepackage{amssymb}　\usepackage{amsbsy}　\usepackage{mathrsfs}　\usepackage{upgreek}　\setlength{\oddsidemargin}{-69pt}　\begin{document}$$1-\epsilon　$$\end{document}　for　any　epsilon　is　an　element　of(0,1]\documentclass[12pt]{minimal}　\usepackage{amsmath}　\usepackage{wasysym}　\usepackage{amsfonts}　\usepackage{amssymb}　\usepackage{amsbsy}　\usepackage{mathrsfs}　\usepackage{upgreek}　\setlength{\oddsidemargin}{-69pt}　\begin{document}$$\epsilon　\in　(0,\,1]$$\end{document}　within　runtime　O(2min{L,h}mnln1　epsilon)\documentclass[12pt]{minimal}　\usepackage{amsmath}　\usepackage{wasysym}　\usepackage{amsfonts}　\usepackage{amssymb}　\usepackage{amsbsy}　\usepackage{mathrsfs}　\usepackage{upgreek}　\setlength{\oddsidemargin}{-69pt}　\begin{document}$$O(2＜^＞{\min　\{L,\,h\}}mn\left\lceil　\ln　\frac{1}{\epsilon　}\right\rceil　)$$\end{document},　where　m,　n　and　h　are　respectively　the　numbers　of　edges,　vertices　and　length　2　negative　cost　cycles　in　G.