• DocumentCode
    1992808
  • Title

    Polynomial time truth-table reductions to p-selective sets

  • Author

    Agrawal, M. ; Arvind, V.

  • Author_Institution
    Sch. of Math., SPIC Science Foundation, Madras, India
  • fYear
    1994
  • fDate
    28 Jun- 1 Jul 1994
  • Firstpage
    24
  • Lastpage
    30
  • Abstract
    We make an elaborate analysis of the intervals defined by the ordered list of queries to the p-selective set. It turns out that the properties we derive are strong enough to get a collapse to P for several complexity classes, assuming that they are quasi-linear truth-table reducible (or in some cases o(logn)-tt reducible) to a p-selective set. More specifically, for any class 𝒦∈{NP, PP, C=P, ⊕P) we show that if 𝒦 is quasi-linear truth-table reducible to a p-selective set then 𝒦=P. For other ModkP classes (k>2) we show that if ModkP is o(log n)-truth-table reducible to a p-selective set then ModkP=P
  • Keywords
    Boolean algebra; computational complexity; set theory; complexity classes; ordered list; p-selective sets; polynomial time truth-table reductions; quasi-linear truth-table reducible; Circuits; Complexity theory; Computer science; Mathematics; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
  • Conference_Location
    Amsterdam
  • Print_ISBN
    0-8186-5670-0
  • Type

    conf

  • DOI
    10.1109/SCT.1994.315821
  • Filename
    315821