scientific article; zbMATH DE number 3568040

MaRDI QIDQ4139697zbMATH OpenFDO

Authors Janos Simon

Publication date 1977

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)

• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• Counting and enumeration complexity with application to multicriteria scheduling
• 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
• Decreasing the bandwidth of a transition matrix

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)