np-sull-hard或not：与非理性输入或参数分区

Question

在 count：np-close或not：用非理性输入或参数

分区

给定集合 $ n={a_1，...，a_ {n} \} $ with $ n $ 正数字和 $ \ sum_i a_i= 1 $ ，查找子集 $ s \ subseteq n $ 使得 $ f（\ sum_ {i \ in s}} _i \ \ alpha）$ 是maxmized，其中 $ f（\ cdot; \ alpha）$ 是一个已知的固定函数，具有参数为 $ \ alpha $ 。

方法1.

为了证明上面的问题的复杂性，我设置了 $ \ alpha= 1 $ 。然后 $ x _ *=textbf {argmax} _ {0 \ le x \ le 1} f（x; \ alpha= 1）$ 可以计算，这是一个非理性的数字和 $ x _ * \约0.52 $ 。

实例

给定集合 $ n={a_1，...，a_ {n + 2} \} $ with $ n + 2 $ 数字

• $ a_1，......，a_n $ 是正面和rational，
• $ \ sum_ {i= 1} ^ n a_i= 0.02 $ ，
• $ a_ {n + 1}= x _ * - 0.01 $ ，和
• $ a_ {n + 2}= 0.99-x _ * $ ，

确定我们是否可以找到 $ n $ 的子集，使得子集的和 $ x_ * $ 。

np-complete

• 由于 $ x _ * $ 是不合理的，所需子集不能包含最后两个数字。
• 由于不包含 $（n + 1）$ th元素的总和小于 $ x_ * $ ，所需子集必须包含 $（n + 1）$ th元素。
• 剩下的问题是找到第一个 $ n $ 数字的子集，其总和为0.01

所以原来的问题是np-complete。

批评

由于 $ x _ * $ 是不合理的，我无法正确地将无理性的数字存储在机器中，我的证明不正确。

方法2

set $ \ alpha $ 具有某些值可能是不合理的，例如 $ \ textbf {argmax} _ { 0 \ Le X \ Le 1} F（x; \ alpha）$ 是合理的。然后在方法1中重复该过程，并且可以从子集总和问题减少问题。此证明没有编码非理性数量的问题。

Answer 1

无法对该问题的NP硬度说出任何内容，因为输入编码未以充分的细节定义。为了能够讨论np-hardence开始，我们需要知道问题实例如何被编码为二进制字符串。改变问题的编码可以改变是否是NP - 硬或不是（例如，如果输入在二进制中的输入编码，则子集总和是多项式的，如果输入在二进制中被编码）。

由于我们正在使用数字，我们需要指定数字在输入中的编码方式。具有非理性数的小问题是将它们作为二进制字符串编码。由于存在许多不合理的数量并且只有许多二进制字符串，因此无法将每个非理性数量作为二进制字符串编码。

假设数字编码的最标准方法是二进制数，但这才允许编码整数或编码。我们当然可以扩展我们可以编码的数字集合，包括一些不合理的数字，例如同意编码的编码，或者同意一些特殊常量的编码（如 $ \ pi $ ）。但是，我们总是限于非理性数的某种可数个子集。

让我们说你选择一个编码，其中，通过纯粹的Serendipity，可以代表 $ x _ * - 0.01 $ 和 $ 0.99-x _ * $ 。然后，问题是NP - 硬于（稍微邋）的）减少，你刚刚给出（除非你使用某种形式的一元编码）。

假设 $ x _ * $ 是一个非常令人讨厌的非理性数字，你不能在问题的编码中代表。此外，假设编码方案在添加和减法下关闭（例如，如果它可以表示 $ x $ 和 $ y $ ，它也可以表示 $ x + y $ 和 $ xy $ ）。那么问题不是NP - 硬，并且是多项式时间可溶性。这是因为每个实例都是一个实例，因为它永远不可能将 $ x _ * $ 作为实例中的数字之和。

有人认为，由于<跨越类=“math-container”> $ x _ * $ 是不合理的，我无法正确地将无理性的数字存储在机器中，我的证明不正确。如何解决它？

您应该通过为您的问题实例指定编码方案来解决此问题。

Answer 2

您所说的问题可能包含错误：

给定集合 $ n $ 使用 $ n + 2 $ 数字，使得第一个 $ n $ 数字是正面和合理的与sum $ 1 $ ， $（n + 1）$ St编号是 $ \ sqrt {2} $ ，以及 $（n + 2）$ nd number是 $ 2 - \ sqrt {2} $ ，确定是否存在 $ n $ 使子集的总和为 $ 3/2 $ 。

答案是从来没有任何这种子集。子集包括 $ \ sqrt {2} $ 和 $ 2 - \ sqrt {2} $ ，或两者都不。如果它既没有包括，那么总和小于或等于 $ 1 $ 。如果它包括两者，那么总和大于或等于 $ 2 $ 。因此，子集的总和永远不会是 $ 3/2 $ 。

Answer 3

是一个众所周知的事实，即子集合总和是np-complete（ $ a_ {n + 1} $ 给你 $ x _ * $ 。检查这正是子集和问题，使其NP完成。

Answer 4

我同意你得到的批评。我认为它比说证明不正确更严重;我认为索赔（你试图证明的东西）尚不清楚或没有明确定义。显然，如果索赔不定义，我们无法询问索赔是否是真实的或虚假的，或者是否存在有效证据。

为什么索赔没有明确定义？这是因为问题并不定义。首先，您未指定如何表示 $ n $ 的数字。如果数字是整数，则默认假设是假设它们在二进制中表示。如果它们是Rational Numbers，则默认假设是Rational Numbers $ a / b $ 表示为一对整数 $ a，b $ ，其中 $ a，b $ ，使 $ b> 0 $ 和 $ \ gcd（a，b）= 1 $ 。但对于可能是非理性的任意数字，目前尚不清楚你的想法。没有办法表示，您可以在有限量的空间中代表所有非理性数量：有不可数的不合理数量，但只有可以有限地表示的数量。因此，要使问题定义良好，您必须指定数字的代表方式，这将隐式对数字构成约束，以便实际上并非所有非理性。

第二，对于 $ x _ * $ 是输入的一部分，还是它是固定常量的。这可能会影响问题的复杂性。

最后，作为奖金，减少证明的缺陷。正确的减少证明必须显示出于任何子集 - 总和的实例，可以使用原始问题的算法来解决该实例。您尚未示出，因为您只考虑子集合的特殊情况。

Answer 5

占用子集和的任何实例，即（多）整数组 $ a={a_1，\ dotsc，a_n \} $ 和目标和 $ s $ （有一个（多） $ a $ 那个sums $ s $ ？），并通过挑选Prime $ p $ 和非理性 $ 0 ，提出 $ a'={a_1 / p，\ dotsc，a_n / p，i， 1 - i \} $ ， $ s'= s / p + 1 $ 。很明显，如果才有一个解决方案，如果只有原始的问题，如果 $ i $ 是有限的 $ \ sqrt {2} - 1 $ ）。因此，您的问题是NP-HARD。如果它也在NP中取决于如何表示（一般）非理性数量。由于存在不可数的非理性，并且只有可计数的有限公式，并非所有实例都可以以有限术语表示。