Master of Science in Computer Science
Department of Computer Science
School of Mathematics and Computer Science (SMCS)
Date of Submission
Dr. Shahid Hussain, Associate Professor and Chairperson, Department of Computer Science
Committee Member 1
Dr. Jibran Rashid, Examiner – I,
Committee Member 2
Dr. Imran Rauf, Examiner – II
Parameterized Complexity Theory aims to provide an expanded multivariate model of computational complexity. Similar to the classical theory, it contains many results on the structure of complexity classes. Most notably, we have the Weft Hierarchy of classes, which are believed to be situated in-between the parameterized version of P (known as FPT) and NP (known as para-NP). While the Weft Hierarchy is a structural refinement over the classical theory, many open problems remain in Parameterized Complexity Theory. Work needs to be done to refine our current understanding of the structural relationships between the parameterized classes and between parameterized and classical results. No up-to-date survey of literature has been published (since 2015) on this topic. We present a systematic way of searching for open problems in the field, using a deductive reasoning tool we have created for this purpose. Our tool includes visual ways of search and deduction. It is novel in the way it synthesizes the domain knowledge, and lets the researcher discover open problems.
Zafar, Muhammad Abdullah. "A Deduction Tool for finding Open Problems in Parameterized Complexity Theory." Unpublished graduate research project. Institute of Business Administration. 2022. https://ir.iba.edu.pk/research-projects-mscs/29
Available for download on Monday, June 15, 2026
The full text of this document is only accessible to authorized users.