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>

www.000webhost.com