
[Abstract / 概要] This paper proposes a deterministic algorithm, "Hierarchical Carry Reduction," that belongs to the computational complexity class P for the Subset Sum Problem (SSP), a representative NP-complete problem. By mapping integer sets into a B=16 base vector space and utilizing the "Carry Inclusion Theorem," we prove that the number of effective states to be maintained is strictly bounded by the number of elements n at any depth k. Furthermore, based on the principle of Resource Equivalence under fixed-variable transition, we demonstrate that state reduction occurs without loss of information. This research presents a constructive solution to the P=NP problem with a total computational complexity of O(L \cdot n^2). 本稿では、NP完全問題の代表例である部分和問題(Subset Sum Problem)に対し、計算複雑性クラスPに属する決定論的アルゴリズム「階層的キャリー縮約法」を提案する。 整数集合を16進法のベクトル空間へ写像し、「キャリー包摂定理」を導出することで、保持すべき有効状態数が要素数 n に対して線形に拘束されることを数学的に証明した。 また、変数軸固定遷移におけるリソース等価性の原理に基づき、状態縮約が厳密解を保持することを明示し、総計算量 O(L \cdot n^2) によるP=NP問題への構成的な解決を提示する。 [Author / 著者] Taiga Fukunaga (福永 大河) Born in 2009(2009年生まれ) Independent Researcher / Riken Doctor AAA
有界キャリー代数, アルゴリズム, P対NP問題, 福永大河, 計算量, NP-complete, 部分和問題
有界キャリー代数, アルゴリズム, P対NP問題, 福永大河, 計算量, NP-complete, 部分和問題
