Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Review . 2026
License: CC BY
Data sources: ZENODO
addClaim

有界キャリー代数によるNP完全問題の多項式時間収束: 部分和問題に対する階層的縮約アルゴリズム (Polynomial-Time Convergence of NP-Complete Problems via Bounded Carry Algebra: Hierarchical Carry Reduction Algorithm for Subset Sum Problem)

有界キャリー代数によるNP完全問題の多項式時間収束: 部分和問題に対する階層的縮約アルゴリズム (Polynomial-Time Convergence of NP-Complete Problems via Bounded Carry Algebra: Hierarchical Carry Reduction Algorithm for Subset Sum Problem)

Abstract

[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

Keywords

有界キャリー代数, アルゴリズム, P対NP問題, 福永大河, 計算量, NP-complete, 部分和問題

Powered by OpenAIRE graph
Found an issue? Give us feedback