ScholarLens Back to search
1988•Unpublished venueRequires access

The polynomial time hierarchy collapses if the Boolean hierarchy collapses

Jim Kadin

Open publisher page 21 citations

Abstract

It is shown that if the Boolean hierarchy (BH) collapses, then there exists a sparse set S such that co-NP contained in NP/sup S/, and therefore the polynomial-time hierarchy (PH) collapses to a subclass of Delta P/3. Since the BH is contained in P/sup NP/, these results relate the internal structure of P/sup NP/ to the structure of the PH as a whole. Other conditions that imply the collapse of the BH (and the collapse of the PH in turn) are examined.>

About this research paper

What this paper is about

It is shown that if the Boolean hierarchy (BH) collapses, then there exists a sparse set S such that co-NP contained in NP/sup S/, and therefore the polynomial-time hierarchy (PH) collapses to a subclass of Delta P/3. Since the BH is contained in P/sup NP/, these results relate the internal structure of P/sup NP/ to the structure of the PH as a whole. Other conditions that imply the collapse of the BH (and the collapse of the PH in turn) are examined.>

Why it matters

OpenAlex reports 21 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

It is shown that if the Boolean hierarchy (BH) collapses, then there exists a sparse set S such that co-NP contained in NP/sup S/, and therefore the polynomial-time hierarchy (PH) collapses to a subclass of Delta P/3. Since the BH is contained in P/sup NP/, these results relate the internal structure of P/sup NP/ to the structure of the PH as a whole. Other conditions that imply the collapse of the BH (and the collapse of the PH in turn) are examined.>

Key concepts: Hierarchy, Polynomial hierarchy, Combinatorics, Time complexity, Mathematics, Set (abstract data type), Boolean data type, Polynomial

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
The polynomial time hierarchy collapses if the Boolean hierarchy collapses — Research Paper | ScholarLens