Global ETD Search

About
The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.

1	An Attempt to Automate <i>NP</i>-Hardness Reductions via <i>SO</i>∃ Logic Nijjar, Paul January 2004 (has links) 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>∃) 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. Computer Science descriptive complexity mathematical discovery second-order existential logic theorem proving
2	An Attempt to Automate <i>NP</i>-Hardness Reductions via <i>SO</i>∃ Logic Nijjar, Paul January 2004 (has links) 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>∃) 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. Computer Science descriptive complexity mathematical discovery second-order existential logic theorem proving

1

Page generated in 0.1991 seconds