A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms

DOI10.1109/MAHC.1984.10036zbMath0998.01527OpenAlexW2165813048WikidataQ55878463 ScholiaQ55878463MaRDI QIDQ4779250

B. A. Trakhtenbrot

Publication date: 25 November 2002

Published in: IEEE Annals of the History of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/mahc.1984.10036

Mathematics Subject Classification ID

History of mathematics in the 20th century (01A60) History of computer science (68-03)

Related Items

On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \), Minimum Circuit Size, Graph Isomorphism, and Related Problems, Relativized alternation and space-bounded computation, Boris Abramovich Trakhtenbrot, A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem, Discrete logarithm and minimum circuit size, Zero knowledge and circuit minimization, The minimum oracle circuit size problem, Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Physical portrayal of computational complexity, Revisiting maximum satisfiability and related problems in data streams, The power of natural properties as oracles, On an optimal randomized acceptor for graph nonisomorphism, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions, A historical note on the complexity of scheduling problems, Revisiting maximum satisfiability and related problems in data streams, Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity, Physical consequences of P≠NP and the density matrix renormalization group annealing conjecture, Inductive Complexity of P versus NP Problem, Minimum Circuit Size, Graph Isomorphism, and Related Problems, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, From Logic to Theoretical Computer Science – An Update, The non-hardness of approximating circuit size, Unnamed Item, Unnamed Item, $$P\mathop{ =}\limits^{?}NP$$, Time-space tradeoffs for satisfiability, Kolmogorov characterizations of complexity classes