scientific article; zbMATH DE number 3568040
From MaRDI portal
Publication:4139697
zbMath0364.68066MaRDI QIDQ4139697
Publication date: 1977
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)
Related Items (25)
Random generation of combinatorial structures from a uniform distribution ⋮ NP is as easy as detecting unique solutions ⋮ The Odds of Staying on Budget ⋮ Some observations on the connection between counting and recursion ⋮ On the power of parity polynomial time ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ Complexity of DNA sequencing by hybridization. ⋮ On measuring inconsistency in definite and indefinite databases with denial constraints ⋮ Discrete extremal problems ⋮ On tape-bounded probabilistic Turing machine acceptors ⋮ Division in idealized unit cost RAMs ⋮ Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis ⋮ The complexity of counting edge colorings for simple graphs ⋮ Decreasing the bandwidth of a transition matrix ⋮ A survey of space complexity ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ Logarithmic advice classes ⋮ Nash equilibria in discrete routing games with convex latency functions ⋮ On sparse hard sets for counting classes ⋮ Multihead two-way probabilistic finite automata ⋮ Counting and enumeration complexity with application to multicriteria scheduling ⋮ Enumerative counting is hard ⋮ Randomised algorithms ⋮ The complexity of counting homeomorphs ⋮ Space-bounded hierarchies and probabilistic computations
This page was built for publication:
