Structural Computational Complexity
{'Code': '05010100', 'Directorate': {'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Dana S. Richards'}
The strategic goal of this research is to contribute to the                   development of a comprehensive theory of computational complexity.              Computational complexity is the study of the quantitative laws that             govern computation and it is part of the developing science base needed         to guide, harness and exploit the explosively growing computer                  technology.  The ultimate goal, which seems very hard to reach and              which motivates most of this research, is a complete understand what is         and is not feasibly computable.                                                   One of the main goals of complexity theory is to develop a                    classification of computational problems by the amount of computational         resources needed to solve them.  This classification leads to                   complexity classes consisting of all computations that can be solved            within a given resource bound.  This research project concentrates on           the study of various complexity classes, relations between these                classes and the internal structure of these classes.  Of particular             interest is understanding what makes problems hard to compute and to            develop techniques to verify the degree of hardness.  Also studied are          trade-offs between various computational resources in problem solving,          with particular attention to the relations and trade-offs between               sequential-time, parallel-time, nondeterministic-time and memory                requirements.
{'FirstName': 'Juris', 'LastName': 'Hartmanis', 'EmailAddress': None, 'StartDate': '04/01/1989', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Cornell University', 'CityName': 'Ithaca', 'ZipCode': '148502820', 'PhoneNumber': '6072555014', 'StreetAddress': '373 Pine Tree Road', 'CountryName': 'United States', 'StateName': 'New York', 'StateCode': 'NY'}
{'Code': '2860', 'Text': 'THEORY OF COMPUTING'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8823053.xml'}