ミレニアム懸賞問題 (635ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

295(1): ◆Ph05QxAcng [] 2024/03/10(日)01:06 ID:86TMEkfZ(3/15)
>>294

Now, if we assume that the proposition does not hold, then for every problem, there exists a problem a whose algorithm does not match the class of the problem, and is of a smaller class.

At this time, it is possible to create a program A that generates problem a infinitely.

Let there be a program X that creates problems infinitely, and let r(X) be the ratio of the total problems solved by it.

In the case of A, even if we take n as large as possible with time being ∞^n, r(A) converges to 0.

Let P be the set of all true proof problems, and let p be the set of all computational problems, then P ⊃ p.

To solve a computational problem means to demonstrate the following two points:
(1) Decide whether there is a better algorithm than brute force search, and if it exists, demonstrate that it is the best; if not, demonstrate its non-existence.
(2) If it exists, verify whether a solution exists using that algorithm and specifically output the value. If it does not exist, verify the existence of a solution through brute force search.

---

296: ◆Ph05QxAcng [] 2024/03/10(日)01:06 ID:86TMEkfZ(4/15)
>>295
Let E be the set of numerous problems created by A. Since the corollary indicates that r converges to 1, both (1) and (2) are demonstrated for E and converge to 1 ⇔ for each problem, as all algorithms are the same, the best algorithm for a computational problem must match its class. However, as demonstrated earlier, r(A) converges to 0, which is a contradiction.
Thus, the proposition is demonstrated.

Corollary: P=NP holds.

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.024s