Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory

DOI10.1137/1036051zbMath0819.68057OpenAlexW2077014640MaRDI QIDQ4305363

Ronald V. Book

Publication date: 5 September 1995

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1036051

zbMATH Keywords

NP-completenesscomplete setsstructural complexity theoryrelativized computationreducibilities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Sparse parameterized problems

This page was built for publication: Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory