scientific article
From MaRDI portal
Publication:3221403
zbMath0557.68033MaRDI QIDQ3221403
Publication date: 1985
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexitytheory of computationpolynomial hierarchycomplexity classesannotated bibliography
Analysis of algorithms and problem complexity (68Q25) Bibliographies for mathematics in general (00A15)
Related Items
The role of polymorphism in the characterisation of complexity by soft types, Collapse of PP with a semi-random source to BPP, It is hard to know when greedy is good for finding independent sets, A characterization of the leaf language classes, Languages represented by Boolean formulas, Reasoning about coalitional games, Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\), A natural family of optimization problems with arbitrarily small approximation thresholds, Ranking games, Complexity of counting the optimal solutions, Nondeterministic functions and the existence of optimal proof systems, The complexity of weighted Boolean \#CSP with mixed signs, The structure and complexity of Nash equilibria for a selfish routing game, The complexity of constraint satisfaction games and QCSP, Backward and forward bisimulation minimization of tree automata, Even faster integer multiplication, Computational complexity of queries based on itemsets, The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria, Non-confluence in divisionless P systems with active membranes, Computing equilibria: a computational complexity perspective, An alternative approach for proving the NP-hardness of optimization problems, A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem, Approximability of single machine scheduling with fixed jobs to minimize total completion time, Coloring some classes of mixed graphs, Approximation of min-max and min-max regret versions of some combinatorial optimization problems, Computing phylogenetic roots with bounded degrees and errors is NP-complete, The complexity of tree automata and XPath on grammar-compressed trees, Reasoning under minimal upper bounds in propositional logic, On neighborhood-Helly graphs, Towards more expressive ontology languages: the query answering problem, On unique graph 3-colorability and parsimonious reductions in the plane, Searching in random partially ordered sets, Graph properties checkable in linear time in the number of vertices, Complexity-style resources in cryptography, Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension, Model-checking hierarchical structures, Equilibria of graphical games with symmetries, QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images, The set of parameterized \(k\)-covers problem, \textsc{Inverse Hamiltonian cycle} and inverse \textsc{3Dimensional matching} are coNP-complete, Asynchronous P systems with active membranes, Minimum sum set coloring of trees and line graphs of trees, On the complexity of enumerating pseudo-intents, Manipulating the quota in weighted voting games, On the complexity of reconfiguration problems, Model checking in the modal \(\mu \)-calculus and generic solutions, Two complexity results on \(c\)-optimality in experimental design, Most probable explanations in Bayesian networks: complexity and tractability, Cyclic Boolean circuits, The complexity of surjective homomorphism problems-a survey, Graph clustering, Solving conflicts in information merging by a flexible interpretation of atomic propositions, On the complexity of core, kernel, and bargaining set, Guarantees and limits of preprocessing in constraint satisfaction and reasoning, Finding explanations of inconsistency in multi-context systems, Probabilistic analysis of a differential equation for linear programming, The complexity of equivalence, entailment, and minimization in existential positive logic, Message-passing algorithms for inference and optimization, Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods, Exploring the tractability border in epistemic tasks, Strong conflict-free coloring for intervals, Verification in incomplete argumentation frameworks, Approximate solution of NP optimization problems, If NP has polynomial-size circuits, then MA=AM, Complexity of rainbow vertex connectivity problems for restricted graph classes, On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data, On the computational power of networks of polarized evolutionary processors, Computational complexity of finite asynchronous cellular automata, On the complexity of propositional and relational credal networks, Parametric runtime verification is NP-complete and coNP-complete, A study on monotone self-dual Boolean functions, On the expression complexity of equivalence and isomorphism of primitive positive formulas, Mediated population protocols, On the complexity of computing winning strategies for finite poset games, Metric structures and probabilistic computation, Weighted argument systems: basic definitions, algorithms, and complexity results, Belief extrapolation (or how to reason about observations and unpredicted change), Disjunction property and complexity of substructural logics, Stack size analysis for interrupt-driven programs, Leaf languages and string compression, Complexity of clique coloring and related problems, Consensus algorithms for the generation of all maximal bicliques, Logical aspects of Cayley-graphs: the group case, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT, XML queries and constraints, containment and reformulation, Machine-based methods in parameterized complexity theory, A universal scaling theory for complexity of analog computation, Mean-payoff games and propositional proofs, Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections, Counting and sampling SCJ small parsimony solutions, The complexity of relating quantum channels to master equations, The no-wait flow-shop paradox, A logic programming approach to knowledge-state planning. II: The DLV\(^\mathcal K\) system, Contingent planning under uncertainty via stochastic satisfiability, Enhancing disjunctive logic programming systems by SAT checkers, Complexity results for explanations in the structural-model approach, \(\text{DA}^2\) merging operators, On the computational complexity of qualitative coalitional games, Group coloring is \(\Pi_2^{\text{P}}\)-complete, Games with winning conditions of high Borel complexity, On the complexity of the parity argument and other inefficient proofs of existence, Default theories that always have extensions, Recursion theory on the reals and continuous-time computation, Multiple total stable models are definitely needed to solve unique solution problems, On approximation algorithms for the minimum satisfiability problem, On resource-bounded instance complexity, Inferring a tree from walks, The complexity of membership problems for circuits over sets of integers, Performance improvement for the GGM-construction of pseudorandom functions, Derivability in certain subsystems of the logic of proofs is \(\Pi_2^p\)-complete, Expressiveness and complexity of graph logic, Can datalog be approximated?, Predicting nonlinear cellular automata quickly by decomposing them into linear ones, Complexity of searching an immobile hider in a graph, Circumscribing DATALOG: expressive power and complexity, Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: complexity, algorithms, and implementation, Dynamical recognizers: real-time language recognition by analog computers, Abduction from logic programs: Semantics and complexity, On computational complexity of contextual languages, Verification of relational transducers for electronic commerce, An oracle builder's toolkit, Ancestors, descendants, and gardens of Eden in reaction systems, Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy., On the expressivity and complexity of quantitative branching-time temporal logics, Complexity of some problems in positive and related calculi, Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules, The complexity of power indexes with graph restricted coalitions, A concept for the evolution of relational probabilistic belief states and the computation of their changes under optimum entropy semantics, A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT., Further hardness results on rainbow and strong rainbow connectivity, Non-approximability of precedence-constrained sequencing to minimize setups., Optimal satisfiability for propositional calculi and constraint satisfaction problems., Jug measuring: algorithms and complexity, On the algebraic complexity of some families of coloured Tutte polynomials, Turing machines and bimachines, Complexity of unique list colorability, Reversal complexity revisited, Computing the minimal covering set, Partition into cliques for cubic graphs: Planar case, complexity and approximation, Computational complexity of determining which statements about causality hold in different space-time models, The complexity of the weight problem for permutation and matrix groups., On the complexity of partial order trace model checking, On the counting complexity of propositional circumscription, Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete, Conformant plans and beyond: principles and complexity, An approximation trichotomy for Boolean \#CSP, Playing monotone games to understand learning behaviors, Logical and algorithmic properties of stable conditional independence, Satisfiability of algebraic circuits over sets of natural numbers, A simplified way of proving trade-off results for resolution, The complexity of propositional implication, Disjunctive merging: quota and Gmin merging operators, Quasilinear cellular automata, Imitation games and computation, On small, reduced, and fast universal accepting networks of splicing processors, Symmetries and the complexity of pure Nash equilibrium, Space complexity of abelian groups, The consequence relation in the logic of commutative GBL-algebras is PSPACE-complete, A new connection between quantum circuits, graphs and the Ising partition function, On the subgroup distance problem., The complexity of computing the Muirhead-Dalton distance, Quantum zero-error algorithms cannot be composed, The complexity of clique graph recognition, The parallel complexity of signed graphs: Decidability results and an improved algorithm, Adjacency on the constrained assignment problem, Reflective relational machines, Succinct representation, leaf languages, and projection reductions, Alphabet indexing for approximating features of symbols, Haplotype inferring via galled-tree networks using a hypergraph covering problem for special genotype matrices, Expressive power and complexity of partial models for disjunctive deductive databases, Bounding queries in the analytic polynomial-time hierarchy, Relating polynomial time to constant depth, A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses, On the algebraic structure of combinatorial problems, On the approximability of the maximum agreement subtree and maximum compatible tree problems, On the complexity of constructing Golomb rulers, Weighted coloring on planar, bipartite and split graphs: Complexity and approximation, Computational properties of argument systems satisfying graph-theoretic constraints, Exploiting functional dependencies in declarative problem specifications, Sequences, datalog, and transducers, Spreading messages, Some APX-completeness results for cubic graphs, Storage controlled pile-up systems, theoretical foundations, Circuits and expressions with nonassociative gates, Positive versions of polynomial time, On the approximability of the Steiner tree problem in phylogeny, Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Optical computing, Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics, Semantical and computational aspects of Horn approximations, A complexity analysis of bisimilarity for value-passing processes, Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application, Polynomial time samplable distributions, The computational complexity of ideal semantics, Mind change optimal learning of Bayes net structure from dependency and independency data, Temporal connectives versus explicit timestamps to query temporal databases, Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, Cut and paste, Bridging the Gap Between Neurons and Cognition Through Assemblies of Neurons, A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols, Efficient timed model checking for discrete-time systems, A Short Introduction to Implicit Computational Complexity, Drawing interactive Euler diagrams from region connection calculus specifications, Computing equality-free and repetitive string factorisations, Mean-payoff games with partial observation, On the connectivity preserving minimum cut problem, A resource portfolio planning model using sampling-based stochastic programming and genetic algorithm, Random matrix theory for the analysis of the performance of an analog computer: a scaling theory, Solving abduction by computing joint explanations. Logic programming formalization, applications to P2P data integration, and complexity results, Two situations with unit-cost: ordered abelian semi-groups and some commutative rings, Supermodular functions and the complexity of MAX CSP, Inverse monoids: decidability and complexity of algebraic questions., Phase transitions of PP-complete satisfiability problems, Expressive probabilistic description logics, On propositional definability, Complexity results and algorithms for possibilistic influence diagrams, Maintenance goals of agents in a dynamic environment: formulation and policy construction, Combining answer set programming with description logics for the semantic web, A linear approximation method for the Shapley value, Outlier detection using default reasoning, Characterising the complexity of tissue P systems with fission rules, A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison, An efficient time-free solution to QSAT problem using P systems with proteins on membranes, From model checking to equilibrium checking: reactive modules for rational verification, Measuring inconsistency with many-valued logics, Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability, A full computation-relevant topological dynamics classification of elementary cellular automata, Complexity of the dynamics of reaction systems, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Limitations of Restricted Branching in Clause Learning, Shallow Non-confluent P Systems, Space complexity equivalence of P systems with active membranes and Turing machines, Scaling and universality of the complexity of analog computation, A Characterisation of NL Using Membrane Systems without Charges and Dissolution, RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC!, Polynomial hierarchy graph properties in hybrid logic, The Undecidability of the Domino Problem, Complexity theory for splicing systems, On the fairness and complexity of generalized \(k\)-in-a-row games, Out of order quantifier elimination for standard quantified linear programs, On the computational complexity of coalitional resource games, Solving logic program conflict through strong and weak forgettings, Automated reformulation of specifications by safe delay of constraints, Weak nonmonotonic probabilistic logics, On the logic of cooperation and propositional control, On the consistency of cardinal direction constraints, On the Decomposition of Abstract Dialectical Frameworks and the Complexity of Naive-based Semantics, Computation of best possible low degree expanders, Reasoning in description logics by a reduction to disjunctive datalog, An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection, On the complexity of non-unique probe selection, Higher-dimensional 3-adic CM construction, 3-Color Bounded Patterned Self-assembly, Interval-valued computations and their connection with PSPACE, Open Problems in Abstract Argumentation, Asymptotic expected number of Nash equilibria of two-player normal form games, GRADIENT FLOWS FOR OPTIMIZATION IN QUANTUM INFORMATION AND QUANTUM DYNAMICS: FOUNDATIONS AND APPLICATIONS, Reductions, completeness and the hardness of approximability, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Controlling the losing probability in a monotone game, Computing best-possible bounds for the distribution of a sum of several variables is NP-hard, Designing PTASs for MIN-SUM scheduling problems, On certain connectivity properties of the internet topology, Solving coalitional resource games, Bounded treewidth as a key to tractability of knowledge representation and reasoning, A parametric analysis of the state-explosion problem in model checking, Limitations of restricted branching in clause learning, How much can analog and hybrid systems be proved (super-)Turing, On complexity of verification of interacting agents' behavior, \(\text{BTL}_{2}\) and the expressive power of \(\text{ECTL}^{+}\), Compact bidding languages and supplier selection for markets with economies of scale and scope, Minimum sum multicoloring on the edges of trees, Computational aspects of mining maximal frequent patterns, Iterative Equitable Partition of Graph as a Model of Constant Structure Discrete Time Closed Semantic System, Most frugal explanations in Bayesian networks, Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value, Optimizing social welfare in social networks, How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge, PSYSTEMS WITH ACTIVE MEMBRANES WORKING IN POLYNOMIAL SPACE, The Computational Complexity of Quantified Reciprocals, Monodirectional P systems, Complexity of intuitionistic propositional logic and its fragments, Packing Arc-Disjoint Cycles in Tournaments, Efficient Reasoning for Inconsistent Horn Formulae, Structure and complexity of extreme Nash equilibria, Games for complexity of second-order call-by-name programs, On the dimension of simple monotonic games, Computational efficiency of dissolution rules in membrane systems, A common algebraic description for probabilistic and quantum computations, The complexity of multi-mean-payoff and multi-energy games, The complexity of string partitioning, Constructing NP-intermediate problems by blowing holes with parameters of various properties, Revealed preference tests for weak separability: an integer programming approach, Information retrieval with unambiguous output, On the entropy of couplings, Complexity and approximation of the smallest \(k\)-enclosing ball problem, Lemmings is PSPACE-complete, Algorithms yield upper bounds in differential algebra, Graphical representation and hierarchical decomposition mechanism for vertex-cover solution space, Sparsity promoting decentralized learning strategies for radio tomographic imaging using consensus based ADMM approach, The possible winner with uncertain weights problem, Stability, vertex stability, and unfrozenness for special graph classes, Well-founded coalgebras, revisited, A CLASS OF EFFICIENT QUANTUM INCREMENTER GATES FOR QUANTUM CIRCUIT SYNTHESIS, A survey of computational complexity results in systems and control, Counting and Gröbner bases, On the difference of Horn theories, Min-max Computation Tree Logic, Approximation of some NP-hard optimization problems by finite machines, in probability, Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, Graph Ramsey theory and the polynomial hierarchy, On the complexity of orthogonal compaction, Fast construction of irreducible polynomials over finite fields, EFFICIENT TESTING OF FORECASTS, Parallel dynamics and computational complexity of the Bak-Sneppen model, Counting over non-planar graphs, Exact learning of DNF formulas using DNF hypotheses, Dot operators, Computational complexity of some problems involving congruences on algebras, On the complexity of recognizing the Hilbert basis of a linear Diophantine system, Algorithm for optimal winner determination in combinatorial auctions, Consistency restoration and explanations in dynamic CSPs---Application to configuration, Statistical mechanics methods and phase transitions in optimization problems, Inapproximability of finding maximum hidden sets on polygons and terrains, Fingerprint clustering with bounded number of missing values, THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS, Counting and enumeration complexity with application to multicriteria scheduling, Computational Complexity of a Hybridized Horn Fragment of Halpern-Shoham Logic, Languages, Decidability, and Complexity, Some aspects of the database resilience, In search of an easy witness: Exponential time vs. probabilistic polynomial time., Computational complexity of optimization and crude range testing: A new approach motivated by fuzzy optimization, Hypothesis finding based on upward refinement of residue hypotheses., Learning elementary formal systems with queries., Describing parameterized complexity classes, Automatic graphs and D0L-sequences of finite graphs, Bounded MSC communication, Reasoning with power defaults, Linearisability on Datalog programs, Realizability of high-level message sequence charts: closing the gaps, Dichotomies for classes of homomorphism problems involving unary functions, On the complexity of inducing categorical and quantitative association rules, Precise interprocedural dependence analysis of parallel programs, On the computational complexity of 2-interval pattern matching problems, Counting and sampling \(H\)-colourings, The possible winner problem with uncertain weights revisited, Complexity of nonemptiness in control argumentation frameworks, The complexity and generality of learning answer set programs, Controlling weighted voting games by deleting or adding players with or without changing the quota, Minimal sets on propositional formulae. Problems and reductions, The first international competition on computational models of argumentation: results and analysis, The counting power of P systems with antimatter, Complexity of control in judgment aggregation for uniform premise-based quota rules, Lewis dichotomies in many-valued logics, A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging, Paired-bacteria optimiser -- a simple and fast algorithm, Automated competitive analysis of real-time scheduling with graph games, On the complexity of computing the temporal hybridization number for two phylogenies, Coherence and computational complexity of quantifier-free dependence logic formulas, Towards a dichotomy for the possible winner problem in elections based on scoring rules, New methods for 3-SAT decision and worst-case analysis, Simultaneous rigid E-unification and other decision problems related to the Herbrand theorem, Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs, Max NP-completeness made easy, Policy expressions and the bottom-up design of computing policies, On solutions and representations of spiking neural P systems with rules on synapses, Oracles and query lower bounds in generalised probabilistic theories, On some tractable classes in deduction and abduction, Towards efficient universal planning: A randomized approach, Copyless cost-register automata: structure, expressiveness, and closure properties, On the computational complexity of data flow analysis over finite bounded meet semilattices, Alternative space definitions for P systems with active membranes, Acceptance in incomplete argumentation frameworks, Control complexity in Borda elections: solving all open cases of offline control and some cases of online control, Proof techniques in membrane computing, Quantum walks: a comprehensive review, The P versus NP-complete dichotomy of some challenging problems in graph theory, Hardness results on the gapped consecutive-ones property problem, Patrolling security games: definition and algorithms for solving large instances with single patroller and single intruder, Augmenting tractable fragments of abstract argumentation, A well-structured framework for analysing Petri net extensions, On solving univariate sparse polynomials in logarithmic time, Optimal covering designs: complexity results and new bounds, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, Non-deterministic weighted automata evaluated over Markov chains, Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria, Uniformity of quantum circuit families for error-free algorithms, The complexity of base station positioning in cellular networks, Functions computable in polynomial space, Faster algorithms for computing power indices in weighted voting games, The effect of multi-sensor data on condition-based maintenance policies, Systematic mistakes are likely in bounded optimal decision-making systems, Computing the depth distribution of a set of boxes, Minimization and \(\mathbf{NP}\) multifunctions, Depth-two P systems can simulate Turing machines with \textbf{NP} oracles, Bypassing BDD construction for reliability analysis, Analog computation with dynamical systems, Default reasoning from conditional knowledge bases: Complexity and tractable cases, A model-theoretic characterization of the weak pigeonhole principle, Easy weighted majority games, Conjunctive-query containment and constraint satisfaction, On the computational complexity of assumption-based argumentation for default reasoning., Conditional independence in propositional logic., An information-based neural approach to generic constraint satisfaction., Complexity results for structure-based causality., How to analyse evolutionary algorithms., Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions., Computing with quanta -- impacts of quantum theory on computation., On the Hamming distance of constraint satisfaction problems., Propositional default logics made easier: computational complexity of model checking., Structural control in weighted voting games, Unification algorithms cannot be combined in polynomial time., Bounded queries, approximations, and the Boolean hierarchy, Some speed-ups and speed limits for real algebraic geometry, Techniques of replica symmetry breaking and the storage problem of the McCulloch-Pitts neuron, Survey of facial results for the traveling salesman polytope, Is your model checker on time? On the complexity of model checking for timed modal logics, Symbolic model checking of timed guarded commands using difference decision diagrams, A theory of complexity for continuous time systems, Quantum computing and quadratically signed weight enumerators, Quantified computation tree logic, On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology, Logic programming and knowledge representation---The A-Prolog perspective, Extending and implementing the stable model semantics, Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT, A very difficult scheduling problem with communication delays, Computational complexity of uniform quantum circuit families and quantum Turing machines, A note on unambiguous function classes, An efficient algorithm for a class of constraint satisfaction problems
