Back to search

University of Waterloo

An Attempt to Automate <i>NP</i>-Hardness Reductions via <i>SO</i>&#8707; Logic

Abstract

dc:description.abstract

We 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>&#8707;) 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>&#8707; 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>&#8707; sentences are equivalent is as hard as GRAPH ISOMORPHISM, and prove that determining whether an arbitrary <i>SO</i>&#8707; 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 × 5

Rights

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

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Nijjar, Paul. An Attempt to Automate <i>NP</i>-Hardness Reductions via <i>SO</i>&#8707; Logic. University of Waterloo, 2004. http://hdl.handle.net/10012/1162