Expressibility and Computational Complexity
{'Code': '05010100', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Bruce H. Barnes', 'PO_EMAI': None, 'PO_PHON': None}
Computational complexity is a modern discipline which analyzes the              inherent difficulty of a given task.  A great deal of progress has been         made in classifying the time and space requirements of certain                  combinatorial problems.  The complexity classes logarithmic space,              nondeterministic logarithmic space, polynomial time, and                        nondeterministic polynomial time have been studied extensively.  Still          little is known about the comparative strengths of different resources          - it is yet to be proved that the above classes are not all identical.          Professor Immerman has studied these classes from a mathematical                viewpoint.  He has examined the inherent difficulties of expressing             conditions and shown that a robust alternative view of complexity               ensues.  This research continues work on complexity theory,                     concentrating on three specific areas: (1)  the power of the transitive         closure operator, (2) an investigation of uniformity, and (3) an                investigation of the effects of altering the number of distinct                 variables.
{'FirstName': 'Neil', 'LastName': 'Immerman', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Neil Immerman', 'EmailAddress': 'immerman@cs.umass.edu', 'NSF_ID': '000178321', 'StartDate': '05/01/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Yale University', 'CityName': 'NEW HAVEN', 'ZipCode': '065113572', 'PhoneNumber': '2037854689', 'StreetAddress': '150 MUNSON ST', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'Connecticut', 'StateCode': 'CT', 'CONGRESSDISTRICT': '03', 'CONGRESS_DISTRICT_ORG': 'CT03', 'ORG_UEI_NUM': 'FL6GV84CKN57', 'ORG_LGL_BUS_NAME': 'YALE UNIV', 'ORG_PRNT_UEI_NUM': 'FL6GV84CKN57'}
{'Name': None, 'CityName': None, 'StateCode': None, 'ZipCode': None, 'StreetAddress': None, 'CountryCode': None, 'CountryName': None, 'StateName': None, 'CountryFlag': None, 'CONGRESSDISTRICT': None, 'CONGRESS_DISTRICT_PERF': '""'}
{'Code': '2860', 'Text': 'THEORY OF COMPUTING'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8806308.xml'}