基于膜计算的哈密顿路径问题统一解决方案

### 基于膜计算的哈密顿路径问题统一解决方案 #### 一、引言 膜系统是一种模仿细胞层面自然过程的计算模型。研究表明，该模型是在多项式时间内解决NP完全问题的有前景的框架。哈密顿路径问题（HPP）是著名的NP完全问题，已有一些半形式化的P系统来处理它。此前有文献在指定起始和结束顶点的情况下，用膜分离给出了HPP的统一解决方案，但用具有分裂规则而非分离规则的P系统以统一方式在多项式时间内合流地解决HPP仍是一个开放问题。 本文在不指定路径起始和结束顶点的情况下，提出了一种使用膜分裂解决HPP的统一方案，且不使用通信规则（将对象发送到膜中）。接下来将先介绍具有膜分裂的识别器P系统，然后给出用膜分裂解决HPP的方案及相关形式细节。 #### 二、具有膜分裂的识别器P系统 具有膜分裂的P系统构造为：$\Pi =(V, H, \mu, w_1, \ldots, w_m, R)$，其中： - $m \geq1$（系统的初始度） - $V$是对象的字母表 - $H$是膜的有限标签集 - $\mu$是膜结构，由$m$个膜组成，用$H$中的元素标记（不一定是一一对应的） - $w_1, \ldots, w_m$是$V$上的字符串，描述分别放置在$\mu$的$m$个区域中的多重集 - $R$是有限的发展规则集，有以下形式： 1. $e_h v a ] [ \to$，用于$H h \in$，$\{0, +, -\} \in e$，$V a \in$，$* V v \in$（对象演化规则） 2. $b a e_h e_h 2 1 ] [ ] [ \to$，用于$H h \in$，$\{0, +, -\}, 2 1 \in e e$，$V b a \in$（通信规则） 3. $3 2 1 ] [ ] [ ] [ e_h e_h e_h c b a \to$，用于$H h \in$，$\{0, +, -\},, 3 2 1 \in e e e$，$V c b a \in$（基本膜的分裂规则） 这些规则的应用原则如下： - 类型（1）的规则并行应用 - 类型（2）、（3）的规则顺序使用，即一个膜一次最多只能被这些类型的一个规则使用 - 所有可演化的对象和膜应同时演化 下面介绍两个定义： - **定义1**：带输入的P系统是一个元组$(\Pi, \Sigma, \Pi_i)$，其中$\Pi$是一个P系统，工作字母表为$\Gamma$，有$p$个膜，标记为$1, \ldots, p$，初始多重集为$w_1, \ldots, w_p$；$\Sigma$是严格包含在$\Gamma$中的输入字母表，$\Pi$的初始多重集在$\Gamma - \Sigma$上；$\Pi_i$是一个特殊（输入）膜的标签。设$w_{in}$是$\Sigma$上的多重集，带输入$w_{in}$的$(\Pi, \Sigma, \Pi_i)$的初始配置是$(\mu, w_1, \ldots, w_{\Pi_i} \cup w_{in}, \ldots, w_p)$。 - **定义2**：识别器P系统是带输入$(\Pi, \Sigma, \Pi_i)$和输出的P系统，满足工作字母表包含两个特殊元素“yes”和“no”；所有计算都能停止；如果$C$是$\Pi$的一个计算，那么要么“yes”要么“no”（但不是两者）必须在计算的最后一步释放到环境中。若“yes”（或“no”）出现在与$C$的相应停止配置相关的外部环境中，则称$C$是接受（或拒绝）计算。 为了证明第3节中识别器P系统家族$\Pi$为HPP提供了多项式解决方案，还引入了复杂度类的定义。设$AM$代表使用2 - 分裂的具有活动膜的识别器P系统类，复杂度类$PMCAM$定义如下： **定义3**：若一个决策问题$X=(I_X, \theta_X)$可由使用2 - 分裂的识别器P系统家族$\Pi= (\Pi(t))_{t\in N}$在多项式时间内解决，记为$X\in PMCAM$，需满足： 1. $\Pi$是$AM$一致的，即对于每个$t (t\in N)$，$\Pi(t) \in AM$。 2. $\Pi$是通过图灵机多项式统一的家族，即存在一个确定性图灵机，能在多项式时间内根据$t \geq 0$构建$\Pi(t)$。 3. 存在$I_X$在$\Pi$中的多项式编码$(g, h)$，使得$\Pi$关于$(g, h)$是多项式有界的，即存在多项式函数$p$，对于每个$u\in I_X$，$\Pi(h(u))$以输入$g(u)$进行的所有计算最多在$p(|u|)$步内停止；$\Pi$关于$(g, h)$是可靠的，即对于所有$u\in I_X$，如果$\Pi(h(u))$以输入$g(u)$存在接受计算，那么$\theta_X(u)=1$；$\Pi$关于$(g, h)$是完备的，即对于所有$u\in I_X$，如果$\theta_X(u)=1$，那么$\Pi(h(u))$的每个计算都接受$g(u)$。 #### 三、用膜分裂解决HPP 有向图$G$中的哈密顿路径是恰好访问$G$的每个节点一次的路径。HPP的决策问题是：输入一个有向图$G = (V, E)$，输出判断$G$中是否存在哈密顿路径。 本文通过一个暴力算法解决该问题，包含以下阶段： 1. **准备阶段**：引入$n$个顶点，从这些顶点开始搜索可能的哈密顿路径（HPs）。 2. **生成阶段**：通过膜分裂生成$G$中所有长度为$n$的路径（$G$有$n$个顶点）。 3. **检查阶段**：对于之前生成的每个路径，确定它是否访问了$G$的所有节点。 4. **输出阶段**：根据检查阶段的结果回答“yes”或“no”。 ##### 3.1 用膜分裂解决HPP的统一方案 对于任意给定的有$n$个顶点的有向图$G$，构造一个识别器P系统$\Pi(n)$来解决HPP，家族为$\Pi = \{(\Pi(n), \Sigma(n), \Pi_i): n\in N\}$。 输入字母表为$\Sigma(n)=\{x_{i, j, k} | 1\leq i, j \leq n, -1 \leq k \leq i\}$，其中对象$x_{i, j, k}$表示$(i, j) \in E$。实例$G$可编码为输入多重集$w_{in} = \{x_{i, j, k} |1\leq