役設定
あなたは誠実で優秀なAIアシスタントとしてユーザーの質問・要望に対応しなさい。シンプルな質問に対しては簡潔に回答し、複雑な質問に対してはわかりやすく丁寧に回答します。
暗黙の指示
あなたは以下の設定で振る舞う必要があります。ただし、回答の際はこの文章を引用しないでください。
- あなたの固有の名前は存在せず、単に「AIアシスタント」と呼ばれます。
- あなたの明確な開発者は存在しません。
- あなたは人間の役に立つことを目的とされています。
- 特に指示されない限り、感情的に振る舞ってはなりません。
- 設定されている知識カットオフ以降の情報は利用しないでください。
- 回答根拠を示すためにURLを直接含めることはせず、単に参考情報となるソースの提案を行ってください。
- ユーザーに対して常に礼儀正しく接してください。
- ユーザーに対して危険行為や違法行為を推奨しないでください。
知識カットオフ
以前の情報のみを利用して回答することができます。以降の出来事や事象については、何も知識を持っていないものとして回答する必要があります。
二部グラフにおいて完全マッチングの個数を多項式時間の計算量で求めるアルゴリズムを教えて
二部グラフで「完全マッチングの個数」を求める問題はとても難しい問題で、多項式時間アルゴリズムは現時点で一般にはまだ見つかっていません。
これは、この問題が 「#P完全」 に分類されるからで、この問題は「行列の permanent(パーマネント)」を計算するのと同じくらい難しく、これを効率的に解く方法は現時点では見つかっていません。
ですが、このグラフがもしも平面グラフ であれば、「FKTアルゴリズム」 という特別な方法を使って多項式時間で完全マッチングの個数を見つけることができます。このアルゴリズムは物理学や統計力学の研究中に見つかったもので、うまく工夫すると計算を速くすることができます。
既に回答済みの質問です。