scientific article; zbMATH DE number 3568040

zbMATH Open0364.68066MaRDI QIDQ4139697FDOQ4139697

Authors: Janos Simon 

Publication date: 1977

Title of this publication is not available (Why is that?)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Turing machines and related notions (03D10)

Cited In (26)

• On tape-bounded probabilistic Turing machine acceptors
• Some observations on the connection between counting and recursion
• Nash equilibria in discrete routing games with convex latency functions
• Enumerative counting is hard
• The complexity of counting edge colorings for simple graphs
• Space-bounded hierarchies and probabilistic computations
• Random generation of combinatorial structures from a uniform distribution
• Complexity and enumeration in models of genome rearrangement
• Logarithmic advice classes
• On sparse hard sets for counting classes
• The odds of staying on budget
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Discrete extremal problems
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• NP is as easy as detecting unique solutions
• Complexity of DNA sequencing by hybridization.
• Multihead two-way probabilistic finite automata (extended abstract)
• On measuring inconsistency in definite and indefinite databases with denial constraints
• A survey of space complexity
• Division in idealized unit cost RAMs
• The complexity of counting homeomorphs
• On the power of parity polynomial time
• Randomised algorithms
• Counting and enumeration complexity with application to multicriteria scheduling
• Decreasing the bandwidth of a transition matrix
• The complexity of approximating bounded-degree Boolean \(\#\)CSP

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 Q4139697)