• DocumentCode
    2454909
  • Title

    NP-sets are Co-NP-immune relative to a random oracle

  • Author

    Vereshchagin, Nikolai K.

  • Author_Institution
    Dept. of Math. Logic, Moscow State Univ., Russia
  • fYear
    1995
  • fDate
    4-6 Jan 1995
  • Firstpage
    40
  • Lastpage
    45
  • Abstract
    We prove that the class NP has Co-NP-immune sets relative to a random oracle. Moreover, we prove that, relative to a random oracle, there are L∈P and NP-set L1⊂L such that both L1 and L|L1 are infinite, L1 has no infinite Co-NP-subsets and L|L1 has no infinite NP-subsets. The second theorem implies both the first theorem and the theorem in Vereshchagin (1993) that Co-NP has NP-immune sets relative to a random oracle
  • Keywords
    computational complexity; probabilistic automata; Co-NP-immune; NP-sets; complexity theory; random oracle; Complexity theory; Logic;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Theory of Computing and Systems, 1995. Proceedings., Third Israel Symposium on the
  • Conference_Location
    Tel Aviv
  • Print_ISBN
    0-8186-6915-2
  • Type

    conf

  • DOI
    10.1109/ISTCS.1995.377048
  • Filename
    377048
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2454909