8 found
Order:
  1.  19
    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.  19
    Theodore Baker, John Gill, and Robert Solovay. Relativizations of the =? Question. SIAM Journal on Computing, Vol. 4 , Pp. 431–442. - Charles H. Bennett and John Gill. 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.
  3.  11
    Yu. V. Matiyasevich. Desyataya Problema Gil'berta. Russian Original of the Preceding. Matematicheskaya Logika I Osnovaniya Matematiki. VO “Nauka,” Moscow1993, 223 Pp. - Christos H. Papadimitriou. 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.
  4.  12
    Computability and Complexity.Neil Immerman - 2008 - Stanford Encyclopedia of Philosophy.
  5.  26
    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.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  6.  21
    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 (7 more)  
     
    Export citation  
     
    Bookmark  
  7.  7
    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  
     
    Bookmark  
  8. 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.