“语言”一词的意思是什么？

Question

我没有太多的正式背景，在谷歌/维基百科上搜索之后，我也找不到合适的解释。

密码协议中使用的“语言”一词的含义是什么？

最近一次纸中的例句：

BQP中的每一种语言都允许一个经典的验证器、量子证明器零知识论证系统，这是针对量子多项式时间验证器的声音，以及针对经典(和量子)多项式时间验证器的零知识。

Answer 1

这个问题涉及到复杂性类定义中“语言”一词的定义，因此我们可以在有关复杂性理论的参考著作中寻找答案。其中一个工作是阿罗拉与巴拉克之书，它可以读取(以前定义为所有有限二进制字符串集的集合\{0,1\}^* )。

函数将字符串映射到字符串的一个重要特例是布尔函数的情况，其输出是一个位。我们用f的子集L_f = \{x : f(x) = 1\}来标识这样的函数\{0,1\}^*，并调用这些集合、语言或决策问题(我们可以互换使用这些术语)。

因此，这种上下文中的语言只是\{0,1\}^*的子集，即有限二进制字符串的集合。这相当于(也许更直观的)决策问题的概念，这个问题基本上是一个问题，答案是“是”或“不是”。对于这样的问题，我们可以将由字符串组成的语言关联起来，其中的答案是“是”；例如，与“给定一个整数，它是素数”的问题相关的语言吗？是一种语言，其元素正是素整数的(二进制表示)。