Abstract | ||
---|---|---|
In this paper, we investigate the Probabilistic Satisfiability Problem, and its relation with the classical Satisfiability
Problem, looking for a possible polynomial-time reduction. For this, we present an Atomic Normal Form to the probabilistic
satisfiability problem and then we define a Probabilistic Entailment relation, showing its inherent properties. At the end,
we enunciate and refute a conjecture that could lead to the desired polynomial-time reduction.
|
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-16138-4_30 | Brazilian Symposium on Artificial Intelligence |
Keywords | Field | DocType |
probabilistic satisfiability,probabilistic entailment relation,probabilistic satisfiability problem,polynomial-time reduction,probabilistic logic,inherent property,atomic normal form,classical satisfiability problem,probabilistic satisfiability.,possible polynomial-time reduction,polynomial time,satisfiability,normal form | Computer science,Satisfiability,Probabilistic CTL,Theoretical computer science,Artificial intelligence,Probabilistic argumentation,Probabilistic logic,Conjecture,Maximum satisfiability problem,Boolean satisfiability problem,Algorithm,Probabilistic analysis of algorithms,Machine learning | Conference |
Volume | ISSN | ISBN |
6404 | 0302-9743 | 3-642-16137-5 |
Citations | PageRank | References |
1 | 0.35 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marcelo Finger | 1 | 365 | 48.82 |
Glauber de Bona | 2 | 31 | 6.59 |