论文标题
锤距离的复杂性类别可回收鲁棒问题
The Complexity Classes of Hamming Distance Recoverable Robust Problems
论文作者
论文摘要
在众所周知的复杂性中，NP是组合问题，其优化对应对许多实际情况很重要。这些问题通常考虑有关输入的全部知识。但是，在实际设置中，输入数据中的不确定性是通常的现象，因此通常不在NP问题的优化版本中涵盖这一现象。对输入数据中的不确定性建模的一个概念是可恢复的鲁棒性。组合问题P的可回收强大版本P分为基本方案$σ_0$，而不确定性方案集$ \ textsf {s} $。 The base scenario and all members of the uncertainty scenario set are instances of the original combinatorial problem P. The task is to calculate a solution $s_0$ for the base scenario $σ_0$ and solutions $s$ for all uncertainty scenarios $σ\in \textsf{S}$ such that $s_0$ and $s$ are not too far away from each other according to a distance measure, so $s_0$ can be容易适应$ s $。本文介绍了锤距离可回收的鲁棒性，其中必须计算解决方案$ s_0 $和$ s $，因此$ s_0 $和$ s $的$κ$元素可能只有差异。我们调查了锤距离距离可回收的优化问题的稳健版本的复杂性，通常在NP中针对不同方案编码发现。复杂性主要位于多项式层次结构的较低水平。该论文的主要贡献是一个小工具还原框架，该框架表明，在大量组合问题中，可回收的稳健版本是$σ^p_ {3} $ - 完整。此类包括诸如顶点封面，着色或子集总和之类的问题。此外，我们将结果扩展到$σ^p_ {2m+1} $ - 用于多级可回收可恢复的可鲁棒问题的完整性，使用$ m \ in \ mathbb {n} $阶段。
In the well-known complexity class NP are combinatorial problems, whose optimization counterparts are important for many practical settings. These problems typically consider full knowledge about the input. In practical settings, however, uncertainty in the input data is a usual phenomenon, whereby this is normally not covered in optimization versions of NP problems. One concept to model the uncertainty in the input data, is recoverable robustness. The instance of the recoverable robust version of a combinatorial problem P is split into a base scenario $σ_0$ and an uncertainty scenario set $\textsf{S}$. The base scenario and all members of the uncertainty scenario set are instances of the original combinatorial problem P. The task is to calculate a solution $s_0$ for the base scenario $σ_0$ and solutions $s$ for all uncertainty scenarios $σ\in \textsf{S}$ such that $s_0$ and $s$ are not too far away from each other according to a distance measure, so $s_0$ can be easily adapted to $s$. This paper introduces Hamming Distance Recoverable Robustness, in which solutions $s_0$ and $s$ have to be calculated, such that $s_0$ and $s$ may only differ in at most $κ$ elements. We survey the complexity of Hamming distance recoverable robust versions of optimization problems, typically found in NP for different scenario encodings. The complexity is primarily situated in the lower levels of the polynomial hierarchy. The main contribution of the paper is a gadget reduction framework that shows that the recoverable robust versions of problems in a large class of combinatorial problems is $Σ^P_{3}$-complete. This class includes problems such as Vertex Cover, Coloring or Subset Sum. Additionally, we expand the results to $Σ^P_{2m+1}$-completeness for multi-stage recoverable robust problems with $m \in \mathbb{N}$ stages.
