k-CNF可满足性问题

k-CNF SAT

判定每个子句最多含k个文字的合取范式布尔公式是否可满足的决策问题,k≥3时为NP完全。

1篇文章最近提及

k-CNF SAT(k-SAT)是这样一个决策问题:给定一个合取范式(CNF)布尔公式,其中每个子句最多包含k个文字,判断是否存在一组变量赋值使所有子句同时为真。它是布尔可满足性问题(SAT)的特例:2-SAT可在多项式时间内求解,而3-SAT以及所有k≥3的k-SAT都是NP完全问题。

SAT是1971年由斯蒂芬·库克证明的第一个NP完全问题,3-SAT则是证明其他问题NP困难性时常用的归约起点。当变量为n个时,枚举所有赋值需要2^n时间,目前已知有运行时间为2^{cn}(c<1)的算法。指数时间假设(ETH)猜想该问题无法在亚指数时间内求解。在实践中,SAT求解器被用于硬件与软件验证、规划等任务。

本条目依据AIPOST的文章与广为人知的事实整理。如有错误,请通过更正请求告诉我们。

涉及该条目的文章

  • OpenAI模型推翻指数时间假设,但P≠NP仍未动摇AI资讯 ·

    这一假设由Russell Impagliazzo、Ramamohan Paturi和Francis Zane在大约三十年前提出,断言求解该问题的k-CNF版本所需的时间会随变量数量严格呈指数增长。

    阅读文章

发现说明有误或找不到条目?

百科说明依据AIPOST的文章与广为人知的事实整理。如有错误,请通过更正请求告诉我们,我们会核实并修改。新文章中出现的名称会在文章发布后加入百科。