We show that generating all negative directed cycles of a directed graph is a hard generating problem. More precisely, given a digraph and a collection of its negative dicycles, it is NP-hard to decide whether this collection is complete.
As a corollary we solve in negative two well-known generating problems from linear programming:

(i) Given an infeasible system of linear inequalities, generating all its minimal infeasible subsystems(so-called Helly subsystems) is hard.
　 Yet, for maximal feasible subsystems the complexity remains open.

(ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron　is hard. Yet, in case of bounded polyhedra the complexity remains open

(連絡先：数理情報学　牧野　和久　内線２６８９６)