0

令 C 是一个将 n 长度位串映射到 {0, 1, 2} 的元素的电路。想象在一个巨大的循环中对一组 n 长度的位串进行排序：00000 与 00001 和 11111 相邻；00001 与 00000 和 00010 相邻；等等

如果 C(00000) = x 且 C(00001) != x，则 C 在这些相邻节点之间更改值。我想计算 C 在循环中更改值的总次数；更具体地说，我只想知道这个数字是偶数还是奇数。

这个问题的复杂性是什么？

4

1 回答 1

0

没有关于函数（电路）C 的其他信息，我想你必须只计算......（你当然不能做的是通过查看它的输入输出来推断 C 的任何功能“特征”只是一个适当的考虑范围的子集。）

所以，我想，你必须执行 O(n) 的许多 C 应用程序，其中 n 是“循环”的大小......所以，在你的情况下是指数的

于 2013-04-25T10:56:38.880 回答