Scidown文献预览系统！
关于Monotone 3 -Sat的简化np -完全变型( On simplified NP-complete variants of Monotone 3 -Sat )
A Darmann J Dcker
我们考虑3-SAT的简化版本，这是著名的可满足性问题的变体，其中每个子句都由三个完全不同的文字组成，这些文字在两两不同的变量上形成。更确切地说，本文的重点放在单调3-SAT上，即3-SAT对带有单调子句的公式的限制，其中如果子句只包含未否定变量或仅包含否定变量，则子句是单调的。我们证明了单调3-SAT的几个硬度结果，这些结果与对变表象施加的各种限制有关。特别地，我们证明了对于任何k≥2的变量，即使每个变量出现精确k次未否定和精确k次否定，单调3-SAT也是NP完全的。因此，对于具有平衡变量表象的单调3-SAT问题，我们在NP完全和多项式时间可解情形之间建立了一个尖锐的边界。此外，我们还证明了对于任意k≥5，即使每个变量出现精确k次未否定和精确一次否定，单调3-SAT也是NP完全的。进一步，我们证明了当仅限于每个变量恰好出现一次未被否定和三次被否定或相反的情况时，问题仍然是NP完全的。从而改进了Darmann等人的一个结果。（2018）显示每个变量四次出现的NP完全性。我们更强的结果还表明，即使每个变量出现三次未否定和一次否定，3-SAT仍然是NP完全的，从而补充了Berman等人的一个结果。（2003）。
SciDown文献求助系统（解决99%问题） Public Download Elsevier ResearchGate
『Sci-Hub|Scidown』怎么用？来看看教程吧！

支持模式 1.支持DOI号 2.支持英文文献全名搜索 3.支持参考文献搜索 4.知网文献（暂时关闭）

安卓手机、电脑用户，您可以在QQ浏览器里输入 www.scidown.cn 打开scidown解析，就可以解析、下载了！（注意是文献的DOI号）

苹果手机用户，您需要先在App Store里搜索并下载 Documents by Readdle 这个APP，在APP首页，左划右下角的指南针图标打开APP内置浏览器，在浏览器里输入 www.scidown.cn 打开scidown解析，就可以解析、下载了！

如出现BUG？赶快加入【Scidown互助交流群】反馈吧：729083885【点击一键加群】
『Sci-Hub|Scidown』相关参考文献
scidown 一种可回收的香草基环氧树脂，具有高性能，可以与DGEBA竞争下载
scidown 光闪合成Mo2C/石墨烯电催化剂的析氢反应下载