(1) NP-hard(definition)

Quoted from http://www.nist.gov/dads/HTML/nphard.html

Definition: The complexity class of decision problems that are intrinsically harder than those that can be solved by a nondeterministic Turing machine in polynomial time. When a decision version of a combinatorial optimization problem is proven to belong to the class of NP-complete problems, which includes well-known problems such as satisfiability, traveling salesman, the bin packing problem, etc., then the optimization version is NP-hard.

Note: For example, “is there a tour with length less than k” is NP-complete: it is easy to determine if a proposed certificate has length less than k. The optimization problem, “what is the shortest tour?”, is NP-hard, since there is no easy way to determine if a certificate is the shortest.

(2) strongly NP-hard (definition)

Quoted from http://www.nist.gov/dads/HTML/stronglyNP.html

Definition: The complexity class of decision problems which are still NP-hard even when all numbers in the input are bounded by some polynomial in the length of the input.