Scholarlink

<p>Unconventional computing plays an important role in computational complexity theory, providing unconventional computing paradigms to tighten the gap between tractable and presumable intractable problems; however, most unconventional paradigms reach similar gaps and their perspective may become stagnant. In this work, we develop a new outlook by a young natural computing paradigm called virus machines (VMs) which takes inspiration from the biological virus life cycle. A new computational complexity theory through VM is developed by attacking a classical NP-complete problem, the Subset Sum problem. It has been uniformly solved by means of deterministic VM. The uniform construction consists of three different modules: one module <i>B</i> for selecting the possible subset; another module <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(Y_j\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Y</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> that encodes the selection, adds it or not to the final sum, and compares the result; and one last module <i>END</i> to reach the halting configuration and make the output consistent. This design provides a new perspective for solving presumably hard problems by means of families of VMs, opening new research lines in this framework.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Uniform solution to Subset Sum by means of virus machines

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年6月29日

查看全文
  • Antonio Ramírez-de-Arellano,
  • David Orellana-Martín,
  • Francis George C. Cabarle,
  • Mario J. Pérez-Jiménez

摘要

Unconventional computing plays an important role in computational complexity theory, providing unconventional computing paradigms to tighten the gap between tractable and presumable intractable problems; however, most unconventional paradigms reach similar gaps and their perspective may become stagnant. In this work, we develop a new outlook by a young natural computing paradigm called virus machines (VMs) which takes inspiration from the biological virus life cycle. A new computational complexity theory through VM is developed by attacking a classical NP-complete problem, the Subset Sum problem. It has been uniformly solved by means of deterministic VM. The uniform construction consists of three different modules: one module B for selecting the possible subset; another module \(Y_j\) Y j that encodes the selection, adds it or not to the final sum, and compares the result; and one last module END to reach the halting configuration and make the output consistent. This design provides a new perspective for solving presumably hard problems by means of families of VMs, opening new research lines in this framework.