Completeness in the Second Level of the Polynomial Time Hierarchy through Syntactic Properties
Author: Edwin Pin
Paper Information
Title: | Completeness in the Second Level of the Polynomial Time Hierarchy through Syntactic Properties |
Authors: | Edwin Pin |
Proceedings: | LCC Contributed Talks |
Editors: | Erich Grädel and Jan Hoffmann |
Keywords: | computational complexity, descriptive complexity, graph theory |
Abstract: | ABSTRACT. In the mid-90's Neil Immerman and José Medina initiated the search for syntactic tools to prove NP-completeness. They conjectured that if a problem defined by the conjunction of an Existential Second Order sentence and a First Order Formula is NP-complete then the Existential Second Order formula denes an NP-complete problem. This property was called superfluity of First Order Logic with respect to NP. Few years later it was proved by Nerio Borges and Blai Bonet that superfluity is true for the universal fragment of First Order Logic and with respect not only to NP but for a major rank of complexity classes. Our work extends that result to the Second Level of the Polynomial-Time Hierarchy |
Pages: | 6 |
Talk: | Jul 13 12:15 (Session 86F: LCC: Contributed Talks) |
Paper: |