<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//TaxonX//DTD Taxonomic Treatment Publishing DTD v0 20100105//EN" "../../nlm/tax-treatment-NS0.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:tp="http://www.plazi.org/taxpub" article-type="research-article" dtd-version="3.0" xml:lang="en">
  <front>
    <journal-meta>
      <journal-id journal-id-type="publisher-id">109</journal-id>
      <journal-id journal-id-type="index">urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891</journal-id>
      <journal-title-group>
        <journal-title xml:lang="en">JUCS - Journal of Universal Computer Science</journal-title>
        <abbrev-journal-title xml:lang="en">jucs</abbrev-journal-title>
      </journal-title-group>
      <issn pub-type="ppub">0948-695X</issn>
      <issn pub-type="epub">0948-6968</issn>
      <publisher>
        <publisher-name>Journal of Universal Computer Science</publisher-name>
      </publisher>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi">10.3217/jucs-003-03-0197</article-id>
      <article-id pub-id-type="publisher-id">27343</article-id>
      <article-categories>
        <subj-group subj-group-type="heading">
          <subject>Research Article</subject>
        </subj-group>
      </article-categories>
      <title-group>
        <article-title>Polynomial-Time Multi-Selectivity</article-title>
      </title-group>
      <contrib-group content-type="authors">
        <contrib contrib-type="author" corresp="yes">
          <name name-style="western">
            <surname>Hemaspaandra</surname>
            <given-names>Lane A.</given-names>
          </name>
          <email xlink:type="simple">lane@cs.rochester.edu</email>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Jiang</surname>
            <given-names>Zhigen</given-names>
          </name>
          <xref ref-type="aff" rid="A2">2</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Rothe</surname>
            <given-names>Joerg</given-names>
          </name>
          <xref ref-type="aff" rid="A3">3</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Watanabe</surname>
            <given-names>Osamu</given-names>
          </name>
          <xref ref-type="aff" rid="A4">4</xref>
        </contrib>
      </contrib-group>
      <aff id="A1">
        <label>1</label>
        <addr-line content-type="verbatim">Department of Computer Science, University of Rochester, Rochester, NY, United States of America</addr-line>
        <institution>Department of Computer Science, University of Rochester</institution>
        <addr-line content-type="city">Rochester, NY</addr-line>
        <country>United States of America</country>
      </aff>
      <aff id="A2">
        <label>2</label>
        <addr-line content-type="verbatim">Institute of Software, Chinese Academy of Sciences, , China</addr-line>
        <institution>Institute of Software, Chinese Academy of Sciences</institution>
        <country>China</country>
      </aff>
      <aff id="A3">
        <label>3</label>
        <addr-line content-type="verbatim">Institut fuer Informatik, Friedrich-Schiller-Universität Jena, , Germany</addr-line>
        <institution>Institut fuer Informatik, Friedrich-Schiller-Universität Jena</institution>
        <country>Germany</country>
      </aff>
      <aff id="A4">
        <label>4</label>
        <addr-line content-type="verbatim">Tokyo Institute of Technology, , Japan</addr-line>
        <institution>Tokyo Institute of Technology</institution>
        <country>Japan</country>
      </aff>
      <author-notes>
        <fn fn-type="corresp">
          <p>Corresponding author: Lane A. Hemaspaandra (<email xlink:type="simple">lane@cs.rochester.edu</email>).</p>
        </fn>
        <fn fn-type="edited-by">
          <p>Academic editor: </p>
        </fn>
      </author-notes>
      <pub-date pub-type="collection">
        <year>1997</year>
      </pub-date>
      <pub-date pub-type="epub">
        <day>28</day>
        <month>03</month>
        <year>1997</year>
      </pub-date>
      <volume>3</volume>
      <issue>3</issue>
      <fpage>197</fpage>
      <lpage>229</lpage>
      <uri content-type="arpha" xlink:href="http://openbiodiv.net/26500BD1-9E0E-5764-AA60-2AC3EC1C33C4">26500BD1-9E0E-5764-AA60-2AC3EC1C33C4</uri>
      <uri content-type="zenodo_dep_id" xlink:href="https://zenodo.org/record/6995350">6995350</uri>
      <permissions>
        <copyright-statement>Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe, Osamu Watanabe</copyright-statement>
        <license license-type="creative-commons-attribution" xlink:href="" xlink:type="simple">
          <license-p>This article is freely available under the J.UCS Open Content License.</license-p>
        </license>
      </permissions>
      <abstract>
        <label>Abstract</label>
        <p>We introduce a generalization of Selman s P-selectivity that yields a more flexible notion of selectivity, called (polynomial-time) multi-selectivity, in which the selector is allowed to operate on multiple input strings. Since our introduction of this class, it has been used [HJRW] to prove the first known (and optimal) lower bounds for generalized selectivity-like classes in terms of EL2 , the second level of the extended low hierarchy. We study the resulting selectivity hierarchy, denoted by SH, which we prove does not collapse. In particular, we study the internal structure and the properties of SH and completely establish, in terms of incomparability and strict inclusion, the relations between our generalized selectivity classes and Ogihara s P-mc (polynomial-time membership-comparable) classes. Although SH is a strictly increasing infinite hierarchy, we show that the core results that hold for the P-selective sets and that prove them structurally simple also hold for SH. In particular, all sets in SH have small circuits, the NP sets in SH are in Low2 , the second level of the low hierarchy within NP, and SAT cannot be in SH unless P = NP. Finally, it is known that the P-selective sets are not closed under union or intersection. We provide an extended selectivity hierarchy that is based on SH and that is large enough to capture those closures of the P-selective sets, and yet, in contrast with the P-mc classes, is refined enough to distinguish them.</p>
      </abstract>
    </article-meta>
  </front>
</article>
