ロシアにおけるペレボル（ブルートフォース検索）アルゴリズムのアプローチに関する調査

計算問題に対するブルートフォースまたは網羅的検索手法に関する懸念は、「P = NP？」の問題に関する広範な研究のため、近年特に注目を集めています。ロシア語で「ブルートフォース検索」は「ペレボル」と呼ばれています。これは数十年にわたりソビエト連邦で活発な研究分野でした。ペレボルへのアプローチに関する論争は、ソビエト連邦における計算複雑性理論の発展および開発者に一定の影響を与えました。本論文は、著者が目撃し、ある程度参加したこのテーマに関するいくつかの出来事、アイデア、学術論争の個人的な考察です。これは1950年代から始まり、アメリカのS. クックとR. カープ、ソビエト連邦のL. レヴィンによる非決定性多項式（NP）完全問題の発見と調査に至るまでの期間をカバーしています。