automata - 自动机和可计算性

Question

程序打印 n 个命题符号的真值表需要多长时间？

（符号：P1、P2、...、Pn）

似乎无法破解这个问题，不太确定如何计算这个实例。

标签： automatacontext-free-languagecomputability

Answer 1

这将花费至少与 n*2^n 成正比的时间。每个命题符号都可以假设两个值之一 - 真或假。列出 n 个此类变量的所有可能赋值的真值表部分必须至少有 2 * 2 * ... * 2 (n 次) = 2^n 行，每行 n 个条目；这甚至还没有计算构成表格其余部分的子表达式。这个下界很紧，因为我们可以想象命题 P1 和 P2 和 ... 和 Pn 以及以下过程需要时间 Theta(n*2^n) 来写出答案：

fill up P1's column with 2^(n-1) TRUE and then 2^(n-1) FALSE
fill up P2's column with 2^(n-2) TRUE and then 2^(n-2) FALSE, alternating
…
fill up Pn's column with 1 TRUE and 1 FALSE, alternating
fill up the last column with a TRUE at the top and FALSE all the way down

如果您有更复杂的命题，那么您可能应该将子表达式的数量作为另一个自变量，因为这可能会产生渐近相关的效果（使用 n 个命题符号，您可以拥有任意多个唯一的子表达式，这些子表达式必须在完整的列中给出自己的列真值表）。