假设有人找到了一种在 O(n^3) 时间内给定 CNF 布尔表达式创建图的方法，并且这个特殊图的任何生成树都将是 CNF 方程的解。
该场景似乎暗示某人已经找到了 SAT 问题的解决方案，并通过使用仅在 O(n^3) 时间内运行的小工具（减少）将 SAT 问题简化为生成树问题来解决 P=NP。
但是，如果他们的算法创建的图有 n！还是 2^n 个节点和边？
在这种情况下，虽然诸如 DFS 或 BFS 之类的生成树算法可以在节点/边的数量上以线性时间运行，但它不会在布尔表达式的输入数量上以多时间运行。所以这个人不会找到解决 SAT 问题的有效算法，因为运行完整的解决方案需要 n！评估的时间。
这个推理正确吗？