Automatically assigned DDC number: 0040151
Manually assigned DDC number: 0040151

Number of references: 8

Title: Locating P/poly Optimally in the Extended Low Hierarchy

Author:

Author:

Subject: J. Kobler,Abteilung Fur Theoretische Informatik Locating P/poly Optimally in the Extended Low Hierarchy

Description: The low hierarchy within NP and the extended low hierarchy have turned out to be very useful in classifying many interesting language classes. We relocate P=poly from the third Sigma-level EL P;Sigma 3 (Balc'azar et al., 1986) to the third Theta-level EL P;Theta 3 of the extended low hierarchy. The location of P=poly in EL P;Theta 3 is optimal since, as shown by Allender and Hemachandra (1992), there exist sparse sets that are not contained in the next lower level EL P;Sigma 2 . As a consequence of our result, all NP sets in P=poly are relocated from the third Sigma-level L P;Sigma 3 (Ko and Schoning, 1985) to the third Theta-level L P;Theta 3 of the low hierarchy. 1 Introduction Based on ideas from recursive function theory, Schoning [Sc83] introduced the low and high hierarchies inside NP which turned out to be very useful in classifying decision problems in NP not known to be NP-complete or in P. In order to characterize the complexity of language classes not contai...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1998-05-18

Pubyear: 1993

Format: ps

Identifier: http://citeseer.ist.psu.edu/151685.html

Source: ftp://theorie.informatik.uni-ulm.de/pub/papers/ti/extlow.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml version="1.0" encoding="UTF-8"?>

<references_metadata>

<rec ID="/552485.html" Type="article" CiteSeer_Book="Journal of the ACM" CiteSeer_Volume="39" Title="Lower Bounds for the Low Hierarchy,">

<identifier Org="ISBN:0387529535" Paper_ID="/552485.html" Extracted="0387529535" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:0546654835" Paper_ID="/552485.html" Extracted="0546654835" />

<identifier Org="ISBN:0792343964" Paper_ID="/552485.html" Extracted="0792343964" DDC="511/.8" Normalized_DDC="5118" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:0818622555" Paper_ID="/552485.html" Extracted="0818622555" />

<identifier Org="ISBN:081862955X" Paper_ID="/552485.html" Extracted="081862955X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540221476" Paper_ID="/552485.html" Extracted="3540221476" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540281932" Paper_ID="/552485.html" Extracted="3540281932" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540424946" Paper_ID="/552485.html" Extracted="3540424946" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:354051371X" Paper_ID="/552485.html" Extracted="354051371X" />

<identifier Org="ISBN:3540552103" Paper_ID="/552485.html" Extracted="3540552103" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540558403" Paper_ID="/552485.html" Extracted="3540558403" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540562796" Paper_ID="/552485.html" Extracted="3540562796" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540565035" Paper_ID="/552485.html" Extracted="3540565035" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540569391" Paper_ID="/552485.html" Extracted="3540569391" />

<identifier Org="ISBN:3540613323" Paper_ID="/552485.html" Extracted="3540613323" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />

</rec>

<rec ID="/132943.html" Type="article" CiteSeer_Book="Electronic Colloquium on Computational Complexity ECCC" CiteSeer_Volume="" Title="Some Connections between Bounded Query Classes and Non-Uniform Complexity,">

<identifier Org="ISBN:0521635500" Paper_ID="/132943.html" Extracted="0521635500" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0769506755" Paper_ID="/132943.html" Extracted="0769506755" />

<identifier Org="ISBN:0769510531" Paper_ID="/132943.html" Extracted="0769510531" />

<identifier Org="ISBN:0818620722" Paper_ID="/132943.html" Extracted="0818620722" />

<identifier Org="ISBN:0818622555" Paper_ID="/132943.html" Extracted="0818622555" />

<identifier Org="ISBN:081862955X" Paper_ID="/132943.html" Extracted="081862955X" />

<identifier Org="ISBN:0818643706" Paper_ID="/132943.html" Extracted="0818643706" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0818656727" Paper_ID="/132943.html" Extracted="0818656727" DDC="004.015113" Normalized_DDC="004015113" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0818680377" Paper_ID="/132943.html" Extracted="0818680377" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0824700260" Paper_ID="/132943.html" Extracted="0824700260" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0897913973" Paper_ID="/132943.html" Extracted="0897913973" />

<identifier Org="ISBN:3540228233" Paper_ID="/132943.html" Extracted="3540228233" DDC="004.1" Normalized_DDC="0041" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540287027" Paper_ID="/132943.html" Extracted="3540287027" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540424962" Paper_ID="/132943.html" Extracted="3540424962" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540529217" Paper_ID="/132943.html" Extracted="3540529217" DDC="511/.8" Normalized_DDC="5118" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540557199" Paper_ID="/132943.html" Extracted="3540557199" DDC="005.13/1" Normalized_DDC="005131" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540565035" Paper_ID="/132943.html" Extracted="3540565035" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540613323" Paper_ID="/132943.html" Extracted="3540613323" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:9810214626" Paper_ID="/132943.html" Extracted="9810214626" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />

</rec>

<rec ID="/364105.html" Type="article" CiteSeer_Book="Mathematical Systems Theory" CiteSeer_Volume="29" Title="Upper Bounds for the Complexity of Sparse and Tally Descriptions,">

<identifier Org="ISBN:3540648275" Paper_ID="/364105.html" Extracted="3540648275" />

<identifier Org="ISBN:354065691X" Paper_ID="/364105.html" Extracted="354065691X" DDC="004" Normalized_DDC="004" Normalized_Weight="1.0" />

</rec>

<rec ID="/522386.html" Type="article" CiteSeer_Book="Theoretical Computer Science" CiteSeer_Volume="84" Title="Bounded Queries to {SAT} and the Boolean Hierarchy,">

<identifier Org="ISBN:0387529535" Paper_ID="/522386.html" Extracted="0387529535" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0387557075" Paper_ID="/522386.html" Extracted="0387557075" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0769510531" Paper_ID="/522386.html" Extracted="0769510531" />

<identifier Org="ISBN:0818608668" Paper_ID="/522386.html" Extracted="0818608668" DDC="511" Normalized_DDC="511" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0818619589" Paper_ID="/522386.html" Extracted="0818619589" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0818622555" Paper_ID="/522386.html" Extracted="0818622555" />

<identifier Org="ISBN:081862955X" Paper_ID="/522386.html" Extracted="081862955X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0818643706" Paper_ID="/522386.html" Extracted="0818643706" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540194886" Paper_ID="/522386.html" Extracted="3540194886" />

<identifier Org="ISBN:354050110X" Paper_ID="/522386.html" Extracted="354050110X" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540514988" Paper_ID="/522386.html" Extracted="3540514988" />

<identifier Org="ISBN:3540552103" Paper_ID="/522386.html" Extracted="3540552103" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540565035" Paper_ID="/522386.html" Extracted="3540565035" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540602496" Paper_ID="/522386.html" Extracted="3540602496" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540620346" Paper_ID="/522386.html" Extracted="3540620346" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:354065691X" Paper_ID="/522386.html" Extracted="354065691X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540875301" Paper_ID="/522386.html" Extracted="3540875301" />

</rec>

<rec ID="/249902.html" Type="inproceedings" CiteSeer_Book="Structure in Complexity Theory Conference" CiteSeer_Volume="" Title="{SPARSE} reduces conjunctively to {TALLY},">

<identifier Org="ISBN:0387948686" Paper_ID="/249902.html" Extracted="0387948686" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:0818640707" Paper_ID="/249902.html" Extracted="0818640707" />

<identifier Org="ISBN:0897917103" Paper_ID="/249902.html" Extracted="0897917103" DDC="004.36" Normalized_DDC="00436" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540221476" Paper_ID="/249902.html" Extracted="3540221476" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540562796" Paper_ID="/249902.html" Extracted="3540562796" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540578110" Paper_ID="/249902.html" Extracted="3540578110" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540591753" Paper_ID="/249902.html" Extracted="3540591753" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540637745" Paper_ID="/249902.html" Extracted="3540637745" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540671412" Paper_ID="/249902.html" Extracted="3540671412" DDC="004.01511" Normalized_DDC="00401511" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540674195" Paper_ID="/249902.html" Extracted="3540674195" DDC="003" Normalized_DDC="003" Normalized_Weight="0.1111111111111111" />

</rec>

<rec ID="/79283.html" Type="article" CiteSeer_Book="Journal of the ACM" CiteSeer_Volume="41" Title="Instance Complexity,">

<identifier Org="ISBN:0387948686" Paper_ID="/79283.html" Extracted="0387948686" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.1" />

<identifier Org="ISBN:0818620722" Paper_ID="/79283.html" Extracted="0818620722" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.1" />

<identifier Org="ISBN:081862955X" Paper_ID="/79283.html" Extracted="081862955X" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.1" />

<identifier Org="ISBN:0818656727" Paper_ID="/79283.html" Extracted="0818656727" DDC="004.015113" Normalized_DDC="004015113" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540164863" Paper_ID="/79283.html" Extracted="3540164863" DDC="511" Normalized_DDC="511" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540529217" Paper_ID="/79283.html" Extracted="3540529217" />

<identifier Org="ISBN:3540557199" Paper_ID="/79283.html" Extracted="3540557199" DDC="005.13/1" Normalized_DDC="005131" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540590420" Paper_ID="/79283.html" Extracted="3540590420" DDC="004/.01/511" Normalized_DDC="00401511" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540634371" Paper_ID="/79283.html" Extracted="3540634371" DDC="004.0151" Normalized_DDC="0040151" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540642307" Paper_ID="/79283.html" Extracted="3540642307" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540671412" Paper_ID="/79283.html" Extracted="3540671412" DDC="004.01511" Normalized_DDC="00401511" Normalized_Weight="0.1" />

<identifier Org="ISBN:3642009816" Paper_ID="/79283.html" Extracted="3642009816" />

<identifier Org="ISBN:9514535634" Paper_ID="/79283.html" Extracted="9514535634" />

<identifier Org="ISBN:9514555260" Paper_ID="/79283.html" Extracted="9514555260" />

</rec>

<rec ID="/342855.html" Type="inproceedings" CiteSeer_Book="Symposium on Theoretical Aspects of Computer Science" CiteSeer_Volume="" Title="The Extended Low Hierarchy Is an Infinite Hierarchy,">

<identifier Org="ISBN:0546655416" Paper_ID="/342855.html" Extracted="0546655416" />

<identifier Org="ISBN:0818656727" Paper_ID="/342855.html" Extracted="0818656727" DDC="004.015113" Normalized_DDC="004015113" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3519003155" Paper_ID="/342855.html" Extracted="3519003155" />

<identifier Org="ISBN:3540221476" Paper_ID="/342855.html" Extracted="3540221476" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540281932" Paper_ID="/342855.html" Extracted="3540281932" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540422005" Paper_ID="/342855.html" Extracted="3540422005" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540552103" Paper_ID="/342855.html" Extracted="3540552103" />

<identifier Org="ISBN:3540557199" Paper_ID="/342855.html" Extracted="3540557199" DDC="005.13/1" Normalized_DDC="005131" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540562796" Paper_ID="/342855.html" Extracted="3540562796" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540565035" Paper_ID="/342855.html" Extracted="3540565035" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540613323" Paper_ID="/342855.html" Extracted="3540613323" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1111111111111111" />

<identifier Org="ISBN:3540674195" Paper_ID="/342855.html" Extracted="3540674195" DDC="003" Normalized_DDC="003" Normalized_Weight="0.1111111111111111" />

</rec>

<rec ID="/123463.html" Type="inproceedings" CiteSeer_Book="Mathematical Foundations of Computer Science" CiteSeer_Volume="" Title="On the Complexity of Small Description and Related Topics,">

<identifier Org="ISBN:354055808X" Paper_ID="/123463.html" Extracted="354055808X" />

</rec>

<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Locating P/poly Optimally in the Extended Low Hierarchy">

<identifier Org="ISBN:0792343964" Paper_ID="SELF" Extracted="0792343964" DDC="511/.8" Normalized_DDC="5118" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:0817636803" Paper_ID="SELF" Extracted="0817636803" DDC="511/.5" Normalized_DDC="5115" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540221476" Paper_ID="SELF" Extracted="3540221476" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540422005" Paper_ID="SELF" Extracted="3540422005" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540565035" Paper_ID="SELF" Extracted="3540565035" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540569391" Paper_ID="SELF" Extracted="3540569391" />

<identifier Org="ISBN:3540578110" Paper_ID="SELF" Extracted="3540578110" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540583254" Paper_ID="SELF" Extracted="3540583254" />

<identifier Org="ISBN:3540600841" Paper_ID="SELF" Extracted="3540600841" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540613323" Paper_ID="SELF" Extracted="3540613323" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540648275" Paper_ID="SELF" Extracted="3540648275" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:3540674195" Paper_ID="SELF" Extracted="3540674195" DDC="003" Normalized_DDC="003" Normalized_Weight="0.09090909090909091" />

<identifier Org="ISBN:9051835361" Paper_ID="SELF" Extracted="9051835361" DDC="510.9" Normalized_DDC="5109" Normalized_Weight="0.09090909090909091" />

</rec>

</references_metadata>