scientific article; zbMATH DE number 192916
From MaRDI portal
Publication:4039803
bibliographycircuit complexitycomplete problemscomplexity classescomplexity theorydiagonalizationP-NP-problempolynomial time hierarchyProbabilistic algorithmsstructural complexitystructural propertiesTuring machines
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25)
Cited in
(only showing first 100 items - show all)- Complexity and structure
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- Bounded queries to SAT and the Boolean hierarchy
- On random oracle separations
- On p-creative sets and p-completely creative sets
- Almost everywhere high nonuniform complexity
- A survey of space complexity
- On polynomial-time Turing and many-one completeness in PSPACE
- A note on two-way probabilistic automata
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- Complexity of logical theories involving coprimality
- Deciding bisimilarity is P-complete
- On the computational complexity of integral equations
- Unambiguity of circuits
- Circuit size relative to pseudorandom oracles
- On 1-truth-table-hard languages
- A positive relativization of polynomial time versus polylog space
- A note on sparse sets and the polynomial-time hierarchy
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- Saturation and stability in the theory of computation over the reals
- The alternation hierarchy for sublogarithmic space is infinite
- A modal perspective on the computational complexity of attribute value grammar
- A note on SpanP functions
- One-way functions and the isomorphism conjecture
- Simple characterizations of \(P(\# P)\) and complete problems
- Computational depth and reducibility
- A note on the density of oracle decreasing time-space complexity
- Listing graphs that satisfy first-order sentences
- Finite-valued distance automata
- On the computational power of dynamical systems and hybrid systems
- The simple dynamics of super Turing theories
- On resource-bounded instance complexity
- An excursion to the Kolmogorov random strings
- Counting quantifiers, successor relations, and logarithmic space
- A reducibility concept for problems defined in terms of ordered binary decision diagrams
- Index sets and presentations of complexity classes
- Gap-languages and log-time complexity classes
- An oracle builder's toolkit
- Optimal proof systems imply complete sets for promise classes
- Test sets for the universal and existential closure of regular tree languages.
- On the simulation of quantum Turing machines.
- Resource bounded randomness and computational complexity
- Undecidability results for low complexity time classes
- Exact learning via teaching assistants
- The counting complexity of group-definable languages
- Stochastic analog networks and computational complexity
- Transfer theorems via sign conditions
- On the computational structure of the connected components of a hard problem
- Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
- Multi-head finite automata: Data-independent versus data-dependent computations
- Sparse selfreducible sets and nonuniform lower bounds
- TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable
- The price of universality
- On the Hamming distance of constraint satisfaction problems.
- Deterministic Turing machines in the range between real-time and linear-time.
- One complexity theorist's view of quantum computing
- Alternating and empty alternating auxiliary stack automata.
- Assembling molecules in ATOMIX is hard
- Nonuniform lowness and strong nonuniform lowness
- Toughness, hamiltonicity and split graphs
- On the geometric separability of Boolean functions
- Entanglement and the complexity of directed graphs
- Non-uniform reductions
- Max NP-completeness made easy
- Two queries
- A bounded arithmetic AID for Frege systems
- \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration
- Bounded truth table does not reduce the one-query tautologies to a random oracle
- Polynomial recognition of equal unions in hypergraphs with few vertices of large degree
- Model checking abilities of agents: a closer look
- Combined hierarchies of finite random access machines
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Graph Isomorphism is in SPP
- How much can analog and hybrid systems be proved (super-)Turing
- Sets without subsets of higher many-one degree
- A common algebraic description for probabilistic and quantum computations
- A reducibility for the dot-depth hierarchy
- A note on the circuit complexity of PP
- On approximate learning by multi-layered feedforward circuits
- On the typical case complexity of graph optimization
- Machines that perform measurements
- The complexity of searching implicit graphs
- A characterization of the leaf language classes
- Coloring Jacobians revisited: a new algorithm for star and acyclic bicoloring
- Sparse sets, approximable sets, and parallel queries to NP
- Classes of bounded nondeterminism
- Limits to measurement in experiments governed by algorithms
- Axiomatizing resource bounds for measure
- Complexity issues for preorders on finite labeled forests
- On the complexity of Szilard languages of regulated grammars
- Do there exist complete sets for promise classes?
- Self-reducible sets of small density
- Reducibilities on tally and sparse sets
- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
- Limitations of the upward separation technique
- scientific article; zbMATH DE number 4166857 (Why is no real title available?)
- On the Complexity of Measurement in Classical Physics
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
- A Characterisation of NL Using Membrane Systems without Charges and Dissolution
- Extending regular expressions with homomorphic replacement
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 Q4039803)
