Complexity problems in computational theory

DOI10.1070/RM1981v036n06ABEH003102zbMath0501.68013OpenAlexW2025146124MaRDI QIDQ3967050

A. O. Slisenko

Publication date: 1981

Published in: Russian Mathematical Surveys (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1070/rm1981v036n06abeh003102

zbMATH Keywords

surveystring matchingeffective algorithmscomplexity classescomputation theorygraph problemssolution of equationscompleteness problemsgeometrical problemscomplexity hierarchiesarithmetical operationsproblems with at least exponential lower complexity boundproblems with nontrivial lower complexity bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (5)

Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity ⋮ Computer algebra: Past and future ⋮ Parallel computations on graphs ⋮ Sorting, linear time and the satisfiability problem ⋮ Unnamed Item

This page was built for publication: Complexity problems in computational theory