难解性(intractability)可解的但又不是易解的一种性质。若一个问题是能行可解的，但又不是实际可解的，则称之为难解的.可见，难解性也是一种非严格定义的直观概念，依库克一卡普论题，难解的问题就是指非多项式时间可解的能行可解问题。

难解性(intractability)可解的但又不是易解的一种性质.若一个问题是能行可解的，但又不是实际可解的，则称之为难解的.可见，难解性也是一种非严格定义的直观概念，依库克一卡普论题，难解的问题就是指非多项式时间可解的能行可解问题.

比较简单的一些可判定的难解问题是在20世纪60年代初发现的，但它们都是一些“人工制造”的问题.这种例子的比较自然的例子直到20世纪70年代初才获得，其中，迈耶(Meyer,A.)和斯托克梅耶(Stokmeyer , L.)证明了带平方的正规表达式的等价性问题是一个可判定的问题.但却需要指数时间，从而这是难解的.另一个有趣的难解问题是普莱斯博格算术系统的判定问题，费希尔(Fisher,J. J. )和拉宾(Rabin, M. O.)于1974年证明了普莱斯博格算术系统的判定需要指数时间2 Zcn，因而也是难解的.