ScholarLens Back to search
1985•SIAM Journal on ComputingRequires access

On Circuit-Size Complexity and the Low Hierarchy in NP

Ker‐I Ko, Uwe Schöning

Open publisher page 91 citations

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 $.

About this research paper

What this paper is about

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 $.

Why it matters

OpenAlex reports 91 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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 $.

Key concepts: Nondeterministic algorithm, Polynomial hierarchy, Time hierarchy theorem, Complexity class, Combinatorics, Time complexity, NP, Hierarchy

Related papers

Related paper 1Related paper 2
Back to paper searchBrowse research topicsOriginal source
On Circuit-Size Complexity and the Low Hierarchy in NP — Research Paper | ScholarLens