Computabiliyt and computational complexity theory
Computability and computational complexity theory address two fundamental questions: what problems can computers solve, and how fast can they solve them?
It provides a rigorous framework for understanding the limits of efficient computation and helps distinguish between tractable and intractable problems. Our research focuses on characterizing complexity classes, exploring reductions and completeness, and studying the boundaries of algorithmic efficiency.
Research
Our core research topics include:
- Computability theory: Investigating which problems can be solved in principle and identifying the limits of algorithmic solvability/decidability
- Computational complexity theory: Classifying problems based on the resources (time, space, randomness, or parallelism) required to solve them
- Models of computation: Analyzing and comparing classical, probabilistic, and emerging frameworks, including quantum and other unconventional models, to understand how they influence algorithmic efficiency
- Reductions and completeness: Studying problem transformations and identifying representative hard problems across complexity classes to reveal the structure of computational challenges
- Algorithmic efficiency and optimization: Exploring the interplay between theoretical bounds and practical algorithm design for real-world applications.
These topics collectively address the fundamental question: “What can be (efficiently) automated?” By combining insights from computability, complexity, and computational models, our research defines which problems are tractable, which are inherently hard, and how different frameworks shape these boundaries. This understanding provides the theoretical foundation for advances in optimization, machine learning, quantum computing, and other computational technologies, while also addressing deeper philosophical and foundational questions about the nature and limits of computation.
People
- Dr Vladimir Gusev
- Dr Nikhil Mande
- Dr Othon Michail
- Dr Anish Mukherjee
- Professor Igor Potapov
- Dr William Rosenbaum
- Professor Rahul Savani
- Professor Paul Spirakis
- Dr Friedrich Slivovsky
- Dr Karteek Sreenivasaiah
- Dr Konstantinos Tsakalidis
- Dr Viktor Zamaraev
Opportunities
We welcome opportunities to engage with students, researchers, and industry partner:
- PhD opportunities: please contact us if you are interested in pursuing a PhD in computational complexity theory
- Consultancy and research collaborations: we welcome partnerships, consultancy, and knowledge exchange projects with academic, industry, and government partners.
Outputs and impact
- Collaboration with MIF on Crystal Structure Predictions (CSP) – The interdisciplinary collaboration culminated in two major research breakthroughs related to CSP. In 2022 we proved the hypothesis about CSP's computational intractability (NP-hardness) and showed even undecidability of the problem when the size of periodic blocks (unit cells) is unknown. In 2023 we presented the first method of finding the best crystal structure with a mathematical guarantee that avoids exhaustive search providing the first alternative to heuristic methods [Nature]. These outcomes have paved the way for further development of Algorithmic Crystal Structure Prediction approaches.
Contact us
Please discuss with relevant academic staff if you are interested in their research.