English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Bottleneck behavior in CNF formulas

Hoffmann, J., Gomes, C., & Selman, B.(2005). Bottleneck behavior in CNF formulas (MPI-I-2005-2-001). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Files

show Files
hide Files
:
MPI-I-2005-2-001.ps (Any fulltext), 471KB
Name:
MPI-I-2005-2-001.ps
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/postscript / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Hoffmann, Jörg1, Author           
Gomes, Carla2, Author
Selman, Bart2, Author
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: Recent research has revealed that CNF formulas encoding applications often contain very small backdoors, i.e. subsets of variables branching over which suffices to decide satisfiability with a DPLL procedure. We shed light on what kinds of problem structure {\em cause} the existence of such small backdoors. We examine carefully crafted synthetic domains, clean enough to allow a rigorous analysis of DPLL search spaces, yet meaningful enough to allow conclusions about more practical domains. The synthetic CNF encodings are parameterized not only in their size, but also by a structure parameter controlling the extent of an intuitive bottleneck behavior in the underlying task. We investigate the size of the smallest possible backdoors as a function of the structure parameter. We prove upper bounds that, in certain cases, decrease {\em exponentially} in that parameter. We empirically verified the upper bounds as lower bounds in formulas small enough for full empirical exploration, and we conjecture that the upper bounds are exact in general. We present empirical results indicating that our notion of bottleneck behavior is relevant not only in our synthetic domains, but also in more practical domains.

Details

show
hide
Language(s): eng - English
 Dates: 2005
 Publication Status: Issued
 Pages: 35 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2005-2-001
Report Nr.: MPI-I-2005-2-001
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -