Constructing NP-intermediate problems by blowing holes with parameters of various properties ?
We provide a framework to obtain NP-intermediate problems based on diagonalization. We categorize different types of parameters that are usable in our framework. We construct NP-intermediate constraint satisfaction problems. We resolve the open question whether Boolean abduction admits intermediate problems.
np-intermediate problems constraint satisfaction problems computational complexity abduction problems