Research Initiation:  Investigations into the Structure of  Intractable Sets
{'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}
This project is an investigation of the computational complexity of             intractable sets.  The object is to gain new insight into the rich              mathematical structure that individual classes such as NP, EXP and TIME         (2poly) appear to have, and to increase our understanding of the                structural relationship between these classes.  To these ends new               concepts and proof techniques will be employed.                                                                                                                 Sets that are difficult to compute on almost all arguments play an              important role in the structural analysis of complexity classes.                Separation results between various deterministic, nondeterministic, and         generalized Kolmogorov complexity classes can be witnessed by these             sets.  In cases where absolute results are elusive, relativization              results will be achieved.                                                                                                                                       Application of these results will be used to study the structure of             complete sets in NP and EXP.  A new nonconstructive reducibility that           relates the polynomial complexity of computable sets will be used to            investigate the structure of the classes NP and EXP.  New results and           insights into the fine structure of these classes have been obtained;           further research into these areas is proposed.
{'FirstName': 'John', 'LastName': 'Geske', 'PI_MID_INIT': 'G', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'John G Geske', 'EmailAddress': 'jgeske@kettering.edu', 'NSF_ID': '000391568', 'StartDate': '09/01/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Michigan State University', 'CityName': 'EAST LANSING', 'ZipCode': '488242600', 'PhoneNumber': '5173555040', 'StreetAddress': '426 AUDITORIUM RD RM 2', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'Michigan', 'StateCode': 'MI', 'CONGRESSDISTRICT': '07', 'CONGRESS_DISTRICT_ORG': 'MI07', 'ORG_UEI_NUM': 'R28EKN92ZTZ9', 'ORG_LGL_BUS_NAME': 'MICHIGAN STATE UNIVERSITY', 'ORG_PRNT_UEI_NUM': 'VJKZC4D1JN36'}
{'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': '8811996.xml'}