Randomised algorithms
From MaRDI portal
Publication:1836980
DOI10.1016/0166-218X(83)90023-9zbMath0506.68040OpenAlexW4212805448MaRDI QIDQ1836980
Publication date: 1983
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(83)90023-9
combinatorial optimizationhierarchiesprimality testsmatrix multiplicationpolynomial multiplicationchecking polynomial identitieslanguages recognisable by randomised algorithmsperfect matchings in graphsrandomly decidable languages
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)
Related Items
An analysis of Monte Carlo algorithms for counting problems, On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes, A randomised 3-colouring algorithm, A survey of space complexity, BPP and the polynomial hierarchy, Combinatorics and connectionism
Cites Work
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Gaussian elimination is not optimal
- The Complexity of Enumeration and Reliability Problems
- New Fast Algorithms for Matrix Operations
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Random Graph Isomorphism
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Probabilistic Algorithms in Finite Fields
- A Fast Monte-Carlo Test for Primality
- Computational Complexity of Probabilistic Turing Machines
- Paths, Trees, and Flowers
- Relativized questions involving probabilistic algorithms
- Factoring Polynomials Over Large Finite Fields
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
