More formally, a problem p is called hard for a complexity class C under a given type of reduction if there exists a reduction (of the given type) from any problem in C to pp.
Више формално, проблем p се зове тешким за сложености класе C под одређеним врстама смањења (комплексности), ако постоји смањење ( датог типа) из било ког проблема из C у pp.