Name
Abstract | ||
|---|---|---|
Let Γ be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in Γ is in LOGSPACE or complete for the class CSP(Γ)NP under deterministic polynomial-time many-one reductions. Here, CSP(Γ)NP is the class of problems that can be reduced to the constraint satisfaction problem of Γ under non-deterministic polynomial-time many-one reductions. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-03073-4_4 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
class csp,constraint satisfaction problems,deterministic polynomial-time many-one reduction,existential positive first-order logic,constraint satisfaction problem,non-deterministic polynomial-time many-one reduction,finite relational signature,computational complexity,existential positive sentence,polynomial time,first order logic | Journal | 23 |
Issue | ISSN | Citations |
4 | 0955-792X | 3 |
PageRank | References | Authors |
0.48 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manuel Bodirsky | 1 | 644 | 54.63 |
| Miki Hermann | 2 | 382 | 27.84 |
| Florian Richoux | 3 | 81 | 6.99 |