9 found
Order:
  1.  6
    On the Unusual Effectiveness of Logic in Computer Science.Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi & Victor Vianu - 2001 - Bulletin of Symbolic Logic 7 (2):213-236.
  2.  18
    Number of Variables is Equivalent to Space.Neil Immerman, Jonathan F. Buss, A. David & Mix Barrington - forthcoming - Journal of Symbolic Logic.
  3.  3
    Review: Theodore Baker, John Gill, Robert Solovay, Relativizations of the $Mathscr{P} = ?Mathscr{N} Mathscr{P}$ Question; Charles H. Bennett, John Gill, Relative to a Random Oracle $A, P^a Neq NP^A Neq Co-NP^A$ with Probability 1. [REVIEW]Neil Immerman - 1986 - Journal of Symbolic Logic 51 (4):1061-1062.
  4.  5
    Number of Variables is Equivalent to Space.Neil Immerman, Jonathan F. Buss & David A. Mix Barrington - 2001 - Journal of Symbolic Logic 66 (3):1217-1230.
    We prove that the set of properties describable by a uniform sequence of first-order sentences using at most k + 1 distinct variables is exactly equal to the set of properties checkable by a Turing machine in DSPACE[n k ] (where n is the size of the universe). This set is also equal to the set of properties describable using an iterative definition for a finite set of relations of arity k. This is a refinement of the theorem PSPACE = (...)
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  5.  1
    Matiyasevich Yu. V.. Desyataya Problema Gil'berta. Russian Original of the Preceding. Matematicheskaya Logika I Osnovaniya Matematiki. VO “Nauka,” Moscow 1993, 223 Pp. Papadimitriou Christos H.. Computational Complexity. Addison-Wesley Publishing Company, Reading, Mass., Etc., 1994, Xv+ 523 Pp. [REVIEW]Neil Immerman - 1997 - Journal of Symbolic Logic 62 (2):677-678.
  6.  3
    Computability and Complexity.Neil Immerman - 2008 - Stanford Encyclopedia of Philosophy.
    Direct download  
     
    Export citation  
     
    My bibliography  
  7. Association for Symbolic Logic.Jon Barwise, Howard S. Becker, Chi Tat Chong, Herbert B. Enderton, Michael Hallett, C. Ward Henson, Harold Hodes, Neil Immerman, Phokion Kolaitis & Alistair Lachlan - 1998 - Bulletin of Symbolic Logic 4 (4):465-510.
  8. Baker Theodore, Gill John, and Solovay Robert. Relativizations of the =? Question. SIAM Journal on Computing, Vol. 4 , Pp. 431–442.Bennett Charles H. And Gill John. Relative to a Random Oracle A, PA ≠ NPA ≠ Co-NPA with Probability 1. SIAM Journal on Computing, Vol. 10 , Pp. 96–113. [REVIEW]Neil Immerman - 1986 - Journal of Symbolic Logic 51 (4):1061-1062.
  9. Review: Yu. V. Matiyasevich, Desyataya Problema Gil'berta; Christos H. Papadimitriou, Computational Complexity. [REVIEW]Neil Immerman - 1997 - Journal of Symbolic Logic 62 (2):677-678.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography