Publication:3221403
From MaRDI portal
zbMath0557.68033MaRDI QIDQ3221403
Publication date: 1985
computational complexity; theory of computation; polynomial hierarchy; complexity classes; annotated bibliography
68Q25: Analysis of algorithms and problem complexity
00A15: Bibliographies for mathematics in general
Related Items
THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS, 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, 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, Counting and enumeration complexity with application to multicriteria scheduling, On certain connectivity properties of the internet topology, A parametric analysis of the state-explosion problem in model checking, 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}^{+}\), Minimum sum multicoloring on the edges of trees, Computational aspects of mining maximal frequent patterns, Structure and complexity of extreme Nash equilibria, Games for complexity of second-order call-by-name programs, On the dimension of simple monotonic games, A common algebraic description for probabilistic and quantum computations, Inverse monoids: decidability and complexity of algebraic questions., Phase transitions of PP-complete satisfiability problems, Computational efficiency of dissolution rules in membrane systems, Limitations of Restricted Branching in Clause Learning, Scaling and universality of the complexity of analog computation, A Characterisation of NL Using Membrane Systems without Charges and Dissolution, The Computational Complexity of Quantified Reciprocals, XML queries and constraints, containment and reformulation, Machine-based methods in parameterized complexity theory, 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, Approximate solution of NP optimization problems, If NP has polynomial-size circuits, then MA=AM, Stack size analysis for interrupt-driven programs, 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, 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, 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, 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, Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: complexity, algorithms, and implementation, Jug measuring: algorithms and complexity, 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, 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, Haplotype inferring via galled-tree networks using a hypergraph covering problem for special genotype matrices, 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, Spreading messages, Circumscribing DATALOG: expressive power and complexity, Dynamical recognizers: real-time language recognition by analog computers, Adjacency on the constrained assignment problem, Reflective relational machines, Succinct representation, leaf languages, and projection reductions, Alphabet indexing for approximating features of symbols, 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, Sequences, datalog, and transducers, Storage controlled pile-up systems, theoretical foundations, Positive versions of polynomial time, On the approximability of the Steiner tree problem in phylogeny, Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application, 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, 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, Can datalog be approximated?, Predicting nonlinear cellular automata quickly by decomposing them into linear ones, Complexity of searching an immobile hider in a graph, 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, 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, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT., Non-approximability of precedence-constrained sequencing to minimize setups., Optimal satisfiability for propositional calculi and constraint satisfaction problems., On the algebraic complexity of some families of coloured Tutte polynomials, Some APX-completeness results for cubic graphs, Circuits and expressions with nonassociative gates, Semantical and computational aspects of Horn approximations, A complexity analysis of bisimilarity for value-passing processes, Polynomial time samplable distributions, Bypassing BDD construction for reliability analysis, Analog computation with dynamical systems, Default reasoning from conditional knowledge bases: Complexity and tractable cases, Easy weighted majority games, Conjunctive-query containment and constraint satisfaction, 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, 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, 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, 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, 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, Minimization and \(\mathbf{NP}\) multifunctions, A model-theoretic characterization of the weak pigeonhole principle, 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., Unification algorithms cannot be combined in polynomial time., Bounded queries, approximations, and the Boolean hierarchy, 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, 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, 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, On some tractable classes in deduction and abduction, Towards efficient universal planning: A randomized approach, A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols, Efficient timed model checking for discrete-time systems, 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, 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, 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, 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, Interval-valued computations and their connection with PSPACE, Asymptotic expected number of Nash equilibria of two-player normal form games, 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
