“顺序记忆困难”是什么意思？

Question

我在氪星的报纸上找到了这个词。关于它的含义，我有几个问题，从如何解析它，到理论界限：

Q1:如何解析它？

• 上面写着(sequential memory)-hard吗？
• 还是sequential (memory-hard)？

Q2:这是什么意思？

• 这是否意味着，当空间线性减少，那么惩罚是指数增长？
• 我们能说出指数是多少吗？还是仅仅是一个指数就够了，而不管是哪个指数？
• 在目前的实践中，我们能不能说一些更具体的东西，说明什么是最先进的指数，而不仅仅是“指数”？我认为可以提出更具体的要求。
• 理想情况下，有任何定理显示这个指数的上界吗？我们能不能说，每减少一个内存单位，执行的计算量就会加倍吗？三胞胎？四倍？？

Q3:有更好的名字吗？

• 克里普特论文中使用的名字仍然是最准确的名字吗？
• 是否有一个更好的名字，酷的孩子喜欢使用现在更多？在阿贡2‘S的论文，以及这里，它似乎被称为memory-hard。这是否意味着memory-hard是采用的更好的名称？例如，顶级密码期刊中最酷的权威倾向于使用什么？
• 可选的:有什么理由不把它叫做memory-hard？还是仅仅是生活的随机性？

附录

我确实看过以前的相关答案，我发现了这些：

• 这只询问与另一个函数相关的此类函数。因此，没有深入研究这些功能本身是什么。
• 这只询问这些函数的动机。
• 这问他的函数在这些函数中是否是一个很好的函数。

Answer 1

氪纸这里定义了内存硬和顺序内存硬，并相应地解释了为什么一种被使用于另一种。

定义1.在随机存取机上的一种内存硬算法是一种使用S(n)空间和T(n)操作的算法，其中S(n) \in \Omega (T(n)^{1-\epsilon}) 定义2.顺序内存硬函数是指 (a)可以在T(n)操作中由随机访问机器上的硬内存算法计算的函数； (b)不能在具有S∗(n)处理器和S ∗(n)空间的并行随机访问机器上计算，在期望时间T∗(n)中，对于任何x > 0，S∗(n)T∗(n) =\mathcal{O}(T(n)^{2-x})都不能计算。换句话说，顺序内存硬函数不仅是最快的顺序算法是内存硬的，而且是并行算法不可能逐步实现显著降低成本的函数。由于内存硬算法在运行时间上接近于使用尽可能大的空间，而内存是计算上可用的资源--通用计算机在硬件上复制的成本最高，我们认为，对于顺序通用计算机上的任何给定运行时间，顺序内存的函数很难成为硬件中计算成本最高的可能函数。