U.S. - Germany Cooperative Research: Parallel Access to NP: Complexity and Applicability

点击翻译按钮获取中文摘要

9815095HemaspaandraThis award supports the PI, Edith Hemaspaandra, co-PI Lane Hemaspaandra, and a graduate student from the Rochester Institute of Technology in collaboration with Klaus Wagner of the Department of Information Technology at the University of Wuerzburg, Germany. The goal of the research is to explore the complexity and applicability of the class of problems solvable via parallel access to NP. Such problems are those that could be solved given an unlimited number of parallel processors working at the same time on the same problem. This research will establish new relationships between several familiar real-world problems and certain classes of solutions that have previously been considered technical and obscure. The German collaborator is well known for his work in this area and is responsible for some of the earliest significant work on the class of problems under study. The cooperation also includes participation of younger researchers who should benefit greatly from the experience.