scientific article; zbMATH DE number 610968

Publication date: 26 July 1994

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Turing machines NP-complete problems complexity theory

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)

Related Items

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, On the data complexity of consistent query answering, Term satisfiability in $\mathrm{FL}_{\mathrm{ew}}$-algebras, Extending propositional dynamic logic for Petri nets, Reverse complexity, Preferential multi-context systems, Reasoning about negligibility and proximity in the set of all hyperreals, A smoothing SQP framework for a class of composite $L_q$ minimization over polyhedron, Some remarks on real numbers induced by first-order spectra, Knowledge base exchange: the case of OWL 2 QL, A complexity analysis and an algorithmic approach to student sectioning in existing timetables, A comment on ``Computational complexity of stochastic programming problems, The complexity of priced control in elections, The computational complexity of iterated elimination of dominated strategies, Norm-based mechanism design, On $f$-reversible processes on graphs, Reducing graph coloring to clique search, Checking interval properties of computations, A generalization of Spira's theorem and circuits with small segregators or separators, Hypersequent rules with restricted contexts for propositional modal logics, Is Valiant-Vazirani's isolation probability improvable?, Parallel approximation of min-max problems, A framework for modular ERDF ontologies, Program equilibrium -- a program reasoning approach, The complexity of computing minimal unidirectional covering sets, Boolean logics with relations, Computational complexity and approximation for a generalization of the Euclidean problem on the Chebyshev center, Motion planning with pulley, rope, and baskets, Extending inclusion dependencies with conditions, On the aggregation problem for synthesized web services, A dichotomy in the complexity of counting database repairs, Tractable counting of the answers to conjunctive queries, Connectivity games over dynamic networks, On testing monomials in multivariate polynomials, Reexamination of an information geometric construction of entropic indicators of complexity, Split clique graph complexity, Generalized satisfiability for the description logic $\mathcal{ALC}$, List-homomorphism problems on graphs and arc consistency, Bounded repairability of word languages, Identifying path covers in graphs, Coloring the nodes of a directed graph, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, The complexity of Boolean formula minimization, More on the Magnus-Derek game, Logic-based ontology comparison and module extraction, with an application to DL-Lite, Updating action domain descriptions, Outlier detection for simple default theories, Lower complexity bounds in justification logic, All normalized anti-monotonic overlap graph measures are bounded, Faster $p$-adic feasibility for certain multivariate sparse polynomials, Towards a theory of patches, Approximating the least hypervolume contributor: NP-hard in general, but fast in practice, On probabilistic and quantum reaction systems, Prioritized and non-prioritized multiple change on belief bases, The complexity of satisfiability for fragments of hybrid logic. I., Complexity of hybrid logics over transitive frames, General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems, Pinpointing the complexity of the interval min-max regret knapsack problem, Moving in a network under random failures: a complexity analysis, An alternating hierarchy for finite automata, Identity checking problem for transformation monoids, Complexity and approximability of the cover polynomial, A complex analogue of Toda's theorem, Cycle bases in graphs characterization, algorithms, complexity, and applications, A survey on the structure of approximation classes, Sensitivity analysis of the knapsack problem: a negative result, The problem of stabilization of networked systems under computational power constraints, Temporal logics for concurrent recursive programs: satisfiability and model checking, The computational complexity of rationalizing Pareto optimal choice behavior, Restricted default theories: expressive power and outlier detection tasks, Two hardness results for Gamson's game, Approximability of the subset sum reconfiguration problem, Gaming is a hard job, but someone has to do it!, Deciding determinism of regular languages, Computational complexity of traffic hijacking under BGP and S-BGP, Multi-parameterised compositional verification of safety properties, Complexity of fixed-size bit-vector logics, Approximating Max NAE-$k$-SAT by anonymous local search, Directed hypergraphs: introduction and fundamental algorithms -- a survey, On nonlinear multi-covering problems, The tabularity problem over the minimal logic, From imperative to rule-based graph programs, Path-disruption games: bribery and a probabilistic model, Graph editing problems with extended regularity constraints, A combinatorial certifying algorithm for linear feasibility in UTVPI constraints, Queries and materialized views on probabilistic databases, Faster algorithms for mean-payoff games, Collaborative planning with confidentiality, A framework for reasoning under uncertainty based on non-deterministic distance semantics, Simplified forms of computerized reasoning with distance semantics, Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems, On the complexity of typechecking top-down XML transformations, Solving QBF with counterexample guided refinement, Games for query inseparability of description logic knowledge bases, On the query complexity of selecting minimal sets for monotone predicates, Maximal and supremal tolerances in multiobjective linear programming, Algorithms and almost tight results for 3-colorability of small diameter graphs, On the complexity of the FIFO stack-up problem, Probabilistic logic under coherence: complexity and algorithms, Modelling web-service uncertainty: the angel/daemon approach, Complexity of limit-cycle problems in Boolean networks, A comparative runtime analysis of heuristic algorithms for satisfiability problems, On the complexity of constrained Nash equilibria in graphical games, Complexity of the identity checking problem for finite semigroups., In some curved spaces, one can solve NP-hard problems in polynomial time, On the separability of subproblems in Benders decompositions, Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies, On the role of Hadamard gates in quantum circuits, Strong order equivalence, Equilibrium logic, On the tree-transformation power of XSLT, Feasible insertions in job shop scheduling, short cycles and stable sets, The $p$-median problem: a survey of metaheuristic approaches, Complexity of admissible rules, An efficient fixed-parameter algorithm for 3-hitting set, Computational complexity of the landscape. I., Towards a dichotomy theorem for the counting constraint satisfaction problem, Fast algorithms for robust classification with Bayesian nets, A new construction technique of a triangle-free 3-colored K16's, An efficient modular method for the control of concurrent discrete event systems: A language-based approach, Social laws in alternating time: effectiveness, feasibility, and synthesis, The complexity of the $K$th largest subset problem and related problems, On the complexity of sampling query feedback restricted database repair of functional dependency violations, Positive and negative proofs for circuits and branching programs, Theory of interaction, Analyzing the computational complexity of abstract dialectical frameworks via approximation fixpoint theory, Combined-semantics equivalence of conjunctive queries: decidability and tractability results, Exploiting hidden structure in selecting dimensions that distinguish vectors, The complexity of reasoning with FODD and GFODD, On updates of hybrid knowledge bases composed of ontologies and rules, On the complexity of bribery and manipulation in tournaments with uncertain information, On the complexity of regular-grammars with integer attributes, Extended RDF: computability and complexity issues, An NP-complete fragment of fibring logic, Complexity of graph self-assembly in accretive systems and self-destructible systems, Quantifying the complexity of geodesic paths on curved statistical manifolds through information geometric entropies and Jacobi fields, Hybridizing evolutionary algorithms with variable-depth search to overcome local optima, Graph unique-maximum and conflict-free colorings, Query languages for data exchange: beyond unions of conjunctive queries, Detecting and repairing anomalous evolutions in noisy environments. Logic programming formalization and complexity results, Hybrid tractability of valued constraint problems, On the complexity of iterated weak dominance in constant-sum games, The computational complexity of weak saddles, Estimating sample mean under interval uncertainty and constraint on sample variance, On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries, The computational complexity of evolutionarily stable strategies, Partitioning a weighted partial order, Relations between average-case and worst-case complexity, Equilibria problems on games: complexity versus succinctness, Martingale families and dimension in P, Groves of phylogenetic trees, Stochastic limit-average games are in EXPTIME, Good neighbors are hard to find: Computational complexity of network formation, Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs, Random subcubes as a toy model for constraint satisfaction problems, Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time, Inverse monoids associated with the complexity class NP, Holographic subregion complexity from kinematic space, Complexity of DNF minimization and isomorphism testing for monotone formulas, Solutions to computational problems through gene assembly, Efficiently embedding QUBO problems on adiabatic quantum computers, Expressive power and abstraction in Essence, On the computational complexity of the Riemann mapping, Undoing the effects of action sequences, Fine hierarchies and m-reducibilities in theoretical computer science, On the complexity of generalized chromatic polynomials, Connectivity with directional antennas in the symmetric communication model, Intruder deduction problem for locally stable theories with normal forms and inverses, Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, The complexity of circumscriptive inference in Post's lattice, The navigational power of web browsers, The complexity of the list homomorphism problem for graphs, Fundamentals of quantum information theory, Average-case complexity and decision problems in group theory., Turing machines, transition systems, and interaction, Recognizing frozen variables in constraint satisfaction problems, Trading polarizations for labels in P systems with active membranes, Algorithms and time complexity of the request-service problem, Complexity and organizational architecture, Deciding regularity of hairpin completions of regular languages in polynomial time, Complexity results for deciding networks of evolutionary processors, Stochastic game logic, Hyperbolic set covering problems with competing ground-set elements, Modular composition via factorization, Conjugacy in Baumslag's group, generic case complexity, and division in power circuits, Complexity classes as mathematical axioms, A theory of ultimately periodic languages and automata with an application to time granularity, On complete one-way functions, Generic case completeness, Rectangular tileability and complementary tileability are undecidable, The complexity of one-agent refinement modal logic, Improved simulation of nondeterministic Turing machines, On quasi-inconsistency and its complexity, Tropical varieties for exponential sums, Unrestricted vs restricted cut in a tableau method for Boolean circuits, Compiling propositional weighted bases, $(p,k)$-coloring problems in line graphs, The complexity of learning concept classes with polynomial general dimension, Abstract complexity theory and the $\Delta_{2}^{0}$ degrees, On the complexity of formulas in semantic programming, Node labels in local decision, Tree size reduction with keeping distinguishability, The computational complexity of calculating partition functions of optimal medians with Hamming distance, First-order linear logic without modalities is NEXPTIME-hard, On residual approximation in solution extension problems, Empirical analysis of algorithms for the shortest negative cost cycle problem, Complexity of Langton's ant, Complexity of Presburger arithmetic with fixed quantifier dimension, The expressive powers of stable models for bound and unbound DATALOG queries, Computing optimal assignments for residual network reliability, The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate, Metafinite model theory, Some consequences of cryptographical conjectures for $S_2^1$ and EF, Universally serializable computation, On the random generation and counting of matchings in dense graphs, Is intractability of nonmonotonic reasoning a real drawback?, Farrell polynomials on graphs of bounded tree width, Generic-case complexity, decision problems in group theory, and random walks., A polynomial space construction of tree-like models for logics with local chains of modal connectives, Tissue P systems., P-immune sets with holes lack self-reducibility properties., The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., The complexity of bisimilarity-checking for one-counter processes., On universally easy classes for NP-complete problems., Orienting rewrite rules with the Knuth-Bendix order., XML with data values: Typechecking revisited., Connection caching: Model and algorithms., $\mathcal P = \mathcal{NP}$?, On the polynomial-space completeness of intuitionistic propositional logic, (2+$f$($n$))-SAT and its properties., The decision problem of provability logic with only one atom, On the hardness of counting problems of complete mappings., Universal relations and {\#}P-completeness, Partially commutative inverse monoids., Resource-bounded measure on probabilistic classes, Translating propositional extended conjunctions of Horn clauses into Boolean circuits, A computational analysis of the tournament equilibrium set, Characterizing sets of jobs that admit optimal greedy-like algorithms, Small universal accepting hybrid networks of evolutionary processors, On the autoreducibility of functions, Approximability of clausal constraints, Variable neighbourhood search: methods and applications, Satisfactory graph partition, variants, and generalizations, General default logic, A new default theories compilation for MSP-entailment, Reasoning under inconsistency: a forgetting-based approach, The complexity of power-index comparison, Approximability of partitioning graphs with supply and demand, A note on the distribution of the distance from a lattice, Knowledge condition games, A complexity tradeoff in ranking-function termination proofs, Complexity of the problem of verifying the coordination mechanism in a system of software support of network collaboration, The hardest linear conjunctive language, Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families, Random walks for selected Boolean implication and equivalence problems, From a zoo to a zoology: Towards a general theory of graph polynomials, Dimension extractors and optimal decompression, Red-blue covering problems and the consecutive ones property, A self-adaptive multi-engine solver for quantified Boolean formulas, Algorithms for compact letter displays: comparison and evaluation, Cellular automaton growth on $\mathbb{Z}^2$: Theorems, examples, and problems, Quantified coalition logic, Minimum weakly fundamental cycle bases are hard to find, Partially ordered connectives and monadic monotone strict NP, Approximating MAPs for belief networks is NP-hard and other theorems, Language complexity of rotations and Sturmian sequences, On the structure of Hamiltonian cycles in Cayley graphs of finite quotients of the modular group, Some complexity bounds for subtype inequalities, Paintshop, odd cycles and necklace splitting, Reasoning about temporal properties of rational play, From Hilbert's program to a logic tool box, Resolution for Max-SAT, AM$_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})$/poly, Linear connectivity problems in directed hypergraphs, Variable neighbourhood search: Methods and applications, On the concavity of delivery games, Reductions and functors from problems to word problems, Almost 2-SAT is fixed-parameter tractable, The complexity of solitaire, $\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})$, On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls, Systems of agents controlled by logical programs: complexity of verification, The zero-one law holds for BPP, Intractability of decision problems for finite-memory automata, Backdoor sets of quantified Boolean formulas, The three-color and two-color Tantrix$^{\text{TM}}$ rotation puzzle problems are NP-complete via parsimonious reductions, Flows with unit path capacities and related packing and covering problems, Properties of uniformly hard languages, Representing interval orders by weighted bases: some complexity results, The complexity of hybrid logics over equivalence relations, Computational complexity of planning and approximate planning in the presence of incompleteness, Succinctness as a source of complexity in logical formalisms, Clique is hard to approximate within $n^{1-\epsilon}$, The complexity of approximating MAPs for belief networks with bounded probabilities, Sensitivity analysis for knapsack problems: Another negative result, The complexity of cover inequality separation, Satisfying subtype inequalities in polynomial space, Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem., Complexity of fixed point counting problems in Boolean networks, Equivalence classes and conditional hardness in massively parallel computations, The delay and window size problems in rule-based stream reasoning, Inconsistency-tolerant query answering for existential rules, The complexity of solution sets to equations in hyperbolic groups, On efficiency of notations for natural numbers, Completeness, approximability and exponential time results for counting problems with easy decision version, A parameterized view on the complexity of dependence logic, Solving a PSPACE-complete problem by symport/antiport P systems with promoters and membrane division, A tetrachotomy of ontology-mediated queries with a covering axiom, Nonuniform reductions and NP-completeness, Computing equilibria for integer programming games, Selecting a subset of diverse points based on the squared Euclidean distance, Root repulsion and faster solving for very sparse polynomials over $p$-adic fields, A probabilistic logic between $LPP_1$ and $LPP_2$, Analyzing the reachability problem in choice networks, Metric space method for constructing splitting partitions of graphs, Emptiness problems for integer circuits, Kernels by rainbow paths in arc-colored tournaments, NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes, Computable aggregations, From NP-completeness to DP-completeness: a membrane computing perspective, The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference, Thirty years of credal networks: specification, algorithms and complexity, 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, Handling and measuring inconsistency in non-monotonic logics, DEL-based epistemic planning: decidability and complexity, Counting linear extensions of restricted posets, Diagnosis and degradation control for probabilistic systems, On the number of integer points in translated and expanded polyhedra, The stable marriage problem: an interdisciplinary review from the physicist's perspective, Estimating the fractional chromatic number of a graph, Computational complexity of flat and generic assumption-based argumentation, with and without probabilities, Incremental computation for structured argumentation over dynamic DeLP knowledge bases, A minimal nonfinitely based semigroup whose variety is polynomially recognizable., On one approach to TSP structural stability, Lee-Yang theorems and the complexity of computing averages, Models of quantum computation and quantum programming languages, Task assignment algorithms for two-type heterogeneous multiprocessors, The minimum firing time of the generalized firing squad synchronization problem for squares, Set graphs. II. Complexity of set graph recognition and similar problems, Control complexity in Bucklin and fallback voting: a theoretical analysis, Does the polynomial hierarchy collapse if onto functions are invertible?, On the computational complexity of weighted voting games, An AGM-style belief revision mechanism for probabilistic spatio-temporal logics, Multiagent resource allocation in $k$-additive domains: preference representation and complexity, Faster polynomial multiplication over finite fields using cyclotomic coefficient rings, Lower bound on the number of Hamiltonian cycles of generalized Petersen graphs, Fast multivariate multi-point evaluation revisited, Analyzing clustering and partitioning problems in selected VLSI models, The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws, Computational complexity for bounded distributive lattices with negation, Subroutines in P systems and closure properties of their complexity classes, Semi-oblivious chase termination: the sticky case, On the complexity of the smallest grammar problem over fixed alphabets, Approximation in (Poly-) logarithmic space, Robustness of approval-based multiwinner voting rules, Orbit expandability of automaton semigroups and groups, An oracle separating conjectures about incompleteness in the finite domain, Quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the size of the clusters: complexity and approximability, Resilient capacity-aware routing, The trouble with the second quantifier, Protecting elections by recounting ballots, Shellings from relative shellings, with an application to NP-completeness, Token sliding on split graphs, Solution to PSPACE-complete problem using P systems with active membranes with time-freeness, Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems, Complexity results for probabilistic answer set programming, Using decomposition-parameters for QBF: mind the prefix!, Cell-like P systems with polarizations and minimal rules, The expressiveness of looping terms in the semantic programming, The word problem of the Brin-Thompson group is \textsf{coNP}-complete, Towards efficient verification of population protocols, Hard problems that quickly become very easy, Answers set programs for non-transferable utility games: expressiveness, complexity and applications, Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks, Novel phylogenetic network distances based on cherry picking, Logical language of description of polynomial computing, A clique search problem and its application to machine scheduling, Černý's conjecture and the road colouring problem, Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas, General information spaces: measuring inconsistency, rationality postulates, and complexity, Information and complexity, or: where is the information?, A deterministic algorithm for finding $r$-power divisors, Complexity of shift bribery for iterative voting rules, Image-binary automata, Numerical experiments with LP formulations of the maximum clique problem, Complexity of local, global and universality properties in finite dynamical systems, An undecidability result for the asymptotic theory of $p$-adic fields, Intensional Kleene and Rice theorems for abstract program semantics, An approach to improve argumentation-based epistemic planning with contextual preferences, The possibilistic Horn non-clausal knowledge bases, Polymer dynamics via cliques: new conditions for approximations, On the computational complexity of reaction systems, revisited, Distributed algorithms for matching in hypergraphs, Subrecursive equivalence relations and (non-)closure under lattice operations, Hardness and optimality in QBF proof systems modulo NP, New lowness results for ZPP$^{\text{NP}}$ and other complexity classes., On the complexity of pattern matching for highly compressed two-dimensional texts., Arithmetical definability and computational complexity, A note on tolerance graph recognition, DP lower bounds for equivalence-checking and model-checking of one-counter automata, On the complexity of integer matrix multiplication, Computational complexity of the landscape. II: Cosmological considerations, Computation as social agency: what, how and who, The complexity of optimal multidimensional pricing for a unit-demand buyer, Self-concordance is NP-hard, The archievable region method in the optimal control of queueing systems; formulations, bounds and policies, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs, Inapproximability of the Tutte polynomial of a planar graph, Approximating the minimum length of synchronizing words is hard, The computational complexity of QoS measures for orchestrations. The computational complexity of QoS measures, Algorithmically complex residually finite groups, The $(k, \ell)$ partitioned probe problem: NP-complete versus polynomial dichotomy, Minimum cost partitions of trees with supply and demand, On inverse traveling salesman problems, Route-enabling graph orientation problems, Keeping logic in the trivium of computer science: a teaching perspective, The multi-stripe travelling salesman problem, On the complexity of tree pattern containment with arithmetic comparisons, One-way functions using algorithmic and classical information theories, Computational aspects of greedy partitioning of graphs, Model checking for fragments of Halpern and Shoham's interval temporal logic based on track representatives, Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games, Formal verification based on Boolean expression diagrams, The intersection of subgroups in free groups and linear programming, Robust certified numerical homotopy tracking, Logical foundations of information disclosure in ontology-based data integration, The complexity of Bayesian networks specified by propositional and relational languages, On computation of Boolean involutive bases, Linearly-growing reductions of Karp's 21 NP-complete problems, Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, Time and space complexity for splicing systems, The complexity of problems for quantified constraints, On structured output training: hard cases and an efficient alternative, On logics with two variables, Hard sets are hard to find, Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs, Unique (optimal) solutions: complexity results for identifying and locating-dominating codes, On the hardness of analyzing probabilistic programs, Data independence of read, write, and control structures in PRAM computations, The maximum clique interdiction problem, The maximum number of Hamiltonian cycles in graphs with a fixed number of vertices and edges, Probabilistic verification of proofs in calculuses, A natural explanation for the minimum entropy production principle, On the complexity of the Leibniz hierarchy, Simulating counting oracles with cooperation, Seeking computational efficiency boundaries: the Păun's conjecture, Decomposing clique search problems into smaller instances based on node and edge colorings, The descriptive complexity of decision problems through logics with relational fixed-point and capturing results, Type-two polynomial-time and restricted lookahead, Two new reformulation convexification based hierarchies for 0-1 MIPs, Intra- and interdiagram consistency checking of behavioral multiview models, Finding read-once resolution refutations in systems of 2CNF clauses, Efficient approximation schemes for economic lot-sizing in continuous time, New genetic algorithm approach for the MIN-degree constrained minimum spanning tree, Complexity of Grundy coloring and its variants, The complexity of computing a (quasi-)perfect equilibrium for an $n$-player extensive form game, Sparse selfreducible sets and nonuniform lower bounds, A faster pseudo-primality test, Parallel computation using active self-assembly, Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem, Efficient algorithms for heavy-tail analysis under interval uncertainty, On the reducibility of sets inside NP to sets with low information content, Incentive-based search for equilibria in Boolean games, A trichotomy for regular simple path queries on graphs, On the generation of circuits and minimal forbidden sets, On the complexity of computing Kronecker coefficients, Finite graph automata for linear and boundary graph languages, Checking quasi-identities in a finite semigroup may be computationally hard., Learning local transductions is hard, Manipulating games by sharing information, The commuting local Hamiltonian problem on locally expanding graphs is approximable in $\mathsf{NP}$, String shuffle: circuits and graphs, Epistemic closure and epistemic logic. I: Relevant alternatives and subjunctivism, Competing provers yield improved Karp-Lipton collapse results, A probabilistic model of computing with words, Generalizations of matched CNF formulas, On deciding subsumption problems, Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity, The center location improvement problem under the Hamming distance, Approximation and dependence via multiteam semantics, The complexity of satisfiability in non-iterated and iterated probabilistic logics, Probabilistic spatio-temporal knowledge bases: capacity constraints, count queries, and consistency checking, Understanding cutting planes for QBFs, On the complexity of finding a Caristi's fixed point, On the approximability of an interval scheduling problem, On the computational complexity of Longley's $H$ functional, On an optimal propositional proof system and the structure of easy subsets of TAUT., Complexity and expressive power of deterministic semantics for DATALOG$^ \neg$., Tally NP sets and easy census functions., The complexity of the exponential output size problem for top-down and bottom-up tree transducers, Complexity theory and genetics: The computational power of crossing over, The complexity of propositional linear temporal logics in simple cases, Functional queries in datalog, The number of 2-SAT functions, Prefix-suffix square reduction, A multi-objective memetic algorithm for the job-shop scheduling problem, On the complexity of the word problem for automaton semigroups and automaton groups, Logic of temporal attribute implications, Generality's price: Inescapable deficiencies in machine-learned programs, Computational depth: Concept and applications, The computational complexity of scenario-based agent verification and design, Disjunctive logic programming with types and objects: the $\mathrm{DLV}^{+}$ system, Complexity of question/answer games, Computational complexity of counting problems on 3-regular planar graphs, Counting for satisfiability by inverting resolution, A zero-one law for RP and derandomization of AM if NP is not small, A logical approach to efficient Max-SAT solving, Solving quantified constraint satisfaction problems, Packing Steiner trees with identical terminal sets, Computational complexities of axiomatic extensions of monoidal t-norm based logic, Parameterized complexity classes beyond para-NP, From causes for database queries to repairs and model-based diagnosis and back, On repairing and querying inconsistent probabilistic spatio-temporal databases, Bounded variability of metric temporal logic, The effect of combination functions on the complexity of relational Bayesian networks, Equations over free inverse monoids with idempotent variables, Reducing hypergraph coloring to clique search, Temporal flows in temporal networks, Clustering without replication in combinatorial circuits, Complexity results for answer set programming with bounded predicate arities and implications, On look-ahead heuristics in disjunctive logic programming, On the complexity of achieving proportional representation, Approximation of the quadratic set covering problem, Maximum series-parallel subgraph, Fixpoint logics over hierarchical structures, Parallelizing time with polynomial circuits, Counting spanning trees using modular decomposition, Computability of the Julia set. Nonrecurrent critical orbits, Multi-objective optimization with an adaptive resonance theory-based estimation of distribution algorithm, Computational aspects of uncertainty profiles and angel-daemon games, Unified QBF certification and its applications, Counting points on hyperelliptic curves in average polynomial time, A note on the approximation of mean-payoff games, The complexity of computing the behaviour of lattice automata on infinite trees, Rationalizations of Condorcet-consistent rules via distances of Hamming type, Uniqueness in quadratic and hyperbolic $0-1$ programming problems, Prefix-suffix duplication, Towards a practical theory of reformulation for reasoning about physical systems, Comparing action descriptions based on semantic preferences, On variable-weighted exact satisfiability problems, On a decision procedure for quantified linear programs, The complexity of satisfying constraints on databases of transactions, Upward separations and weaker hypotheses in resource-bounded measure, The complexity of two problems on arithmetic circuits, Counting truth assignments of formulas of bounded tree-width or clique-width, Optimal infinite scheduling for multi-priced timed automata, Baire categories on small complexity classes and meager-comeager laws, A DNA-based solution to the graph isomorphism problem using Adleman-Lipton model with stickers, Model checking abilities of agents: a closer look, Grasp and delivery for moving objects on broken lines, The computational complexity of basic decision problems in 3-dimensional topology, Using the renormalization group to classify Boolean functions, Algorithms for modular counting of roots of multivariate polynomials, Exact bounds on finite populations of interval data, Dynamics of local search trajectory in traveling salesman problem, Computational complexity of stochastic programming problems, Uniform generation in spatial constraint databases and applications, On the computational consequences of independence in propositional logic, The complexity of agent design problems: Determinism and history dependence, Solving HPP and SAT by P systems with active membranes and separation rules, LTL over integer periodicity constraints, Effective solution of linear Diophantine equation systems with an application in chemistry, Model checking hybrid logics (with an application to semistructured data), If P $\neq$ NP then some strongly noninvertible functions are invertible, Randomized algorithms for robust controller synthesis using statistical learning theory: a tutorial overview, Polynomial time relatively computable triangular arrays for almost sure convergence, The model checking fingerprints of CTL operators, A multiparametric view on answer set programming, A uniform solution to SAT problem by symport/antiport P systems with channel states and membrane division, On coarser interval temporal logics, Strong inconsistency, Backdoors to planning, Complexity results for preference aggregation over ($m$)CP-nets: Pareto and majority voting, Rational closure for all description logics, On the complexity of inconsistency measurement, Orthogonal representations over finite fields and the chromatic number of graphs, On interval and circular-arc covering problems, Clustering with qualitative information, On the hardness of approximating the min-hack problem, Balance problems for integer circuits, Discrete quantum walks hit exponentially faster, All superlinear inverse schemes are coNP-hard, The complexity of primal logic with disjunction, A note on the circuit complexity of PP, Parameterized counting problems, Refinement checking on parametric modal transition systems, Iterative and core-guided maxsat solving: a survey and assessment, Coloring the edges of a directed graph, Synthesis of succinct systems, Approaches to measuring inconsistency for stratified knowledge bases, Semantics for possibilistic answer set programs: uncertain rules versus rules with uncertain conclusions, Hitting all maximal independent sets of a bipartite graph, Complexity analysis and algorithms for the program download problem, ``Selfish algorithm for reducing the computational cost of the network survivability analysis, md-MST is NP-hard for, Checking identities is computationally intractable NP-hard and therefore human provers will always be needed, P Systems with Active Membranes Operating under Minimal Parallelism, Complexity of Safe Strategic Voting, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, Specification and Verification of Multi-Agent Systems, On Exact Sampling of Nonnegative Infinitely Divisible Random Variables, Edge coloring of graphs, uses, limitation, complexity, Cooperation through social influence, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Using SAT solvers for synchronization issues in non-deterministic automata, Characteristic function games with restricted agent interactions: core-stability and coalition structures, Backdoors to Satisfaction, Studies in Computational Aspects of Voting, Revisiting Shinohara's algorithm for computing descriptive patterns, Equivalence between model-checking flat counter systems and Presburger arithmetic, The complexity of online manipulation of sequential elections, On computational complexity of construction of c -optimal linear regression models over finite experimental domains, Inconsistency Management for Traffic Regulations: Formalization and Complexity Results, The Complexity of One-Agent Refinement Modal Logic, Boolean functions as models for quantified Boolean formulas, Learning parallel portfolios of algorithms, ON OPTIMAL INVERTERS, Complexity issues of checking identities in finite monoids, Unpredictability and Computational Irreducibility, The unbearable hardness of unknotting, Unnamed Item, On the complexity exponent of polynomial system solving, The asymptotics of the clustering transition for random constraint satisfaction problems, Integer multiplication in time $O(n\log n)$, Descriptive complexity of deterministic polylogarithmic time and space, Packing arc-disjoint cycles in tournaments, Drawing Euler Diagrams from Region Connection Calculus Specifications with Local Search, Computing Covariance and Correlation in Optimally Privacy-Protected Statistical Databases: Feasible Algorithms, Depth-First Search Using $$O(n)$$ Bits, Complexity results for preference aggregation over $(m)$CP-nets: max and rank voting, Strong simulation, Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes, Reversible Limited Automata, A Characterization of NP Within Interval-Valued Computing, Modal Inclusion Logic: Being Lax is Simpler than Being Strict, Complexity Classifications for Logic-Based Argumentation, A Cookbook for Temporal Conceptual Data Modelling with Description Logics, On the Complexity of Probabilistic Abstract Argumentation Frameworks, The complexity of searching implicit graphs, Some wonders of a bio-computer-scientist, Solving projected model counting by utilizing treewidth and its limits, Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems, EDT0L solutions to equations in group extensions, On the Variable Hierarchy of First-Order Spectra, On the Complexity of Extracting Subtree with Keeping Distinguishability, Computing smallest MUSes of quantified Boolean formulas, Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$, Ontology-Mediated Query Answering with Data-Tractable Description Logics, Is the World Itself Fuzzy? Physical Arguments and Unexpected Computational Consequences of Zadeh’s Vision, On quantum lambda calculi: a foundational perspective, An automaton group with \textsf{PSPACE}-complete word problem, Remarks on the Computational Power of Some Restricted Variants of P Systems with Active Membranes, The Power of Non-determinism in Higher-Order Implicit Complexity, Local Transition Functions of Quantum Turing Machines, Recognizing Sparse Perfect Elimination Bipartite Graphs, Finite Combinatory Logic with Intersection Types, Generalized Satisfiability for the Description Logic $\mathcal{ALC}$, Synthesis and Analysis of Product-Form Petri Nets, On Stopping Evidence Gathering for Diagnostic Bayesian Networks, Extensions of Decision-Theoretic Troubleshooting: Cost Clusters and Precedence Constraints, Complexity results for prefix grammars, Hybrid logics: characterization, interpolation and complexity, COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA, On the Complexity of Query Result Diversification, Exponential Time Complexity of Weighted Counting of Independent Sets, Function operators spanning the arithmetical and the polynomial hierarchy, THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA, Preimage Problems for Reaction Systems, Towards the Possibility of Objective Interval Uncertainty, The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks, On a family of preimage-resistant functions, Inapproximability of b-Matching in k-Uniform Hypergraphs, Counting Spanning Trees in Graphs Using Modular Decomposition, Quantum computation techniques for gauging reliability of interval and fuzzy data, Strong Backdoors for Default Logic, MCS Extraction with Sublinear Oracle Queries, Randomness and Computation, Solution sets for equations over free groups are EDT0L languages, Deciding According to the Shortest Computations, Partial Observation of Quantum Turing Machines and a Weaker Well-Formedness Condition, Query Answering with DBoxes is Hard, $$P\mathop{ =}\limits^{?}NP$$, Split Clique Graph Complexity, Automatic structures of bounded degree revisited, On the Maximum Uniquely Restricted Matching for Bipartite Graphs, Book Review: Inevitable randomness in discrete mathematics, COMPLEXITY OF SHORT GENERATING FUNCTIONS, Faster deterministic integer factorization, On the computational power of probabilistic and quantum branching program, On the complexity of unfrozen problems, Bounded fixed-parameter tractability and $\log^{2}n$ nondeterministic bits, Undecidability of Multi-modal Hybrid Logics, Primal-dual approximation algorithms for a packing-covering pair of problems, Property testers for dense constraint satisfaction programs on finite domains, Finite Variable Logics in Descriptive Complexity Theory, Logics which capture complexity classes over the reals, Machines, Logic and Quantum Physics, Computing the shape of the image of a multi-linear mapping is possible but computationally intractable: Theorems, Complexity of interpolation and related problems in positive calculi, Immunity and Simplicity for Exact Counting and Other Counting Classes, Solution Sets for Equations over Free Groups are EDT0L Languages, Local Search to Approximate Max NAE-$$k$$-Sat Tightly, SAT-Based Formula Simplification, Compositional Reasoning, The phase transition in random horn satisfiability and its algorithmic implications, Unnamed Item, DP-Complete Problems Derived from Extremal NP-Complete Properties, The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I, Weighted Boolean Formula Games, Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, A subquadratic algorithm for computing the $n$-th Bernoulli number, A search for Wilson primes, XML Schema Mappings, Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem, Directed Pathwidth and Palletizers, On Clustering Without Replication in Combinatorial Circuits, Unconventional Computing: Do We Dream Too Much?, Information geometric methods for complexity, Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP, The expressive power of unique total stable model semantics, Small Resolution Proofs for QBF using Dependency Treewidth, Definability in the class of all -frames – computability and complexity, Boolean Logics with Relations, Computation of Renameable Horn Backdoors, Characterizing and extending answer set semantics using possibility theory, Consistency and trust in peer data exchange systems, Some Inverse Traveling Salesman Problems, Parameterized Derandomization, First-Order Model Checking Problems Parameterized by the Model, On the Complexity of Equilibria Problems in Angel-Daemon Games, Complexity of Counting the Optimal Solutions, Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis, Haplotype Inferring Via Galled-Tree Networks Is NP-Complete, Expander graphs and their applications, On the expressive power of the shuffle operator matched with intersection by regular sets, Non-dichotomies in Constraint Satisfaction Complexity, WORD EQUATIONS OVER GRAPH PRODUCTS, An Analysis of Slow Convergence in Interval Propagation, Handling Ignorance in Argumentation: Semantics of Partial Argumentation Frameworks, Local Monotonicity in Probabilistic Networks, Unnamed Item, Recovering Consistency by Forgetting Inconsistency, ON THE POWER OF QUANTUM TAMPER-PROOF DEVICES, A Logical Approach to Dynamic Role-Based Access Control, Synchronizing Automata and the Černý Conjecture, The Alcuin Number of a Graph, ON THE DESCRIPTIONAL COMPLEXITY OF ACCEPTING NETWORKS OF EVOLUTIONARY PROCESSORS WITH FILTERED CONNECTIONS, Infinite Runs in Weighted Timed Automata with Energy Constraints, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, Solutions to twisted word equations and equations in virtually free groups, Completeness of classical spin models and universal quantum computation, Physical consequences of P≠NP and the density matrix renormalization group annealing conjecture, The large deviations of the whitening process in random constraint satisfaction problems, LC and Its Pretabular Relatives, Least Upper Bounds on the Size of Church-Rosser Diagrams in Term Rewriting and λ-Calculus, Estimating information amount under uncertainty: algorithmic solvability and computational complexity, THE ${\mathcal R}$- AND ${\mathcal L}$-ORDERS OF THE THOMPSON–HIGMAN MONOID M_{k, 1} AND THEIR COMPLEXITY, The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions, On Shuffle Ideals, Unnamed Item, How to divide a territory? A new simple differential formalism for optimization of set functions, Arthur and Merlin as Oracles, Strategic Agent Communication: An Argumentation-Driven Approach, Short rational generating functions for lattice point problems, Approximate algorithms for generalized maximum utility problems, An Algorithm for SAT Without an Extraction Phase, Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems, Worst-case performance of approximation algorithms for tool management problems, Secure information hiding based on computationally intractable problems, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, The ultra-weak Ash conjecture and some particular cases, Constraint Propagation with Tabu List for Min-Span Frequency Assignment Problem, Horn representation of a concept lattice, NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability, TESTING EMBEDDABILITY BETWEEN METRIC SPACES, The Complexity of Reasoning for Fragments of Default Logic, Size Complexity of Two-Way Finite Automata, Complexity and Cautiousness Results for Reasoning from Partially Preordered Belief Bases, Answer Set Programming: A Primer, Ontologies and Databases: The DL-Lite Approach, Lower Bounds for Las Vegas Automata by Information Theory, Dynamic logics of the region-based theory of discrete spaces, A logical characterisation of qualitative coalitional games, A Topological Constraint Language with Component Counting, A Canonical Model of the Region Connection Calculus, Confined modified realizability, Efficient Combination of Decision Procedures for MUS Computation, Query Order, Modular exponentiation via the explicit Chinese remainder theorem, GPDOF — A FAST ALGORITHM TO DECOMPOSE UNDER-CONSTRAINED GEOMETRIC CONSTRAINT SYSTEMS: APPLICATION TO 3D MODELING, SIMULATION OF QUANTUM ADIABATIC SEARCH IN THE PRESENCE OF NOISE, Complexity classes for membrane systems, Solving maximum independent set by asynchronous distributed hopfield-type neural networks, The complexity of the Weight Problem for permutation groups, A user authentication protocol based on the intractability of the 3-coloring problem, The operators min and max on the polynomial hierarchy, The complexity of generating test instances, Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$, Query order in the polynomial hierarchy, Networks of Polarized Splicing Processors, Polynomial Multiplication over Finite Fields in Time $ O(n \log n $, Unnamed Item, A log-log speedup for exponent one-fifth deterministic integer factorisation, Short Presburger Arithmetic Is Hard, Equations in virtually abelian groups: Languages and growth, INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH, Unnamed Item, The isomorphism problem for finite extensions of free groups is in PSPACE, On evaluating permanents and a matrix of contangents^∗, Unnamed Item, Complexity results for abductive logic programming, Unnamed Item, The Computational Complexity of Integer Programming with Alternations, A Logic Framework for P2P Deductive Databases, Optimal Switching Sequence for Switched Linear Systems, The Bounded and Precise Word Problems for Presentations of Groups, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Fast integer multiplication using generalized Fermat primes, Computational Complexity of Atomic Chemical Reaction Networks, Unnamed Item, Unnamed Item, On the critical exponent α of the 5D random-field Ising model, Unnamed Item, Quantified Constraints in Twenty Seventeen, Algebra and the Complexity of Digraph CSPs: a Survey, Rewriting with generalized nominal unification, An analysis of the Core-ML language: Expressive power and type reconstruction, Coalition formation in social environments with logic-based agents1, On computational complexity of Cremer Julia sets, Quantitative Automata under Probabilistic Semantics, Proof Compression and NP Versus PSPACE II, Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras., COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS, Non-deterministic Weighted Automata on Random Words, Dimensional Inconsistency Measures and Postulates in Spatio-Temporal Databases, A note on the complexity of S4.2, New collapse consequences of NP having small circuits, The complexity of searching succinctly represented graphs, A Twin Error Gauge for Kaczmarz's Iterations, Unification algorithms cannot be combined in polynomial time, Datalog and Its Extensions for Semantic Web Databases, OWL 2 Profiles: An Introduction to Lightweight Ontology Languages, A Complex-Networks View of Hard Combinatorial Search Spaces, Making big data small, The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences, Complexity of Weak Bisimilarity and Regularity for BPA and BPP, Algorithms and Complexity of Automata Synthesis by Asynhcronous Orchestration With Applications to Web Services Composition, Parallel Computation Using Active Self-assembly, Revising Type-2 Computation and Degrees of Discontinuity, Optimality parsing and local cost functions in Discontinuous Grammar, Loop invariants, The Descriptive Complexity of the Deterministic Exponential Time Hierarchy, Unnamed Item, Unnamed Item, The ground-negative fragment of first-order logic is -complete, Implicit measurements of dynamic complexity properties and splittings of speedable sets, Unnamed Item, Faster integer multiplication using plain vanilla FFT primes, Simulation of Natural Deduction and Gentzen Sequent Calculus, Constraint Satisfaction with Counting Quantifiers, Unnamed Item, Polynomial-time right-ideal morphisms and congruences, On the parameterized complexity of approximate counting, A $\Sigma_2^P \cup \Pi_2^P$ Lower Bound Using Mobile Membranes, An exponent one-fifth algorithm for deterministic integer factorisation, The complexity of properties of transformation semigroups, Unnamed Item, Definable Inapproximability: New Challenges for Duplicator, On the Prefix–Suffix Duplication Reduction, Geometrical organization of solutions to random linear Boolean equations, Multitasking Capacity: Hardness Results and Improved Constructions, Statistical and algebraic analysis of a family of random Boolean equations, Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer, The complexity of weakly recognizing morphisms, The Complexity of Finding Read-Once NAE-Resolution Refutations, P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle, The Complexity of Counting Surjective Homomorphisms and Compactions, A time-space tradeoff for Lehman’s deterministic integer factorization method, Logic—The Big Picture, Counting problems for parikh images, Emptiness Problems for Integer Circuits, A Twin Error Gauge for Kaczmarz's Iterations, The Complexity of Quantified Constraints Using the Algebraic Formulation, Unnamed Item, Logic and Game Theory, Logic and Complexity in Cognitive Science, Unnamed Item, Biased landscapes for random constraint satisfaction problems, ahmaxsat: Description and Evaluation of a Branch and Bound Max-SAT Solver, Parallel algorithms for matroid intersection and matroid parity, On Quantifying Literals in Boolean Logic and its Applications to Explainable AI, Packing a Knapsack of Unknown Capacity, Backdoors to Normality for Disjunctive Logic Programs, A generic optimization framework for resilient systems, Quantified Constraint Satisfaction Problem on Semicomplete Digraphs, Computability Models: Algebraic, Topological and Geometric Algorithms, Completeness Results for Counting Problems with Easy Decision, Complexity and polymorphisms for digraph constraint problems under some basic constructions, The subpower membership problem for semigroups, Finding similar/diverse solutions in answer set programming, Expressiveness of communication in answer set programming, NP‐completeness of list coloring and precoloring extension on the edges of planar graphs, Minimality of a solution update in conflict resolution: An application of revision programming to the von Neumann-Morgenstern approach, An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set, On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries, On Finding Small 2-Generating Sets, Effective Poset Inequalities, Small networks of polarized splicing processors are universal, Topological Complexity in AdS₃/CFT₂, Solution Enumeration by Optimality in Answer Set Programming, Some consequences of cryptographical conjectures for S 2 1 and EF, A general framework for preferences in answer set programming, Some rainbow problems in graphs have complexity equivalent to satisfiability problems, Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино?, Taming strategy logic: non-recurrent fragments, The notion of abstraction in ontology-based data management, Interference as a computational resource: a tutorial, Toward credible belief base revision, Markov chains and unambiguous automata, On the complexity of inverse semigroup conjugacy, Commuting quantum circuits and complexity of Ising partition functions, A completeness proof for a regular predicate logic with undefined truth value, Sometimes travelling is easy: The master tour problem, Weighted two-way transducers, Polynomial combined first-order rewritings for linear and guarded existential rules, Reachability in choice networks, Testing for weak separability and utility maximization with incomplete adjustment, On the parallel complexity of constrained read-once refutations in UTVPI constraint systems, Weighted two-way transducers, From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules, Decision Questions for Probabilistic Automata on Small Alphabets, Fixed points and attractors of reactantless and inhibitorless reaction systems, Computational complexity of reversible reaction systems, Quantum encoding of dynamic directed graphs, Active P-colonies, A simple logic of concepts, Unnamed Item, Unnamed Item, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, Unnamed Item, Linear Logic Proof Games and Optimization, SOLVABILITY OF SYSTEMS OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS, First-order and counting theories ofω-automatic structures, The complexity of recursion theoretic games, On the complexity of problems on simple games, QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES, Absorbing random walks and the NAE2SAT problem, Circuit complexity of regular languages, NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES, Interpolating greedy and reluctant algorithms, Weak cardinality theorems, Cyclic Extensions of Order Varieties, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Infinitely generated semigroups and polynomial complexity, A model of $\widehat{R}^2_3$ inside a subexponential time resource, On pseudorandomness and resource-bounded measure, On the unique shortest lattice vector problem, A nonadaptive NC checker for permutation group intersection, Randomized algorithms for robust controller synthesis using statistical learning theory, Probabilistic solutions to some NP-hard matrix problems, Securing a compiler transformation, Time-space tradeoffs for SAT on nonuniform machines, Integer circuit evaluation is PSPACE-complete, On the Complexity of Computing Generators of Closed Sets, Complement for two-way alternating automata, Default logic and bounded treewidth, Generalized satisfiability problems via operator assignments, Tractable constraints on ordered domains, Some Results on the Expressive Power and Complexity of LSCs, Tractable constraints on ordered domains, Satisfiability of Algebraic Circuits over Sets of Natural Numbers, CASCADING RANDOM WALKS, Sublinear-time reductions for big data computing, The computational complexity of knot genus and spanning area, Complexity, decidability and completeness, Enumerations of the Kolmogorov function, TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS, LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE, Logspace computations in graph products, Toward Best Approximation of Nonlinear Systems: A Case of Models with Memory, ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS, Knapsack problems in groups, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Sublinear-time reductions for big data computing, A geometric approach to complexity, Faster 3-Coloring of Small-Diameter Graphs, An FPTAS for a vector subset search problem, Deterministic factorization of sums and differences of powers, Continuous One-counter Automata, The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation, Optimal deterministic controller synthesis from steady-state distributions, On measuring inconsistency in definite and indefinite databases with denial constraints, Taking into account ``who said what in abstract argumentation: complexity results, A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules, Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata, A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases, Faster integer multiplication using short lattice vectors, The word problem for finitary automaton groups, Evaluating space measures in P systems, The inverse satisfiability problem, Identities and bases in the Sylvester and Baxter monoids, Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty, Identities in twisted Brauer monoids, Almost disjoint paths and separating by forbidden pairs, On Imperfect Recall in Multi-Agent Influence Diagrams, Maximizing Social Welfare in Score-Based Social Distance Games, The pumping lemma for regular languages is hard, Picturing Counting Reductions with the ZH-Calculus, Faster truncated integer multiplication, Pure Nash equilibria in a generalization of congestion games allowing resource failures