Publication:4298260
From MaRDI portal
zbMath0833.68049MaRDI QIDQ4298260
Publication date: 26 July 1994
68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D10: Turing machines and related notions
Related Items
Immunity and Simplicity for Exact Counting and Other Counting Classes, On the expressive power of the shuffle operator matched with intersection by regular sets, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, On Shuffle Ideals, Short rational generating functions for lattice point problems, Approximate algorithms for generalized maximum utility problems, Secure information hiding based on computationally intractable problems, Lower Bounds for Las Vegas Automata by Information Theory, 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, The phase transition in random horn satisfiability and its algorithmic implications, Unnamed Item, Unnamed Item, The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences, A user authentication protocol based on the intractability of the 3-coloring problem, On evaluating permanents and a matrix of contangents∗, The ground-negative fragment of first-order logic is -complete, Implicit measurements of dynamic complexity properties and splittings of speedable sets, 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, SOLVABILITY OF SYSTEMS OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS, First-order and counting theories ofω-automatic structures, On the Complexity of Computing Generators of Closed Sets, Some Results on the Expressive Power and Complexity of LSCs, Satisfiability of Algebraic Circuits over Sets of Natural Numbers, CASCADING RANDOM WALKS, 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, 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, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Linear Logic Proof Games and Optimization, The complexity of recursion theoretic games, QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES, NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES, Interpolating greedy and reluctant algorithms, Weak cardinality theorems, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, 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, Tractable constraints on ordered domains, Unnamed Item, Hybrid logics: characterization, interpolation and complexity, Complexity results for prefix grammars, Primal-dual approximation algorithms for a packing-covering pair of problems, Property testers for dense constraint satisfaction programs on finite domains, Checking identities is computationally intractable NP-hard and therefore human provers will always be needed, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, The ultra-weak Ash conjecture and some particular cases, 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, Boolean Logics with Relations, Computation of Renameable Horn Backdoors, 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, 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, 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, Arthur and Merlin as Oracles, Strategic Agent Communication: An Argumentation-Driven Approach, An Algorithm for SAT Without an Extraction Phase, Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems, Constraint Propagation with Tabu List for Min-Span Frequency Assignment Problem, Horn representation of a concept lattice, 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, Unnamed Item, Unnamed Item, Query Order, Finite Variable Logics in Descriptive Complexity Theory, Logics which capture complexity classes over the reals, 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., Reductions and functors from problems to word problems, The zero-one law holds for BPP, Intractability of decision problems for finite-memory automata, Computational complexity of planning and approximate planning in the presence of incompleteness, Clique is hard to approximate within \(n^{1-\epsilon}\), The complexity of approximating MAPs for belief networks with bounded probabilities, Satisfying subtype inequalities in polynomial space, Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem., Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees, On the reducibility of sets inside NP to sets with low information content, On the generation of circuits and minimal forbidden sets, 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, Competing provers yield improved Karp-Lipton collapse results, A probabilistic model of computing with words, Generalizations of matched CNF formulas, On deciding subsumption problems, The center location improvement problem under the Hamming distance, 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, 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, The archievable region method in the optimal control of queueing systems; formulations, bounds and policies, On logics with two variables, Hard sets are hard to find, Data independence of read, write, and control structures in PRAM computations, The maximum number of Hamiltonian cycles in graphs with a fixed number of vertices and edges, Probabilistic verification of proofs in calculuses, 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, 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, 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, Orthogonal representations over finite fields and the chromatic number of graphs, Clustering with qualitative information, On the hardness of approximating the min-hack problem, Discrete quantum walks hit exponentially faster, All superlinear inverse schemes are coNP-hard, A note on the circuit complexity of PP, Parameterized counting problems, 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, Boolean functions as models for quantified Boolean formulas, Learning parallel portfolios of algorithms, Local Transition Functions of Quantum Turing Machines, 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, Time-space tradeoffs for SAT on nonuniform machines, Integer circuit evaluation is PSPACE-complete, On the complexity of typechecking top-down XML transformations, 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, 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, Probabilistic logic under coherence: complexity and algorithms, 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 computational complexity of evolutionarily stable strategies, Partitioning a weighted partial order, Relations between average-case and worst-case complexity, Martingale families and dimension in P, 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, Complexity of DNF minimization and isomorphism testing for monotone formulas, Solutions to computational problems through gene assembly, 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, Universal relations and {\#}P-completeness, Partially commutative inverse monoids., 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, Quantified coalition logic, Minimum weakly fundamental cycle bases are hard to find, Partially ordered connectives and monadic monotone strict NP, 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 random generation and counting of matchings in dense graphs, Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems, 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, On the concavity of delivery games, \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\), Succinctness as a source of complexity in logical formalisms, Sensitivity analysis for knapsack problems: Another negative result, The complexity of cover inequality separation, First-order linear logic without modalities is NEXPTIME-hard, 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, 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}\)?
