Master of Science in Computer Science


Department of Computer Science


School of Mathematics and Computer Science (SMCS)

Date of Submission

Summer 2022


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.

Document Type

Restricted Access

Submission Type


Available for download on Monday, June 15, 2026

The full text of this document is only accessible to authorized users.