Browse Prior Art Database

Probabilistic Analysis of a Generalization of the Unit Clause Literal Selection Heuristic for the k-Satisfiability Problem

IP.com Disclosure Number: IPCOM000148994D
Original Publication Date: 1985-Jan-31
Included in the Prior Art Database: 2007-Mar-30
Document File: 28 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Chao, Ming-Te: AUTHOR [+3]

Abstract

Probabilistic Analysis of' a Generdization of the Unit Clause Literal Selection Heuristic for the ksatisfiability Problem Ming-Te Chao Case Weatern Reserve University Department of Computer Engineering and Science Cleveland, 08 44106 and John h c o Indiaaa UniversityDepartment of Computer Science Bloomington, IN 47405 TECHNICAL REPORT NO. 165 Probabilistic Analysis of a Generalization of the Unit Clause Literal Selection Heuristic for the ksatisfiability Problem Ming-Te Chao, Case Western Reserve University and John h c o , Indiana University January, 19115 This material is brued on work supported by the U.S. Air Force under grant number AFOSR-840372. ABSTRACT Two algorithm for the k-Satiefiabiity problem are prerrented and a probabii tic analysis is performed. The analysis ir, basedl on an instance distribution which is parameterised to simulate a variety of sample characteristics. The algorithms aaaign dueu to literals appearing in a given instance of k-Satisfiability, one at a time, until a solution is found or it is discovered that further assignments cannot lead to finding a solution. One algorithm tho- the next literal from a unit clause if one exists and randomly from the eet of remaining literals otherwise. The other algorithm u w a generaliaation of the Unit-Clause rule as a heuristic for selecting the next literal: at each step a literal is choeen randomly from a clause containing the least number of literals. The algorithms run in polynomial time and it ia shown that they find a solution to a random instance of k-Satisfiabiility with probability bounded from below by a constant greater than sero for two different rangea of parameter values. It is also shown that the second algorithm mentioned finds a solution with probability approaching one for a wide range of parameter values.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 28

   Probabilistic Analysis of' a Generdization of the Unit Clause Literal Selection Heuristic for the ksatisfiability Problem

Ming-Te Chao

     
Case Weatern Reserve University Department of Computer Engineering and Science Cleveland, 08 44106

and

      John h c o Indiaaa University
Department of Computer Science Bloomington,
IN 47405

TECHNICAL REPORT NO. 165

 Probabilistic Analysis of a Generalization of the Unit Clause Literal Selection Heuristic for the ksatisfiability Problem

Ming-Te Chao, Case Western Reserve University

and John h c o , Indiana University

January, 19115

This material is brued on work supported by the U.S. Air Force under grant number AFOSR-840372.

[This page contains 1 picture or other non-text object]

Page 2 of 28

[This page contains 1 picture or other non-text object]

Page 3 of 28

ABSTRACT

   Two algorithm for the k-Satiefiabiity problem are prerrented and a probabii tic analysis is performed. The analysis ir, basedl on an instance distribution which is parameterised to simulate a variety of sample characteristics. The algorithms aaaign dueu to literals appearing in a given instance of k-Satisfiability, one at a time, until a solution is found or it is discovered that further assignments cannot lead to finding a solution. One algorithm tho- the next literal from a unit clause if one exists and randomly from the eet of remaining literals otherwise. The other algorithm u w a generaliaation of the Unit-Clause rule as a heuristic for selecting the next literal: at each step a literal is choeen randomly from a clause containing the least number of literals. The algorithms run in polynomial time and it ia shown that they find a solution to a random instance of k-Satisfiabiility with probability bounded from below by a constant greater than sero for two different rangea of parameter values. It is also shown that the second algorithm mentioned finds a solution with probability approaching one for a wide range of parameter values.

[This page contains 1 picture or other non-text object]

Page 4 of 28

[This page contains 1 picture or other non-text object]

Page 5 of 28

1. Introduction

This paper is concerned with the probabilistic performance of henristia for the k-Satisfiability problem (k-SAT). &-SAT is the problem of determining whether all
of a collection of k-literal disjunctiom (claw) of Boolean variablea are true for some truth awignment to the variablea. Thb problem b NP-complete ao there is
no known polynomial time algorithm for solving it. &-SAT ia a rpecial cam of the Satidability problem (SAT) which b the problem of determining whether all of a collection of disjunctions of Boolean dablea am true for some truth dgnment to the variables.

   The analyais is based on an equally likely instance distribution which has been used in other studiea of algorithm for thh problem. Thir model hm two paramt- tens in addition t...