Order:
  1.  35
    Complexity of equivalence relations and preorders from computability theory.Egor Ianovski, Russell Miller, Keng Meng Ng & André Nies - 2014 - Journal of Symbolic Logic 79 (3):859-881.
    We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined byR≤S⇔ ∃f∀x, y[x R y↔fS f].Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a${\rm{\Pi }}_1^0$-complete equivalence relation, but no${\rm{\Pi }}_k^0$-complete fork≥ 2. We show that${\rm{\Sigma }}_k^0$preorders arising naturally in the above-mentioned areas are${\rm{\Sigma }}_k^0$-complete. This includes polynomial timem-reducibility on (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  2.  18
    Grammar Logics in Nested Sequent Calculus: Proof Theory and Decision Procedures.Alwen Tiu, Egor Ianovski & Rajeev Goré - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 516-537.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   4 citations  
  3.  16
    The complexity of decision problems about equilibria in two-player Boolean games.Egor Ianovski & Luke Ong - 2018 - Artificial Intelligence 261 (C):1-15.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark