On k-positive satisfiability problem

Xiong Huang; Wei Li

doi:10.1007/BF02948732

On k-positive satisfiability problem

Xiong Huang
, Wei Li

计算机学院

Beihang University

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

An algorithm for solving the satisfiability problem is presented. It is proved that this algorithm solves 2-SAT and Horn-SAT in linear time and k-positive SAT (in which every clause contains at most k positive literals) in time O(|F| · ξ_kⁿ), where |F| is the length of input F, n is the number of atoms occurring in F, and ξ_k is the greatest real number satisfying the equation x = 2-1/x^k. Compared with previous results, this nontrivial upper bound on time complexity could only be obtained for k-SAT, which is a subproblem of k-positive SAT.

源语言	英语
页（从-至）	309-313
页数	5
期刊	Journal of Computer Science and Technology
卷	14
期	4
DOI	https://doi.org/10.1007/BF02948732
出版状态	已出版 - 7月 1999

访问文件

10.1007/BF02948732

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{93f83f4eaf8e4c2ab1b9c481d44ab4b6,

title = "On k-positive satisfiability problem",

abstract = "An algorithm for solving the satisfiability problem is presented. It is proved that this algorithm solves 2-SAT and Horn-SAT in linear time and k-positive SAT (in which every clause contains at most k positive literals) in time O(|F| · ξkn), where |F| is the length of input F, n is the number of atoms occurring in F, and ξk is the greatest real number satisfying the equation x = 2-1/xk. Compared with previous results, this nontrivial upper bound on time complexity could only be obtained for k-SAT, which is a subproblem of k-positive SAT.",

author = "Xiong Huang and Wei Li",

year = "1999",

month = jul,

doi = "10.1007/BF02948732",

language = "英语",

volume = "14",

pages = "309--313",

journal = "Journal of Computer Science and Technology",

issn = "1000-9000",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - On k-positive satisfiability problem

AU - Huang, Xiong

AU - Li, Wei

PY - 1999/7

Y1 - 1999/7

N2 - An algorithm for solving the satisfiability problem is presented. It is proved that this algorithm solves 2-SAT and Horn-SAT in linear time and k-positive SAT (in which every clause contains at most k positive literals) in time O(|F| · ξkn), where |F| is the length of input F, n is the number of atoms occurring in F, and ξk is the greatest real number satisfying the equation x = 2-1/xk. Compared with previous results, this nontrivial upper bound on time complexity could only be obtained for k-SAT, which is a subproblem of k-positive SAT.

AB - An algorithm for solving the satisfiability problem is presented. It is proved that this algorithm solves 2-SAT and Horn-SAT in linear time and k-positive SAT (in which every clause contains at most k positive literals) in time O(|F| · ξkn), where |F| is the length of input F, n is the number of atoms occurring in F, and ξk is the greatest real number satisfying the equation x = 2-1/xk. Compared with previous results, this nontrivial upper bound on time complexity could only be obtained for k-SAT, which is a subproblem of k-positive SAT.

UR - https://www.scopus.com/pages/publications/0032627579

U2 - 10.1007/BF02948732

DO - 10.1007/BF02948732

M3 - 文章

AN - SCOPUS:0032627579

SN - 1000-9000

VL - 14

SP - 309

EP - 313

JO - Journal of Computer Science and Technology

JF - Journal of Computer Science and Technology

IS - 4

ER -

On k-positive satisfiability problem

摘要

访问文件

其它文件与链接

学术指纹

引用此