The complexity class θp2: Recent results and applications in AI and modal logic
From MaRDI portal
Publication:5055917
DOI10.1007/BFb0036168WikidataQ59259757 ScholiaQ59259757MaRDI QIDQ5055917
Publication date: 9 December 2022
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Modal logic (including the logic of norms) (03B45) Logic in artificial intelligence (68T27) Logic programming (68N17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Related Items
A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison, The complexity of computing minimal unidirectional covering sets, Mixed Iterated Revisions: Rationale, Algorithms, and Complexity, Solving conflicts in information merging by a flexible interpretation of atomic propositions, Unnamed Item, On the complexity of data disjunctions.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing functions with parallel queries to NP
- \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
- Henkin quantifiers and complete problems
- The complexity of optimization problems
- More complicated questions about maxima and minima, and some closures of NP
- A logic for default reasoning
- On truth-table reducibility to SAT
- Bounded queries to SAT and the Boolean hierarchy
- On the complexity of propositional knowledge base revision, updates, and counterfactuals
- Preferred answer sets for extended logic programs
- Zero-one laws for modal logic
- Querying disjunctive databases through nonmonotonic logics
- Abduction from logic programs: Semantics and complexity
- The complexity of default reasoning under the stationary fixed point semantics
- Equivalence of NC\(^ k\) and AC\(^{k-1}\) closures of NP and other classes
- Constant Depth Reducibility
- Bounded Query Classes
- Second order logic and the weak exponential hierarchies
- RelativizedNC
- The Boolean Hierarchy I: Structural Properties
- Complexity Results for Nonmonotonic Logics
- Probabilities on finite models
- Relativization of questions about log space computability
- The complexity of logic-based abduction
- NP trees and Carnap's modal logic
- Capturing Relativized Complexity Classes without Order
- Characterizations of some complexity classes between Θ2p and Δ2p
