Simple random logic programs

Gayathri Namasivayam, Mirosław Truszczyński

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations


We consider random logic programs with two-literal rules and study their properties. In particular, we obtain results on the probability that random "sparse" and "dense" programs with two-literal rules have answer sets. We study experimentally how hard it is to compute answer sets of such programs. For programs that are constraint-free and purely negative we show that the easy-hard-easy pattern emerges. We provide arguments to explain that behavior. We also show that the hardness of programs from the hard region grows quickly with the number of atoms. Our results point to the importance of purely negative constraint-free programs for the development of ASP solvers.

Original languageEnglish
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 10th International Conference, LPNMR 2009, Proceedings
Number of pages13
StatePublished - 2009
Event10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009 - Potsdam, Germany
Duration: Sep 14 2009Sep 18 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5753 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Simple random logic programs'. Together they form a unique fingerprint.

Cite this