NP困難（エヌピーかんなん）とは、計算複雑性理論における概念の一つで、特定の問題がどれだけ計算資源（時間やメモリなど）を要するかを分類する際に使用されます。この用語を理解するためには、まず「P問題」と「NP問題」という基本的な概念を把握する必要があります。
「P問題」とは、多項式時間内で解くことができる問題を指します。多項式時間とは、問題のサイズに対して、計算に必要な時間が問題のサイズの多項式で表せる場合をいいます。例えば、問題のサイズがnであるとき、計算時間がn^2（nの2乗）で済むような問題はP問題に分類されます。
一方、「NP問題」とは、「Non-deterministic Polynomial」の略で、多項式時間内でその解の正しさを検証できる問題を指します。NP問題は必ずしも多項式時間内で解を見つけることができるわけではありませんが、解が提示された場合にはその解が正しいかどうかを多項式時間内で確認することができます。
NP困難は、NP問題の中でも特に難しい部類に属します。正確には、NPに属する全ての問題が、あるNP困難な問題に多項式時間内で変換可能であるとき、その問題をNP困難と呼びます。つまり、NP困難な問題を解くアルゴリズムが見つかれば、それを使ってNPに属する他の全ての問題も効率的に解くことができるということになります。
しかし、NP困難な問題はその性質上、現在のところ多項式時間内で解くことができるアルゴリズムが見つかっていません。そのため、これらの問題に対しては、問題のサイズが大きくなるにつれて計算に膨大な時間がかかることが知られています。
NP困難な問題の一例としては、「巡回セールスマン問題」があります。これは、複数の都市を巡り、各都市を一度だけ訪れて元の都市に戻る最短のルートを見つける問題です。都市の数が増えるにつれて、考えられるルートの数が指数関数的に増加し、計算に必要な時間も膨大になります。
NP困難な問題は、その計算の難しさから、現実世界での応用が困難な場合が多いですが、暗号技術の分野では逆にこの計算の難しさが利点となります。例えば、RSA暗号などは、大きな素数の積を素因数分解する問題の難しさに基づいており、この問題がNP困難であるために、現実的な時間内に解を見つけることが非常に困難です。これにより、暗号が安全に機能するというわけです。
NP困難な問題に対する研究は、計算機科学において非常に重要な分野であり、もしP=NP（すなわち、NP問題が全て多項式時間内で解けるという仮説）が証明された場合、計算機科学だけでなく、数学、暗号学、最適化問題など多くの分野に革命をもたらす可能性があります。しかし、この問題は現在も未解決であり、多くの研究者が挑戦しています。
