Complexity problems in computational theory

DOI10.1070/RM1981V036N06ABEH003102MaRDI QIDQ3967050zbMATH OpenOpenAlexFDO

Authors 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

arithmetical operationscompleteness problemscomplexity classescomplexity hierarchiescomputation theoryeffective algorithmsgeometrical problemsgraph problemsproblems with at least exponential lower complexity boundproblems with nontrivial lower complexity boundsolution of equationsstring matchingsurvey

Mathematics Subject Classification ID

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

Cited in

(5)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3967050)