scientific article; zbMATH DE number 1303203

zbMath0936.03041MaRDI QIDQ4249726

William I. Gasarch

Publication date: 15 May 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

surveyarithmetic hierarchyrecursive functionconstructive proofsrecursive combinatorics

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Theory of numerations, effectively presented structures (03D45)

Related Items (16)

Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete ⋮ The complexity of optimization problems ⋮ Primitive recursive reverse mathematics ⋮ Unnamed Item ⋮ Domatic partitions of computable graphs ⋮ Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems ⋮ Computing planarity in computable planar graphs ⋮ Generalizations of Opt P to the polynomial hierarchy ⋮ Graph Ramsey theory and the polynomial hierarchy ⋮ Forbidden substructures and combinatorial dichotomies: WQO and universality ⋮ Undecidability of equality for codata types ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case ⋮ Index sets for \(\Pi^0_1\) classes ⋮ Unnamed Item ⋮ Reverse Mathematics and Recursive Graph Theory ⋮ One query reducibilities between partial information classes

This page was built for publication: