Publication:4942157
From MaRDI portal
zbMath1001.68050MaRDI QIDQ4942157
Publication date: 20 March 2000
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Polynomial-time right-ideal morphisms and congruences, On the Complexity of Convex Hulls of Subsets of the Two-Dimensional Plane, On the Complexity of the Pancake Problem, Jordan Curves with Polynomial Inverse Moduli of Continuity, Unnamed Item, $LINSPACE$ конструктивный аналог функции $(1+x)^h$, On the complexity of the pancake problem, Managing complexity in industrial collaborations, Algorithms for randomized time-varying knapsack problems, A semantically secure public key cryptoscheme using bit-pair shadows, A provably secure non-iterative hash function resisting birthday attack, On parallel complexity of analytic functions, On testing monomials in multivariate polynomials, Space functions and space complexity of the word problem in semigroups., A public key cryptosystem based on three new provable problems, Finding quasi core with simulated stacked neural networks, Computational ludics, The computational complexity of distance functions of two-dimensional domains, New dominating sets in social networks, On positive influence dominating sets in social networks, Observations on complete sets between linear time and polynomial time, Levels of undecidability in rewriting, Lower bounds and the hardness of counting properties, Accepting networks of genetic processors are computationally complete, Asymptotic granularity reduction and its application, Group coloring is \(\Pi_2^{\text{P}}\)-complete, Influence maximization problem: properties and algorithms, A note on quadratic residuosity and UP, On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain, On the complexity of computing the logarithm and square root functions on a complex domain, Conformant plans and beyond: principles and complexity, A note on width-parameterized SAT: an exact machine-model characterization, Non-unique probe selection and group testing, Jordan curves with polynomial inverse moduli of continuity, Minimal achievable approximation ratio for MAX-MQ in finite fields, On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts, Theory of one-tape linear-time Turing machines, Simple explanation of the no-free-lunch theorem and its implications, Polynomially-bounded Dehn functions of groups, Positive influence domination in graphs, Liouville numbers and the computational complexity of changing bases, On the complexity of conversion between classic real number representations, A new algorithm design technique for hard problems, Polynomial upper bounds on the size of changes of a RAM+BOOL program as a tool for proving belonging to FP, Computation of algebraic numbers and arithmetic operations over them with linear memory, Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem, The word problem of the Brin-Thompson group is \textsf{coNP}-complete, \(\mathbf P =\mathbf{NP}\) for some structures over the binary words, Relativized collapsing between BPP and PH under stringent oracle access, Polynomial time quantum computation with advice, On the complexity of computing the Hausdorff distance, On the complexity of non-unique probe selection, Computational power of infinite quantum parallelism, Resource bounded immunity and simplicity, Space functions of groups, Function operators spanning the arithmetical and the polynomial hierarchy, Smale’s 17th problem: Average polynomial time to compute affine and projective solutions, A Public Key Cryptoscheme Using Bit-Pairs with Provable Semantical Security, In Memoriam: Ker-I Ko (1950–2018), The polynomial hierarchy for some structures over the binary words, Improved lower bounds on the randomized complexity of graph properties, Complexity and Algorithms for Well-Structured k-SAT Instances, Arthur and Merlin as Oracles
