An algorithm for Exact Satisfiability analysed with the number of clauses as parameter

被引：8

作者：

Madsen, BA ^{[1
]}

机构：

[1] Univ Aarhus, BRICS, Dept Comp Sci, Aarhus, Denmark

来源：

INFORMATION PROCESSING LETTERS | 2006年 / 97卷 / 01期

关键词：

Exact satisfiability; analysis of algorithms;

D O I：

10.1016/j.ipl.2005.08.011

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We give an algorithm for Exact Satisfiability with polynomial space usage and a time bound of poly(L) (.) m!, where m is the number of clauses and L is the length of the formula. Skjernaa has given an algorithm for Exact Satistiability with time bound poly(L) (.) 2(m) but using exponential space. We leave the following problem open: Is there an algorithm for Exact Satisfiability using only polynomial space with a time bound of c(m), where c is a constant and m is the number of clauses? (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：28 / 30

页数：3

共 11 条

[1] New algorithms for Exact Satisfiability [J].