FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
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: