Arithmetical hierarchy and complexity of computation
type: Item
instance of: scholarly article
title: Arithmetical hierarchy and complexity of computation
zbMATH Open document ID: 0402.03038
DOI: 10.1016/0304-3975(79)90046-X
published in: Theoretical Computer Science
publication date: 1979-01-01T00:00:00Z
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D20
zbMATH DE Number: 3623540
zbMATH Keywords: Complete Sets of Turing Machines
zbMATH Keywords: Arithmetical Hierarchy
zbMATH Keywords: Provable Complexity Classes
author: Petr Hájek
MaRDI profile type: Publication
cites work: On the computational power of pushdown automata
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: The complexity of theorem-proving procedures
cites work: Q4107930
cites work: Arithmetization of metamathematics in a general setting
cites work: Q4125776
cites work: Examples of sets definable by means of two and three quantifiers
cites work: Q5573961
full work available at URL: 0304-3975(79)90046-x
OpenAlex ID: W2009621880
description: scientific article; zbMATH DE number 3623540