Informatics Report Series
|
|
|
|
|
|
Title:Does SAT Exhibit Fractal Behavior? |
Authors:
Grant Passmore
; Joost Joosten
|
Date:Oct 2008 |
Publication Title:Institute for Logic, Language and Computation Research Report, University of Amsterdam |
Publisher:ILLC, Amsterdam |
Publication Type:Other
Publication Status:Pre-print
|
|
|
- Abstract:
-
In this paper we study the structure of the set SAT of all satisfiable propositional logical formulas. In particular we raise the question whether the distribution of SAT within the set A of all propositional formulas exhibits fractal behavior. This answer is of course relative to a metric on A. We show that for one such metric there is strong evidence that the distribution does indeed behave wildly. Next we look at an alternative metric.
- Links To Paper
- 1st Link
- Bibtex format
- @Misc{EDI-INF-RR-1310,
- author = {
Grant Passmore
and Joost Joosten
},
- title = {Does SAT Exhibit Fractal Behavior?},
- publisher = {ILLC, Amsterdam},
- year = 2008,
- month = {Oct},
- url = {http://homepages.inf.ed.ac.uk/s0793114/joosten-passmore-sat-fractal-behavior.pdf},
- note = {Institute for Logic, Language and Computation Research Report, University of Amsterdam},
- }
|