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 (only showing first 100 items - show all)
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
This page was built for publication:
