Study of the complexity of sparse sets and of kolmogorov complexity
FP4 — Training and Mobility of Researchers
- Duration
- 1997-01-01 → 1997-09-30
- EU contribution
- —
- Participants
- 2
- Scheme
- RGI
Lines connect the coordinator with its partners. CORDIS does not always give exact coordinates for projects before 2014. These points are placed at city or country level.
Project objective
Research objectives and content I plan to investigate structural properties of complexity classes, and to further my research on the sparse hard set problem by collaborating with experts at CWI and the University of Amsterdam. Specific issues I would like to address are: - the existence of sparse hard sets for P under logspace Turing reductions - the existence of sparse hard sets for P under logspace randomized reductions - applications of techniques used for the sparse hard set problem for P to the analogous problem for NP Training content (objective, benefit and expected impact) I would like to get a thorough training in the basics of Kolmogorov complexity and applications of the incompressibility method to computational complexity theory.
Original text from CORDIS.
Participants
- STICHTING MATHEMATISCH CENTRUM · AMSTERDAMCoordinatorNetherlands
- Not availableCity levelBelgium
Links
Data: CORDIS, © European Union