scientific article; zbMATH DE number 2226428

MaRDI QIDQ5703379zbMATH OpenFDO

Authors Alexander Razborov

Publication date 8 November 2005

zbMATH Keywords

brute force search theory of algorithmsTuring machines

Mathematics Subject Classification ID

History of mathematics in the 20th century (01A60) History of mathematical logic and foundations (03-03) Proof theory in general (including proof-theoretic semantics) (03F03) Combinatorial identities, bijective combinatorics (05A19) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 1157651
• scientific article; zbMATH DE number 863498
• scientific article; zbMATH DE number 218387
• scientific article; zbMATH DE number 2167361
• scientific article; zbMATH DE number 2079850
• scientific article; zbMATH DE number 3917675
• New Computational Paradigms

Cited in

(8)

• A brief history of NP-completeness, 1954--2012
• Reducibility among combinatorial problems
• Algorithmics -- is there hope for a unified theory? (Invited talk)
• Beyond NP
• Reducibility among combinatorial problems (1972)
• \({\mathcal P}\), \({\mathcal{NP}}\) and mathematics -- a computational complexity perspective
• scientific article; zbMATH DE number 7676615 (Why is no real title available?)
• In some curved spaces, one can solve NP-hard problems in polynomial time

This page was built for publication:

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