組合せ最適化
計算複雑性理論の研究は、組合せ最適化に役立っている。いくつかの組合せ最適化問題が、NP困難である事に関係している。そのような問題は、一般的には効率的に解けるとは思われていない。しかし、複雑性理論の様々な近似は、これらの問題のいくつか(例えば「小さな」問題)が効率的に解けることを示唆する。組合せ最適化にも近似解法があり、そのような解法はしばしば重要な応用が可能である。
組合せ最適化(くみあわせさいてきか、英: combinatorial optimization、組み合わせ最適化、または組み合せ最適化とも表記される)は、応用数学や情報工学での組合せ論の最適化問題である。オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。