恋がNP完全であることの証明~定式化まで~

Annihilatus

皆さんこんにちは。街中を歩いていて「恋の方程式」という単語が聞こえてくると、「計算量はどんなもんなんだろう」と疑問に感じることありますよね。（これが多項式時間で解けるならば誰も苦労はしないわけですが……）
そんなわけで、恋のNP完全性を無理やり示していきます。


方針

一口に恋の方程式と言っても、それが具体的にどのような問題であるかを定めなければ何も始まりません。例えば、世の中には恋愛微分方程式$${^{1)}}$$なるものが提唱されているらしいですね。実際の恋愛に即した問題を考えようと思ったら、自分で定式化するしかなさそうです。
そこで、次のような方針で進めていくことにします。

  1. 問題の定式化

  2. NP完全性の証明

本記事では1の定式化までやります。

1) Strogatz, Steven H. "Love affairs and differential equations." Mathematics Magazine 61.1 (1988): 35-35.

定式化

自分の独断と偏見で定式化を試みても良いのですが、主観が入りすぎるとよろしくありません。フラットな意見を提供してくれる助手を採用しましょう。

お願いする前からやる気十分みたいですね。早速次のような指示を与えてみます。

Take1: First Impression

Q. 恋がNP完全であることの証明を以下のステップにしたがって行いたいです。
　1. 「恋の方程式」を定式化する
　2. これがクラスNPに属することを示す
　3. NP完全な問題（SATなど）から帰着できることを示す
指針を教えてください。

NP完全性を示すことが目的なので、事前にそのことを伝えておきます。こうしておくと計算量理論っぽい判定問題を吐き出してくれるはずです。

A. 「恋がNP完全であることを証明する」というユニークなテーマですね！以下は、この証明のための指針です。冗談交じりの比喩的な説明としてお楽しみください。

ステップ1: 「恋の方程式」を定式化する

「恋の方程式」として、恋愛を以下のように形式化できます：

  1. 入力:

    • $${P = \{p_1, p_2, \ldots, p_n\}}$$: 恋の候補者の集合

    • $${C = \{c_1, c_2, \ldots, c_m\}}$$: 候補者に対する制約条件（例：性格、趣味、価値観など）

    • $${S = \{s_1, s_2, \ldots, s_k\}}$$: 相手から自分への好意の度合い

  2. 問題の定式化:
    「$${P}$$ から候補者の部分集合 $${P' \subseteq P}$$ を選び、すべての制約 $${C}$$ を満たし、かつ $${S}$$ を最大化することが可能か？」ここで、制約の満足は「条件 $${c_i}$$をすべて $${True}$$ にする組み合わせを探す」と考えればよいです。恋愛における「相性の良さ」を最大化する最適化問題のように見えます。

ステップ2: NPに属することを示す

この問題がクラスNPに属するためには、解（適切な候補者集合 $${P'}$$）が与えられた場合に、それがすべての制約 $${P'}$$を満たしているかどうかを多項式時間で検証できる必要があります。

  • 各候補者 $${p}$$ に対して、制約 $${C}$$ を一つずつチェックするのは効率的に行えます（例えば、$${O(m \cdot |P'|)}$$ 時間）。

  • $${P'}$$ の中で $${S}$$ を計算する（好意の合計値を確認する）操作も同様に多項式時間で可能です。

したがって、この問題は少なくともクラスNPに属します。

ステップ3: NP完全な問題からの帰着

ここでは、SAT（充足可能性問題）から恋の方程式への帰着を考えます。

  1. SATの構造:
    SATでは、命題論理の式が与えられ、真偽値を適切に割り当てて式を満たせるかを判断します。

  2. 帰着の方法:

    • SATのリテラル $${x_i}$$ を恋愛の候補者 $${p_i}$$​ に対応付けます。

    • SATの句（例えば $${(x_1 \lor \lnot x_2 \lor x_3)}$$）を恋愛の制約 $${c_j}$$ に対応させます（例：「候補者1または候補者3を選び、候補者2は選ばない」）。

    • SATが充足可能である場合、その充足解が恋の方程式の解となります。

したがって、SATを多項式時間で恋の方程式に変換できることから、この問題はNP困難であると言えます。

結論

「恋の方程式」はクラスNPに属し、かつSATから帰着可能であるため、NP完全であると主張できます。

．．．．．．huh?

うん、やろうとしていることは合ってるんだよ。でもね、言ってることがいっちょんわからん。

補足:
この議論は現実の恋愛を正確に説明するものではありませんが、論理パズルとしての楽しさを追求しています！

正確とか不正確以前の問題なのよね。楽しさを追求してくれるのはありがたいのだけれど。

一応解読を試みてみましょう。まず入力として恋の候補者の集合$${P}$$が与えられています。よくあるホールの結婚定理とかが関わってくるのかと思いきやそういった話ではなく、最終的には候補者の部分集合$${P'}$$を選ぶと……一人を選ぶのではなく？

制約$${C}$$を満たし、かつ好感度$${S}$$を最大化するというのは良さそうです。一方、我々が知りたい情報、つまり「恋の方程式」の解として得たいものについてですが、基本的には特定の相手との恋愛が成就するかどうかでしょう。
そう考えると、入力として2人の情報を与え、何かしらの行動を起こすことによって好感度が変動し、最終的な好感度を最大化するといった方向性で定式化するのがしっくりきます。

なんか恋愛シミュレーションゲームみたいだな。

さて、これをもとに考えた問題について意見を聞いてみます。

Take2: Second Impression

Q.  もう少し現実の恋愛に即した定式化をしてみましょう。

「AとBの恋愛が1年後に成就している確率$${p}$$を最大化する」
　・入力$${A,B}$$（その人の特性）
　・制約$${C}$$（2人の特性が$${A,B}$$であるとき、現在の成就確率$${p}$$のもとで、ある行動$${x}$$をとると成就確率が$${y}$$だけ上昇(下降)する）
　・1日に1度行動をとるとして、計365回の行動をとる
　・365回の行動で$${p}$$を最大化する

A. これは非常に興味深く、現実的な恋愛のダイナミクスを取り入れた問題ですね！「$${A}$$と$${B}$$の恋愛が1年後に成就している確率 $${p}$$ を最大化する」という問題を、最適化問題として定式化してみます。

問題の定式化

  1. 入力データ

    • $${A, B}$$: それぞれの特性（性格、趣味、価値観、行動パターンなどの特徴ベクトル）。例えば、$${A = \{a_1, a_2, \ldots, a_k\}}$$,$${ B = \{b_1, b_2, \ldots, b_k\}}$$。

    • 制約 $${C}$$: 行動 $${x_i}$$ による成就確率の変化 $${\Delta p(x_i, A, B)}$$。行動 $${x_i}$$ は行動の選択肢（例：連絡する、デートに誘う、プレゼントを渡すなど）であり、$${A}$$と$${B}$$の特性に依存して効果が変わる。

    • 初期確率 $${p_0}$$​: 恋愛の初期成就確率。

  2. 変数

    • $${x_t}$$​: 時刻 $${t}$$ における行動選択（$${x_t \in X, |X| = m}$$）。

    • $${p_t}$$​: 時刻 $${t}$$ の成就確率。

  3. 目的関数
    1年後の成就確率 $${p_{365}}$$​ を最大化する:$${\\ \qquad \text{maximize} \quad p_{365} = p_0 + \sum_{t=1}^{365} \Delta p(x_t, A, B)}$$

  4. 制約条件

    • $${x_t \in X}$$: 1日に選択できる行動は行動集合 $${X}$$ から1つ。

    • 行動 $${x_t}$$ の選択による効果 $${\Delta p(x_t, A, B)}$$ は以下のように依存する：

      • $${A}$$と$${B}$$の特性（例：性格が似ている場合、好感度が上がりやすい）。

      • 現在の成就確率 $${p_t}$$​（進展度が低い場合、効果が大きいなど）。

この問題がNPに属することの議論

  1. 解の検証可能性

    • 与えられた行動の列 $${\{x_1, x_2, \ldots, x_{365}\}}$$ が成就確率 $${p_{365}}$$​ を計算可能かどうかを検討します。

    • 各 $${x_t}$$ に対して、対応する $${\Delta p(x_t, A, B)}$$ を計算し、合計すればよいので、検証には多項式時間で済みます。

したがって、この問題はクラスNPに属します。

SATからこの問題への帰着

SATの解を「行動選択の列」にマッピングすることで帰着できます。

  1. SATのリテラル → 行動選択

    • SATの変数（リテラル）を、1日に取るべき行動 $${x_t}$$ と対応付けます。

  2. SATの句 → 制約条件

    • 句（例えば $${x_1 \lor \lnot x_2 \lor x_3}$$）を「特定の行動選択が成就確率に影響を与える条件」としてマッピングします。

  3. SATの解 → 成就確率の向上

    • SATで式が満たされるとき、恋愛行動の列が最適化され、確率 $${p_{365}}$$ を最大化する方向に寄与します。

SATからこの問題への帰着は多項式時間で可能なので、この問題はNP困難です。

結論

「$${A}$$と$${B}$$の恋愛が1年後に成就している確率 $${p}$$ を最大化する問題」は、

  1. 解が与えられたときに検証可能である（NPに属する）。

  2. SATから帰着可能である（NP困難）。

したがって、この問題は NP完全 であると考えられます。

定式化についてはだいぶ形になりましたね。GPTちゃんに投げてから気が付きましたが、これだと最適化問題なのでNP完全性の議論ができません。そこを修正したら定式化完了かな……とその前に

追記: 現実世界の恋愛を数学的にモデル化することは楽しい試みですが、愛の真髄は予測不可能性にあるかもしれませんね！

やかましいわ！

何故かAIに人間の機微を諭されながらも先に進みます。

進化続ける AI の支配下で
真価問われる Human Human Human Human

ストレイライト「Timeless Shooting Star」(作詞:下地悠 作曲:徳田光希)

Chat GPT o1シリーズなんかは理数系にもだいぶ強くなっているようで。
本当にうかうかしてられないわね……。

Take3: Final Decision

Q. これ最大化ではなくて、成就確率がある値以上になりうるかを判定する問題にした方が良くないですか？

A. 素晴らしい指摘です！最大化問題と判定問題の違いはNP完全性を議論する際に重要です。それぞれのケースを整理して解説します。

1. 最大化問題とNP完全性

NP完全性は基本的に「判定問題」に対して定義されています。つまり、「解が存在するかどうか」を多項式時間で判定でき、他のNP問題から多項式時間で帰着可能であることが条件です。

一方で、最大化問題は「最適な解を見つける」ことを求めており、NP完全性というよりは「NP困難（NP-hard）」として分類されます。これは、解そのものを探索するため、判定問題よりも難しい可能性があるからです。

恋愛最大化問題の場合：

「365日間で成就確率 $${p_{365}}$$ を最大化する」という問題は、

  • $${p_{365}}$$​ の最大値そのものを見つける必要があるため、NP問題ではなく「NP困難」と考えられます。

2. 成就確率が閾値以上になりうるかを判定する問題

最大化問題を次のような判定問題に変換すると、NP完全性を議論しやすくなります：

判定問題の定義：

「365日の行動選択により、成就確率 $${p_{365}}$$​ が閾値 $${P_{\text{target}}}$$ 以上になる行動列が存在するか？」

  • 入力: $${A, B}$$（特性）、制約 $${C}$$、初期確率 $${p_0}$$​、閾値 $${P_{\text{target}}}$$

  • 出力: YES/NO（そのような行動列が存在するか）

この問題は次のように整理できます：

  1. クラスNPに属することの確認

    • 解（行動列）が与えられた場合、365日間の行動を1日ずつシミュレーションし、確率 $${p_{365}}$$​ を計算して $${P_{\text{target}}}$$ 以上かを判定するのは多項式時間で可能です。

    • よって、この問題はクラスNPに属します。

  2. NP困難な問題からの帰着

    • SAT問題を帰着できます。例えば、行動選択が満たすべき条件を句（制約）として対応させ、恋愛成就確率が閾値以上となるかどうかを判定問題に落とし込むことで、多項式時間で帰着できます。

3. 最大化問題 vs 判定問題

  • 最大化問題: 恋愛成就確率を最大化する問題は「NP困難（NP-hard）」として分類され、解を直接求めるのが難しい。

  • 判定問題: 成就確率がある閾値以上になるかを判定する問題は「NP完全」となる可能性が高い。

今更ですけどGPTちゃんの言ったこと鵜呑みにしちゃダメですよ？
この回答に関しては大体合ってますが、前2つはクラスNPに属することの説明から出鱈目なので真に受けないように。

NP完全とNP困難の違いですが、NP困難な問題のうちクラスNPに属するものをNP完全と言います。クラスNPに属する問題以上に難しいというのが、NP困難の直感的な理解ですね。

結論

最大化問題そのものはNP完全ではなく、NP困難に分類されます。一方、成就確率が閾値以上になるかを判定する形にすれば、NP完全性を議論できます。そのため、NP完全性を示したい場合は判定問題の形式にするほうが適切です。

現実的には、恋愛における最適解を見つけるのはどちらにしても困難ですね！

うまいこと言ったつもりか！！！！！！！！！

結果

「恋の方程式」を定式化した結果、次のような判定問題になりました。

「$${n}$$日の行動選択により、恋愛の成就確率 $${p_{n}}$$​ が閾値 $${P_{\text{target}}}$$ 以上になる行動列が存在するか？」

入力

  • 自分自身の特性$${A}$$

  • 相手の特性$${B}$$

  • 成就確率の変動を決定する制約$${C}$$

  • 初期確率 $${p_0}$$​

  • 閾値$${P_{\text{target}}}$$

詳細

  • 2人の特性が$${A,B}$$であるとき、現在の成就確率$${p}$$のもとで、ある行動$${x}$$をとると成就確率が$${y}$$だけ上昇(下降)することを制約$${C}$$とする。

  • ただし、$${A,B}$$が不変である状況においては入力として$${A,B}$$を与える必要はなく、制約$${C}$$に組み込んでしまえばよい。

  • 行動の選択肢は有限$${m}$$個

  • 確率はパーセント表記の整数値（0以上100以下）で表す。

例えば閾値を100にすると、必勝法の有無を判定してくれます。

成就確率は言い換えると好感度みたいなものですよね。最終的な好感度によってエンディングが変わるとか。
うーん、シチュエーションが美少女ゲームすぎるなあ。

というわけで、勝手ながらこれを「ギャルゲ問題」と名付け、次の記事ではギャルゲ問題のNP完全性を示していきたいと思います！（恋がNP完全なんじゃなくてギャルゲーがNP完全なだけじゃねというツッコミはさておき）

宣伝

次の記事と書きましたが、この続きは夏コミ（c106）で公開されます！

もともとは自分のサークル（アニ研）の会誌用に書こうとしていた記事なんですが、どうせなら 理情 Advent Calendar 2024 - Adventar にも載せようということで急遽突貫工事で書きました。
「アニメ関係なくね？」と思われそうですが、夏コミ記事では『理系が恋に落ちたので証明してみた。』（通称『リケ恋』）のSSみたいな感じに仕上げようと思っています。作品を知っている人ならピンとくると思いますが、判定問題がギャルゲーみたいになったのも実はめちゃくちゃ理由があったり。

ちなみにうちのサークルはリケ恋のアニメ制作に協力してたみたいですね。あまり詳しいことはわかりませんが。

恐らくそこら辺の繋がりからだと思いますが、駒場祭でもトークショーやったりしてたみたいです。

それから、夏コミで出す会誌ってなんじゃという話ですが、毎回こんなやつ作ってます。

自分は冬コミ（c105）には間に合いそうにないので、残念ながら見送りです。直近3回は毎度書いていたのですが……。

「恋がNP完全であることの証明」なんて記事を書こうと思った背景ですが、サークル内で学問×恋愛の話題が出まして。要するに文学×恋愛とか物理×恋愛とか、そういった類でどういう物語が作れそうかという。
情報×恋愛となったとき真っ先に思い浮かぶのは、いかにもな眼鏡キャラがパソコンをカタカタしながら解析した結果、「クソッ！　データに合わないッ！」と叫ぶ光景ですが、それはさすがに浅すぎるなと。

そこで考え付いたのが「恋はNP完全である」という謎フレーズでした。難しいってニュアンスを伝えたいだけならNP困難でも良かった、というよりクラスNPに属さないだろと思うのでむしろそちらの方が適切な気もするのですが、単純に「完全」の方がかっこいいんですよね言葉が。恋愛の美しさも表しているというか。

さらに理情の人はお察しの通り、講義『計算量理論』のボーナス問題
『自分の好きな「ゲーム」がNP完全（あるいはP）であることを示せ！』
にも繋がっているんですよね。ちゃんとした証明ではなくあくまでも余興ではありますが、本レポートとは別に書いて、あわよくばフィードバックもらえないかなあと淡い期待を胸に抱いております。

いかがだったでしょうか

続きの公開が半年以上先になってしまうのは非常に心苦しいのですが、ちゃんとした記事にして公表する予定なので、完成版が気になるという方はぜひ夏コミ号をご購入ください。コミケ会場以外でも五月祭・駒場祭で販売しています。あるいは通販でも入手できるかも（↓これは過去のやつ）。

SSA 冬コミケ号C103 ジンバラン（メロンブックス）の通販・購入はメロンブックス | メロンブックス

質問は常にAVAILABLEです。何かあれば https://x.com/observer929 まで。

いいなと思ったら応援しよう！