Index Catalog // Carleton University Institutional Repository

This site uses cookies to offer you a better browsing experience. Find out more on how we use cookies and how you can change your settings.

Start Over

Filtering by: Date Created 1996 Publisher Springer Berlin Heidelberg

Approximating the unsatisfiability threshold of random formulas: (Extended abstract)

Resource Type:

Conference Proceeding

Creator:

Krizanc, Danny, Kranakis, Evangelos, and Kirousis, Lefteris M.

Abstract:

Let φ be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number such that if the ratio of the number of clauses over the number of variables of φ strictly exceeds κ, then φ is almost certainly unsatisfiable. By a well known and more or less straightforward argument, it can be shown that κ 3.

Date Created:

1996-01-01