8 found
Sort by:
  1. Neil Immerman, Jonathan F. Buss, A. David & Mix Barrington (forthcoming). Number of Variables is Equivalent to Space. Journal of Symbolic Logic.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. Neil Immerman, Computability and Complexity. Stanford Encyclopedia of Philosophy.
    Direct download  
     
    My bibliography  
     
    Export citation  
  3. Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi & Victor Vianu (2001). On the Unusual Effectiveness of Logic in Computer Science. Bulletin of Symbolic Logic 7 (2):213-236.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  4. Neil Immerman, Jonathan F. Buss & David A. Mix Barrington (2001). Number of Variables is Equivalent to Space. 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)  
     
    My bibliography  
     
    Export citation  
  5. 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). Association for Symbolic Logic. Bulletin of Symbolic Logic 4 (4).
     
    My bibliography  
     
    Export citation  
  6. Neil Immerman (1997). 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] Journal of Symbolic Logic 62 (2):677-678.
    Direct download  
     
    My bibliography  
     
    Export citation  
  7. Neil Immerman (1997). Review: Yu. V. Matiyasevich, Desyataya Problema Gil'berta; Christos H. Papadimitriou, Computational Complexity. [REVIEW] Journal of Symbolic Logic 62 (2):677-678.
    Translate to English
    | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  8. Neil Immerman (1986). 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] Journal of Symbolic Logic 51 (4):1061-1062.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation