机构名称：
¥ 1.0
考虑一个函数 f：{0,1} n --> {0,1} n 。其定义域和余定义域各由 2 n 个元素组成。在编程上下文中，f 接受 n 个布尔参数并返回一个包含 n 个布尔值的数组。如果将 n 个 0/1 值视为整数二进制表示中的位，那么 f 可以被认为是一个函数，将 [0,N-1] 中的整数映射到 [0,N-1] 中的整数，其中 N=2 n 。我们假设 f 作为一个黑盒 U f（一个 oracle ）提供，并在硬件中实现它。假设 f 满足属性（承诺）：∃𝑠∈{0,1} ！: ∀𝑥, 𝑦∈{0,1} ！ , 𝑓(𝑥) = 𝑓(𝑦) ⇔𝑥= 𝑦 ⊕𝑠 查找位串 s 。换句话说，f 要么是 2 对 1 的（将通过掩码 s 连接的对映射到同一幅图像），要么是 1 对 1 的（将不同的元素映射到不同的图像）。1 对 1 的情况对应于 s 是一串 0，这很简单，我们将通过在承诺中添加 s ≠ 0 n 来回避。因此，我们假设 f 是 2 对 1 的。和以前一样，我们假设 f 通过实现它的黑盒 U f （一个 oracle ）给出。2. 例子
西蒙算法 - CS@YorkU
主要关键词
相关文件推荐
