On Circuit-Size Complexity and the Low Hierarchy in NP
Authors:
- Ker-I KoKKKer-I Ko
- Uwe SchöningUSUwe Schöning
- 1 February 1985
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 14 (1) , 41-51
Abstract
Let A be a set having polynomial size circuits. If A is also known to be in NP, then we may conclude that the graph of the polynomial size circuits for A is actually in $\Pi _2^p $. Using this observation, we show that sets in NP which have polynomial size ciruits are in $L_3^p $, the third level of the low hierarchy in NP. By a similar technique, we are able to show that some other intuitively low sets in NP are in $L_2^p $, and even in a certain refinement of $L_2^p $. As a consequence, sparse sets are not strong nondeterministic polynomial time Turing complete in NP unless the polynomial time hierarchy collapses to $\Delta _2^p $.
Keywords
This publication has 19 references indexed in Scilit:
- On self-reducibility and weak P-selectivityJournal of Computer and System Sciences, 1983
- A note on sparse oracles for NPJournal of Computer and System Sciences, 1982
- A Note on Sparse Complete SetsSIAM Journal on Computing, 1979
- Information content characterizations of complexity theoretic properties1979
- Two theorems on random polynomial time1978
- Relationship between density and deterministic complexity of MP-complete languages1978
- Some lowness properties and computational complexity sequencesTheoretical Computer Science, 1978
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- Tally languages and complexity classesInformation and Control, 1974