Approximating the stable model semantics is hard

Georg Gottlob; Mirosław Truszczyński

doi:10.3233/fi-1996-281207

Approximating the stable model semantics is hard

Georg Gottlob, Mirosław Truszczyński

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we investigate the complexity of problems concerned with approximating the stable model semantics. We show that under rather weak assumptions it is NP-hard to decide whether the size of a polynomially computable approximation is within a constant factor from the size of the intersection (union) of stable models of a program. We also show that unless P=NP, no approximation exists that uniformly bounds the intersection (union) of stable models.

Original language	English
Pages (from-to)	123-128
Number of pages	6
Journal	Fundamenta Informaticae
Volume	28
Issue number	1-2
DOIs	https://doi.org/10.3233/fi-1996-281207
State	Published - Nov 1996

Keywords

Computational complexity
Logic programming
Stable models
Well-founded semantics

ASJC Scopus subject areas

Theoretical Computer Science
Algebra and Number Theory
Information Systems
Computational Theory and Mathematics

Access to Document

10.3233/fi-1996-281207

Cite this

@article{294cb25860bb49b4ae6469ca19899e18,

title = "Approximating the stable model semantics is hard",

abstract = "In this paper we investigate the complexity of problems concerned with approximating the stable model semantics. We show that under rather weak assumptions it is NP-hard to decide whether the size of a polynomially computable approximation is within a constant factor from the size of the intersection (union) of stable models of a program. We also show that unless P=NP, no approximation exists that uniformly bounds the intersection (union) of stable models.",

keywords = "Computational complexity, Logic programming, Stable models, Well-founded semantics",

author = "Georg Gottlob and Miros{\l}aw Truszczy{\'n}ski",

year = "1996",

month = nov,

doi = "10.3233/fi-1996-281207",

language = "English",

volume = "28",

pages = "123--128",

number = "1-2",

}

TY - JOUR

T1 - Approximating the stable model semantics is hard

AU - Gottlob, Georg

AU - Truszczyński, Mirosław

PY - 1996/11

Y1 - 1996/11

N2 - In this paper we investigate the complexity of problems concerned with approximating the stable model semantics. We show that under rather weak assumptions it is NP-hard to decide whether the size of a polynomially computable approximation is within a constant factor from the size of the intersection (union) of stable models of a program. We also show that unless P=NP, no approximation exists that uniformly bounds the intersection (union) of stable models.

AB - In this paper we investigate the complexity of problems concerned with approximating the stable model semantics. We show that under rather weak assumptions it is NP-hard to decide whether the size of a polynomially computable approximation is within a constant factor from the size of the intersection (union) of stable models of a program. We also show that unless P=NP, no approximation exists that uniformly bounds the intersection (union) of stable models.

KW - Computational complexity

KW - Logic programming

KW - Stable models

KW - Well-founded semantics

UR - http://www.scopus.com/inward/record.url?scp=0030282516&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030282516&partnerID=8YFLogxK

U2 - 10.3233/fi-1996-281207

DO - 10.3233/fi-1996-281207

M3 - Article

AN - SCOPUS:0030282516

SN - 0169-2968

VL - 28

SP - 123

EP - 128

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

IS - 1-2

ER -

Approximating the stable model semantics is hard

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this