A descriptive approach to the class NP

مرکز و کتابخانه مطالعات اسلامی به زبان های اروپایی

منو

" A descriptive approach to the class NP "
J. A. Medina-Peralta N. Immerman

Document Type	:	Latin Dissertation
Language of Document	:	English
Record Number	:	1113256
Doc. No	:	TLpq304376015
Main Entry	:	J. A. Medina-Peralta
	:	N. Immerman
Title & Author	:	A descriptive approach to the class NP\ J. A. Medina-PeraltaN. Immerman
College	:	University of Massachusetts Amherst
Date	:	1997
student score	:	1997
Degree	:	Ph.D.
Page No	:	107
Abstract	:	Descriptive complexity is the study of the expressive power of logical languages. There exists a close relationship between the expressive power of a logical language and the computational complexity of the properties captured by such a language. R. Fagin proved that every sentence in second-order existential logic expresses a problem that can be decided by a non-deterministic polynomial time Turing machine: SOusd\existsusd = NP (9). With this fact as our starting point, we study the sentences that express properties that are complete for the class NP via first-order projections (fops). This type of reductions arises naturally in descriptive complexity, and it is known that all problems complete for NP via fops are FO-isomorphic (1). Our study of SOusd\existsusd sentences includes a normal form for sentences that describe NP-complete properties, the development of syntactic tools for proving problems NP-complete via fops, the definition of syntactic families of problems that have a similar syntactic structure, the study of the approximability of the problems in the syntactic families that we define, and a descriptive version of the PCP theorem. This dissertation is organized in seven chapters. In Chapter 1, we present an overview of our research area and results. In Chapter 2, we review the concepts and definitions of descriptive complexity. In Chapter 3 we describe a normal form for SOusd\existsusd sentences that define a NP-complete problems via fops. In Chapter 4 we present syntactic tools to prove problems NP-complete via fops and use them to prove that a large number of the known NP-complete problems remain complete via fops. Among these tools, we define families of problems with similar syntactic structure. In Chapter 5, we study the approximation properties of some of the families defined in chapter 4. In Chapter 6, we prove a descriptive version of the PCP theorem. This descriptive version implies both the PCP theorem in its computational version and Fagin's theorem. We close this work with Chapter 7 presenting our conclusions and suggestions for future research motivated by this dissertation.
Subject	:	Applied sciences
	:	complexity
	:	Computer science
	:	Fagin's theorem
	:	PCP theorem