University of Waterloo
An Attempt to Automate <i>NP</i>-Hardness Reductions via <i>SO</i>∃ Logic
Abstract
dc:description.abstractWe explore the possibility of automating <i>NP</i>-hardness reductions. We motivate the problem from an artificial intelligence perspective, then propose the use of second-order existential (<i>SO</i>∃) logic as representation language for decision problems. Building upon the theoretical framework of J. Antonio Medina, we explore the possibility of implementing seven syntactic operators. Each operator transforms <i>SO</i>∃ sentences in a way that preserves <i>NP</i>-completeness. We subsequently propose a program which implements these operators. We discuss a number of theoretical and practical barriers to this task. We prove that determining whether two <i>SO</i>∃ sentences are equivalent is as hard as GRAPH ISOMORPHISM, and prove that determining whether an arbitrary <i>SO</i>∃ sentence represents an <i>NP</i>-complete problem is undecidable.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2004
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Nijjar, Paul
Subjects
dc:subject × 5Rights
dc:rights- Statement dc:rights
-
- Copyright: 2004, Nijjar, Paul. All rights reserved.
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/1162