Apr, 2014

布尔公式解空间中的最短重构路径

PDF
TL;DR本研究研究了用 flip 操作实现布尔公式中一个满足赋值到另一个满足赋值的最短转换问题的复杂度，结果表明该问题的复杂度可能为 P、NP-complete 或 PSPACE-complete。
boolean formulassatisfying assignmentsflipscomplexityreconfiguration
发现论文，激发创造
  • 重新规划最短路径的复杂性

    研究了最短路径重构问题在不同类型的图中的复杂度，其中爪图和弦图可以用多项式时间解决并具有线性长度，同时提供了计算孤立路径数量的算法。

    Sep, 2010

  • 二分图独立集重构的复杂度

    本文研究了在三种常见改变模式下的独立集重新配置问题，发现在 Token Jumping 或 Token addition/removal 模式下问题是 NP-complete，而在 Token Sliding 模式下问题仍然保持是 PSPACE-complete。

    Jul, 2017

  • 平面图中的最短路径重定向

    本文主要探讨最短路径重路由问题，通过引入动态规划方法解决了该问题在平面图上的多项式时间算法。核心关键词为重新路由序列、最短 st - 路径、图论、动态规划。

    Apr, 2012

  • 通过非确定性约束逻辑模型计算的滑块拼图和其他问题的 PSPACE 完备性

    本文介绍了一种基于加权有向图和最小流限制的非确定性计算模型，并且通过一系列特例的证明和简单归约，证明了该模型可以被用于解决复杂的运动规划问题，包括障碍物移动、滑动积木等。

    May, 2002

  • 带量词求解器的通用布尔公式最小化

    该研究旨在解决将命题公式转化为任意格式的等价公式的问题，使用量子布尔公式编码的方法可以有效地解决此类问题，因为这种方法远优于使用暴力方法或者 SAT 求解器进行转化。

    Mar, 2023

  • 图中最短路径的重新配置

    该研究论文提出一个问题：一次只修改一个顶点，从而将一个最短路径修改为另一个最短路径，其应用于优化网络中的路由算法，数据流管理，以及列车调度等优化问题，并基于图论方法研究该问题的复杂度与算法优化。

    Dec, 2021

  • 偏序约束满足问题的复杂性二分定理

    本文研究了扩展时序约束问题的复杂性，并针对一组量词自由的 “小于等于（leq）” 公式所形成的 Poset-SAT 问题进行了讨论。其问题是对于 $x_1$，$x_2$，…，$x_n$ 成为偏序集时是否存在满足给定公式的赋值。最后，作者使用模型理论概念和通用代数技术研究了这些问题的约束满足问题，并提出了独立于通用代数和模型理论的分裂定理。

    Feb, 2016

  • 稀疏图上的重构

    本研究针对两种古典的顶点子集问题 ISR 和 DSR，研究其重配置变体问题，同时提出一种固定参数可跟踪的算法来解决 ISR 和 DSR 问题。

    Feb, 2015

  • 最短路径的重构图

    研究了最短路径重新配置图的性质，包括由最短路径图构成的图类、最短路径图的分解和和以及具有周长五以上的最短路径图的完整分类，并证明了格图的最短路径图是格子的诱导子图。

    May, 2017

  • 模型生成器的转换系统 - 一种统一的方法

    该研究将过渡系统用于计算命题公式的模型，证明了其适用于逻辑规划和 PC（ID）逻辑中，通过计算答案集表示的模型，提供了一种统一的视角，为不同命题形式开发的解决程序提供联系。

    May, 2011