2017/07/28 by Pin, Edwin, Borges, Nerio
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.1707.09327
In the nineties Immerman and Medina initiated the search for syn- tactic tools to prove NP-completeness. In their work, amongst several results, they conjecture that the NP-completeness of a problem defined by the conjunction of a sentence in Existential Second Order Logic with a First Order sentence, necessarily imply the NP-completeness of the problem defined by the Existential Second Order sentence alone. This is interesting because if true it would justify the restriction heuristic pro- posed in Garey and Johnson in his classical book on NP completeness, which roughly says that in some cases one can prove NP- complete a problem A by proving NP-complete a problem B contained in A. Borges and Bonet extend some results from Immerman and Medina and they also prove for a host of complexity classes that the Immerman- Medina conjecture is true when the First Order sentence in the conjunc- tion is universal. Our work extends that result to the Second Level of the Polynomial-Time Hierarchy.