scientific article; zbMATH DE number 610968
From MaRDI portal
Publication:4298260
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Recommendations
Cited in
(only showing first 100 items - show all)- The Complexity of Reasoning for Fragments of Default Logic
- Non-deterministic Weighted Automata on Random Words
- On the structure of Hamiltonian cycles in Cayley graphs of finite quotients of the modular group
- On the complexity of typechecking top-down XML transformations
- Reducing hypergraph coloring to clique search
- Remarks on the computational power of some restricted variants of P systems with active membranes
- The computational complexity of basic decision problems in 3-dimensional topology
- Connectivity games over dynamic networks
- On testing monomials in multivariate polynomials
- Approximation in (poly-) logarithmic space
- Generalized satisfiability for the description logic \(\mathcal{ALC}\)
- Split clique graph complexity
- List-homomorphism problems on graphs and arc consistency
- Complexity and approximability of quantified and stochastic constraint satisfaction problems
- Universal relations and {\#}P-completeness
- Solution sets for equations over free groups are EDT0L languages
- An Algorithm for SAT Without an Extraction Phase
- From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules
- Physical consequences of P NP and the density matrix renormalization group annealing conjecture
- Modelling web-service uncertainty: the angel/daemon approach
- Games for query inseparability of description logic knowledge bases
- On the query complexity of selecting minimal sets for monotone predicates
- Solving QBF with counterexample guided refinement
- Maximal and supremal tolerances in multiobjective linear programming
- How to pack directed acyclic graphs into small blocks
- From QBFs to \textsf{MALL} and back via focussing
- Further oracles separating conjectures about incompleteness in the finite domain
- On theory of regular languages with the Kleene star operation
- The complexity of properties of transformation semigroups
- Simulating counting oracles with cooperation
- Complexity and expressive power of deterministic semantics for DATALOG^ .
- Computational complexity of planning and approximate planning in the presence of incompleteness
- Small universal accepting hybrid networks of evolutionary processors
- On exact sampling of nonnegative infinitely divisible random variables
- How to divide a territory? A new simple differential formalism for optimization of set functions
- Complexity of Weak Bisimilarity and Regularity for BPA and BPP
- Bandwidth of timed automata: 3 classes
- Reachability games and friends: a journey through the Lens of memory and complexity (invited talk)
- Unpredictability and computational irreducibility
- On the computational consequences of independence in propositional logic
- Reasoning on property graphs with graph generating dependencies
- Proving the infeasibility of Horn formulas through read-once resolution
- An oracle separating conjectures about incompleteness in the finite domain
- Studies in Computational Aspects of Voting
- Effective solution of linear Diophantine equation systems with an application in chemistry
- SAT-Based Formula Simplification
- A parameterized halting problem, _0 truth and the MRDP theorem
- Coloring the nodes of a directed graph
- On the reducibility of sets inside NP to sets with low information content
- Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting
- Parameterized counting problems
- Intruder deduction problem for locally stable theories with normal forms and inverses
- Worst-case performance of approximation algorithms for tool management problems
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
- Computational Complexity
- Complexity results for prefix grammars
- The complexity of generating test instances
- A nonadaptive NC checker for permutation group intersection
- The complexity of Boolean formula minimization
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- On the complexity of the FIFO stack-up problem
- A note on the circuit complexity of PP
- The complexity of satisfiability for fragments of hybrid logic. I.
- Complexity of model checking for reaction systems
- More results on the complexity of identifying problems in graphs
- The effect of end-markers on counter machines and commutativity
- Linearly-growing reductions of Karp's 21 NP-complete problems
- Complexity of graph self-assembly in accretive systems and self-destructible systems
- New genetic algorithm approach for the MIN-degree constrained minimum spanning tree
- Approximate algorithms for generalized maximum utility problems
- Characterizing sets of jobs that admit optimal greedy-like algorithms
- Translating propositional extended conjunctions of Horn clauses into Boolean circuits
- Model checking hybrid logics (with an application to semistructured data)
- Numerical experiments with LP formulations of the maximum clique problem
- Intensional Kleene and Rice theorems for abstract program semantics
- An approach to improve argumentation-based epistemic planning with contextual preferences
- Quantum circuits and low-degree polynomials over \(\mathbb{F}_2\)
- The possibilistic Horn non-clausal knowledge bases
- On the complexity of achieving proportional representation
- Complexity of limit-cycle problems in Boolean networks
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- Complexity of local, global and universality properties in finite dynamical systems
- Turing machines, transition systems, and interaction
- The complexity of the Kth largest subset problem and related problems
- Estimating information amount under uncertainty: algorithmic solvability and computational complexity
- Is intractability of nonmonotonic reasoning a real drawback?
- Algorithms for computing the set of acceptable arguments
- Cyclic extensions of order varieties
- Faster 3-coloring of small-diameter graphs
- The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game
- Absorbing random walks and the NAE2SAT problem
- The computational complexity of scenario-based agent verification and design
- Fixed points and attractors of reactantless and inhibitorless reaction systems
- Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
- Token sliding on split graphs
- Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
- P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
- Uniqueness in quadratic and hyperbolic \(0-1\) programming problems
- Satisfying subtype inequalities in polynomial space
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 Q4298260)
