Circuit-size lower bounds and non-reducibility to sparse sets
type: Item
instance of: scholarly article
title: Circuit-size lower bounds and non-reducibility to sparse sets
zbMATH Open document ID: 0537.94027
DOI: 10.1016/S0019-9958(82)90382-5
published in: Information and Control
publication date: 1982-01-01T00:00:00Z
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3854976
zbMATH Keywords: Boolean circuit
zbMATH Keywords: circuit-size
zbMATH Keywords: reducibility to sparse sets
zbMATH Keywords: polynomial-time hierarchy
zbMATH Keywords: NP
Wikidata QID: Q61877185
author: R. Kannan
MaRDI profile type: Publication
full work available at URL: s0019-9958(82)90382-5
OpenAlex ID: W2092429268
description: scientific article