scientific article; zbMATH DE number 1142309
From MaRDI portal
Publication:4385525
zbMath0900.68246MaRDI QIDQ4385525
Publication date: 4 May 1998
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, On randomized versus deterministic computation, On the synchronization of semi-traces, The complexity class θp2: Recent results and applications in AI and modal logic, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, Solving abduction by computing joint explanations. Logic programming formalization, applications to P2P data integration, and complexity results, The Complexity of One-Agent Refinement Modal Logic, Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\), A split-combination approach to merging knowledge bases in possibilistic logic, 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 PARALLEL BEST-FIRST B&B ALGORITHM AND ITS AXIOMATIZATION, Unnamed Item, On the complexity of graph reconstruction, The expressive power of unique total stable model semantics, 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 preference aggregation over \((m)\)CP-nets: max and rank voting, Expressivity and Complexity of MongoDB Queries, The complexity of graph connectivity, Probably approximately optimal satisficing strategies, The complexity of searching implicit graphs, Linear constraint query languages expressive power and complexity, Some rainbow problems in graphs have complexity equivalent to satisfiability problems, Lower complexity bounds for lifted inference, Complexity results for answer set programming with bounded predicate arities and implications, The complexity of counting problems in equational matching, On the computational complexity of coalitional resource games, Weak nonmonotonic probabilistic logics, Complexity and compilability of diagnosis and recovery of graph-based systems, Voting Procedures, Complexity of, The complexity of searching succinctly represented graphs, Unification algorithms cannot be combined in polynomial time, Unnamed Item, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Unnamed Item, Belief revision and update: Complexity of model checking, The computational power of parsing expression grammars, New tractable classes for default reasoning from conditional knowledge bases, Strategic Agent Communication: An Argumentation-Driven Approach, Computing LOGCFL certificates, The asymmetric median tree. --- A new model for building consensus trees, Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete, The Computational Complexity of Choice Sets, The Complexity of the Nucleolus in Compact Games, A uniform tableaux method for nonmonotonic modal logics, Uniform Constraint Satisfaction Problems and Database Theory, More results on the complexity of identifying problems in graphs, Probabilistic logic under coherence: complexity and algorithms, The complexity of propositional closed world reasoning and circumscription, Inconsistency-tolerant query answering for existential rules, Revisiting a result of Ko, Cumulative default logic: Finite characterization, algorithms, and complexity, Precise interprocedural dependence analysis of parallel programs, Finite-state dimension, Parallel approximation algorithms for maximum weighted matching in general graphs, On the complexity of constrained Nash equilibria in graphical games, On the complexity of some basic problems in computational convexity. I. Containment problems, A decision method for nonmonotonic reasoning based on autoepistemic reasoning, Largest \(j\)-simplices in \(n\)-polytopes, 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, Attribute value reordering for efficient hybrid OLAP, 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, Algorithmic uses of the Feferman-Vaught theorem, On the geometric separability of Boolean functions, Query languages for bags and aggregate functions, Resource trade-offs in syntactically multilinear arithmetic circuits, Arity and alternation in second-order logic, The intrinsic difficulty of recursive functions, Weighted hypertree decompositions and optimal query plans, Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: complexity, algorithms, and implementation, On the computational cost of disjunctive logic programming: Propositional case, A refined architecture for terminological systems: Terminology = Schema + Views, State-variable planning under structural restrictions: algorithms and complexity, Magic Sets and their application to data integration, 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, Small space analogues of Valiant's classes and the limitations of skew formulas, Rational analysis, intractability, and the prospects of `as if'-explanations, Detecting and repairing anomalous evolutions in noisy environments. Logic programming formalization and complexity results, HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, On the complexity of core, kernel, and bargaining set, Restricted default theories: expressive power and outlier detection tasks, Unique (optimal) solutions: complexity results for identifying and locating-dominating codes, Typechecking top-down XML transformations: Fixed input or output schemas, 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, On 2-QBF truth testing in parallel, Conjunctive query containment with respect to views and constraints, Multilist layering: Complexity and applications, Undoing the effects of action sequences, Removing redundancy from a clause, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, Matching theory -- a sampler: From Dénes König to the present, On the complexity of propositional knowledge base revision, updates, and counterfactuals, Deciding uniqueness in norm maximazation, A string-matching algorithm for the CREW PRAM, Hypertree decompositions and tractable queries, Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}, Extension and equivalence problems for clause minimal formulae, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Symmetries and the complexity of pure Nash equilibrium, Combining experts' causal judgments, The complexity of one-agent refinement modal logic, From a zoo to a zoology: Towards a general theory of graph polynomials, Minimal temporal epistemic logic, On timeline-based games and their complexity, A probabilistic approach to navigation in Hypertext, Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting, The complexity of belief update, A survey on the complexity of tournament solutions, On the complexity of Slater's problems, The computational complexity of ideal semantics, On the computational complexity of reconstructing lattice sets from their \(X\)-rays, Succinctness as a source of complexity in logical formalisms, Default reasoning from conditional knowledge bases: Complexity and tractable cases, 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\(^ \neg\)., Unification algorithms cannot be combined in polynomial time., Preprocessing of intractable problems, Functional queries in datalog, 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, Complexity results for explanations in the structural-model approach, On the computational complexity of qualitative coalitional games
