Solving the SAT problem with the string multiset rewriting calculus

期刊论文
出版模式：

开放获取
发表日期：

2024年2月6日

查看全文

Péter Battyányi

摘要

In this paper, we develop computing machinery within the framework of the String Multiset Rewriting calculus (SMSR), as defined by Barbuti et al. [4], to solve the SAT problem in linear time regarding the number of variables of a given conjunctive normal form. This shows that SMSR can be considered a computational model capable of significantly reducing the time requirement of classical decision problems.