最大充足可能性問題の疎な例題に対する厳密アルゴリズム

• 脊戸 和寿

Bibliographic Information

Other Title

• サイダイ ジュウソク カノウセイ モンダイ ノ ソ ナ レイダイ ニ タイスル ゲンミツ アルゴリズム

Abstract

type:Article

We present a moderately exponential time polynomial space algorithm for sparse instances of Max SAT. For instances with n variables and cn clauses, our algorithm runs in time O(2^<(1-μ(c))n)>, where μ(c) = O(1/c^2log^2 c). Previously, an exponential space algorithm with μ(c) = O(1/clog c) was shown by Dantsin and Wolpert [SAT 2006] and a polynomial space algorithm with μ(c) = O(1/2^<O(c)>) was shown by Kulikov and Kutzkov [CSR 2007]. Our algorithm is based on the combination of two techniques, width reduction of Schuler and greedy restriction of Santhanam.

identifier:http://repository.seikei.ac.jp/dspace/handle/10928/606

Journal

• 成蹊大学理工学研究報告 = The journal of the Faculty of Science and Technology, Seikei University

  成蹊大学理工学研究報告 = The journal of the Faculty of Science and Technology, Seikei University 51 (2), 19-21, 2014-12-01

  成蹊大学理工学部

Keywords

• exponential time algorithm
• polynomial space
• satisfiability

Details

• CRID: 1390854717679894016
• NII Article ID: 120005576220
• NII Book ID: AA1203510X
• ISSN: 18802265
• DOI: 10.15018/00000931
• NDL BIB ID: 026087309
• Web Site: http://hdl.handle.net/10928/606
• Web Site: http://id.ndl.go.jp/bib/026087309
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I026087309
• Text Lang: ja
• Data Source:
  • JaLC
  • IRDB
  • NDL
  • CiNii Articles