scientific article; zbMATH DE number 1142309

Number-theoretic algorithms; complexity (11Y16) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Cryptography (94A60)

Cited in

(only showing first 100 items - show all)

Symmetries and the complexity of pure Nash equilibrium
From a zoo to a zoology: Towards a general theory of graph polynomials
A survey on the complexity of tournament solutions
On the complexity of Slater's problems
The computational complexity of ideal semantics
A refined architecture for terminological systems: Terminology = Schema + Views
State-variable planning under structural restrictions: algorithms and complexity
Matching theory -- a sampler: From Dénes König to the present
On the complexity of propositional knowledge base revision, updates, and counterfactuals
On the computational complexity of reconstructing lattice sets from their X-rays
Succinctness as a source of complexity in logical formalisms
The complexity of propositional closed world reasoning and circumscription
Cumulative default logic: Finite characterization, algorithms, and complexity
On the complexity of some basic problems in computational convexity. I. Containment problems
Multiple total stable models are definitely needed to solve unique solution problems
On the complexity of partially observed Markov decision processes
On the computational complexity of graph closures
On the language of primitive words
The expressive powers of stable models for bound and unbound DATALOG queries
The complexity of concept languages
The forbidden projections of unate functions
On randomized versus deterministic computation
The complexity of query evaluation in indefinite temporal constraint databases
Query languages for bags and aggregate functions
On compact representations of propositional circumscription
Is intractability of nonmonotonic reasoning a real drawback?
Queries with arithmetical constraints
McNaughton families of languages.
Complexity of some problems in positive and related calculi
Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.
Reducing belief revision to circumscription (and vice versa)
Semantics and complexity of abduction from default theories
The complexity of belief update
Default reasoning from conditional knowledge bases: Complexity and tractable cases
On scheduling send-graphs and receive-graphs under the LogP-model
On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
On the algorithmic inversion of the discrete Radon transform
A note on unambiguous function classes
Rational analysis, intractability, and the prospects of `as if'-explanations
Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
Extension and equivalence problems for clause minimal formulae
Minimal temporal epistemic logic
A probabilistic approach to navigation in Hypertext
Complexity results for structure-based causality.
Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
An algebra for pomsets.
Complexity and expressive power of deterministic semantics for DATALOG^ .
Unification algorithms cannot be combined in polynomial time.
Preprocessing of intractable problems
Functional queries in datalog
Precise interprocedural dependence analysis of parallel programs
Finite-state dimension
A decision method for nonmonotonic reasoning based on autoepistemic reasoning
Largest \(j\)-simplices in \(n\)-polytopes
On the geometric separability of Boolean functions
Arity and alternation in second-order logic
The intrinsic difficulty of recursive functions
On the computational cost of disjunctive logic programming: Propositional case
Small space analogues of Valiant's classes and the limitations of skew formulas
HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
Data independence of read, write, and control structures in PRAM computations
Using temporal logics to express search control knowledge for planning
On the decidability and complexity of reasoning about only knowing
Towards efficient universal planning: A randomized approach
The size of a revised knowledge base
On the complexity of inference about probabilistic relational models
Cook's versus Valiant's hypothesis
Combining experts' causal judgments
Inconsistency-tolerant query answering for existential rules
On timeline-based games and their complexity
Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting
Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
Solving abduction by computing joint explanations. Logic programming formalization, applications to P2P data integration, and complexity results
Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
Expressive probabilistic description logics
Combining answer set programming with description logics for the semantic web
Outlier detection using default reasoning
A PTIME-complete matching problem for SLP-compressed words
A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
Complexity results for answer set programming with bounded predicate arities and implications
On the computational complexity of coalitional resource games
Weak nonmonotonic probabilistic logics
New tractable classes for default reasoning from conditional knowledge bases
A split-combination approach to merging knowledge bases in possibilistic logic
More results on the complexity of identifying problems in graphs
Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting
Probably approximately optimal satisficing strategies
The complexity of searching implicit graphs
A lattice-based McEliece scheme for encryption and signature
The complexity of the nucleolus in compact games
Monotonic extensions of Petri nets: forward and backward search revisited
Revisiting a result of Ko
FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
The complexity of one-agent refinement modal logic
Parallel approximation algorithms for maximum weighted matching in general graphs
Expressivity and complexity of MongoDB queries
The Computational Complexity of Choice Sets
Strategic Agent Communication: An Argumentation-Driven Approach
Resource trade-offs in syntactically multilinear arithmetic circuits

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4385525)