具有指数空间的多项式时间算法是否合格？

Question

我对两件事感到好奇。

1. 当我们定义计算机科学中称为“概率多项式时间算法”的类时，它是否包含具有指数空间的多项式时间算法？例如，当认为算法被认为是从域中给出$ {0,1 }^n $的输入时，如果内部算法在内部查询其指数尺寸表（例如$ 0^n to 0,0,0,0^{n-）该怎么办1} 1 to1 $等等..）并输出结果？它仍然是多项式时间算法吗？

2. 在理论加密中，单向函数$ f： {0,1 }^* to {0,1 }^*$有一个要求，与之相关 难以扭转 属性，如下块。如果上述问题的答案是肯定的，是否可以使用指数表构建算法$ a'$，以模拟与$ {0,1 }^n $中每个值完全相同？如果这样，这意味着不可能设计单向功能，这绝对不是正确的。那我错过了什么？

   对于每个概率的多项式时间算法$ a'$，每个积极的多项式$ p（ cdot）$，以及所有足够大的$ n $'

   $ pr [a'（f（u_n），1^n）在f^{ - 1}（f（u_n））] < frac {1} {p（n）} $

   其中$ u_n $是随机变量均匀分布在$ {0,1 }^n $上

Answer 1

关于您的第一个问题，您缺少的是“指数表”的来源。您的算法具有有限的描述，应适用于每$ n $。因此，它不能明确包含所有$ n $的$ n $表。它可以包含 指示 为了计算表，但是必须先执行它们，并且构造指数尺寸表需要指数时间。

另一方面，您的程序可以使用（据称）指数的数量 非初始化 空间。由于其运行时间是多项式，因此仅访问多项式的许多单元。您可以以一种方式实现内存访问，以使$ t $单元访问，然后使用$ tilde {o}（t）$内存（练习）。相应的运行时间可能会变得更糟，但仍然多项式。

第三个可能性是 不均匀 计算模型，在密码学中很受欢迎。这里的想法是，该算法可以使用一定的硬编码数据，仅取决于$ n $。但是，该数据必须是多项式大小。这种限制来自对模型的解释 电路. 。在多项式时间内运行的机器对应于每$ n $多项式大小的电路。如果我们现在放松所有这些电路都来自某种算法的约束，那么我们得到 多项式时间, ，这是相同的计算，具体取决于多项式大小的$ n $（练习）。

第一个问题的答案应避免第二个问题。我只想提到，有时而不是概率的多项式时间算法，而是考虑（确定性）多项式大小电路。

Answer 2

1. 没有。在加密社区的标准框架中，这种算法通常不被视为概率多项式时间：如有必要，我们对定义进行调整以确保不是。

   从技术上讲，在密码学中，有些人建议我们使用运行时间的总和以及程序代码的大小作为我们攻击时间的度量（您可以这样考虑：如果程序的代码为$ $ k $位，将需要$ k $时间步骤才能在开始运行之前将代码读取到内存中）。如果您听到某人在密码学中说“跑步时间”，那么他们实际上可能意味着这一总和。我想我首先从菲尔·罗加威（Phil Rogaway）那里学到了这一技术细节，但我不知道他是否是第一个。

   如果您不相信我，这里是文学的一个例子：您可以看一下Bellare等人 密码块链接消息身份验证代码的安全性, ，计算机和系统科学杂志。请参阅第2.2节，《计算模型》，他们在其中写下：

   我们将一些特定的随机访问机（RAM）修复为计算模型。 [...]当我们谈论A的运行时间时，这将包括A的实际执行时间以及A描述的长度（这意味着描述A的RAM程序的长度）。如果人们可以在A的描述中嵌入任意大型查找表，则该惯例消除了导致的病理。

   注意他们如何预期这个角落案例，并选择避免问题的定义。有了这个定义，一切都以合理的方式工作，而您提出的算法（具有指数尺寸的常数）不是概率的多项式时间算法。

   许多密码学家并不总是对他们对运行时间的定义进行谨慎。有点草率并忽略了这种细节非常常见。通常，没关系。但是，当我们开始谈论指数尺寸的常数时，此细节 做 重要的是，如果您想对形式主义争论，那么必须了解此技术细节。

2. 没有。

顺便说一句，尽管有（无法解释的）倾向，但我对此表示支持。许多人并不知道研究界的其他人已经预料到这种微妙之处，而且很少有论文造成了很大的作用，因此我不怪其他人没有意识到加密社区中的相关定义。