Classification and complexity of problems.

MaRDI QIDQ2735586zbMATH OpenFDO

Authors Ana Maria de Almeida, Rosália Rodrigues

Publication date 3 September 2001

Published in Textos de Matemática. Série B (Search for Journal in Brave)

zbMATH Keywords

complexity theory

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Review text

This is a short survey (in Portuguese) on complexity theory. The authors review the basic definitions of problem, complexity, classes \(P\), \(NP\) and NP-complete and present the main ideas in the field.

Recommendations

• scientific article; zbMATH DE number 4120160
• Classifying the computational complexity of problems
• Complexity of classification problems
• scientific article; zbMATH DE number 139608
• scientific article; zbMATH DE number 1197456
• Evaluating the complexity of mathematical problems. I
• scientific article; zbMATH DE number 2161249
• Dimension and the structure of complexity classes
• Complexity and categoricity
• A taxonomy of complexity classes of functions

Cited in

(5)

• Overview of some solved NP-complete problems in graph theory
• scientific article; zbMATH DE number 3848608 (Why is no real title available?)
• Improving the classification of complexities
• scientific article; zbMATH DE number 139608 (Why is no real title available?)
• scientific article; zbMATH DE number 218387 (Why is no real title available?)

This page was built for publication: Classification and complexity of problems.

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