Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
P, NP, and NP-Completeness - MaRDI portal

P, NP, and NP-Completeness

From MaRDI portal

Publication:3066266

Jump to:navigation, search

DOI10.1017/CBO9780511761355zbMath1230.68006OpenAlexW4251610435MaRDI QIDQ3066266

Oded Goldreich

Publication date: 10 January 2011

Full work available at URL: https://doi.org/10.1017/cbo9780511761355

zbMATH Keywords

NP-completeness polynomial time computation P versus NP NP-computability polynomial time checking polynomial time find

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Parameterized complexity classes beyond para-NP ⋮ A new asymptotic notation: Weak Theta ⋮ When the Gomory-chvátal closure coincides with the integer hull ⋮ Randomness and Computation ⋮ Computational complexity, Newton polytopes, and Schubert polynomials ⋮ NP–hard problems naturally arising in knot theory

This page was built for publication: P, NP, and NP-Completeness

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3066266&oldid=16119562"