Dissertation > Excellent graduate degree dissertation topics show
Some Results between Descriptive Complexity and Computational Complexity
Author: BaiShuLiang
Tutor: Prabhu Manyem
School: Shanghai University
Course: Operational Research and Cybernetics
Keywords: Descriptive complexity Firstorder reduction Computationalcomplexity
CLC: O221.1
Type: Master's thesis
Year: 2013
Downloads: 0
Quote: 0
Read: Download Dissertation
Abstract
In finite model theory, descriptive complexity theory as the link which connects computational complexity and logics of finite structures, through providing new proof methods and additional evidences makes the complexity classes looks "natural" but not tied to the specific abstract machines used to define them. As to some main complexity class, descriptive complexity uses logics to define them in a semantical way. For example, PH as a union of complexity class in the polynomial hierarchy, is precisely the class of languages expressible by statements of secondorder logic.As its development progressed, a group of computer science theorists have proved that many diverse logics can capture different complexity classes. We call that these logics are equal to their corresponding complexity classes. Consequently, we can study some properties of computational complexity with the help of mathematical logic.While not all problems can be captured by a corresponding logic, these examples which cannot be captured by logic are all important and oriented. In computational complexity theorem, the very famous problem is P vs NP, and the results of inexpressibility of logic are possible to separate the complexity class. Thus, the inexpressibility of logics has been considered as a core topic. In this thesis, we expand the cope of problems involving inexpressibility of logics:In descriptive complexity, we know that existential second order (ESO) logic with a first order part that is universal Horn, as well as logics such as LFP+C IFP+C and C∞ωω can capture the class P when the structures are ordered.In Chapter2, we show that Linear Programming cannot be expressed in these logics at the structure level, at the same time, we extend the similar result to quadratic programming.In Chapter3, We also present the limits of expressibility of certain properties in logics L∞ωω, LFP, and PFP, by using Pebble Games, one of methodologies of mathematical logic. Another key focus of this thesis is given, in computer science, the NPcomplete class plays one of the most useful roles in classifying the complexity of computational problems. This is not only because any problem in NP can be reduced to an NPcomplete problem, but also for that if any NPcomplete problem can be solved by polynomialtime algorithm, then all NP problems will be solvable in polynomialtime. Although it is widely thought that NPcomplete problems do not have polynomialtime algorithms, so far there is no proof for the conjecture. In this case, identifying the class of NPComplete is very important.In Chapter4, we consider the computational problems from the descriptive complexity point of view, and show how to prove an NP problem is complete by logical reduction.In addition,we also show another role of logical reduction when it is operated between P problems, we found that the logical sentences of LFP+C, IFP+C and C∞ωω are insufficient to express P problem, this part has been shown in Chapter2.

Related Dissertations
 On Measurement and Computation,O413
 The Research of Fetal Ecg Signal Extraction Method and Application,TN911.7
 Study on Rate Control and Parallel Process for H.264/AVC Video Coding,TN919.81
 The Research on the Models of Nonclassical Computation and Their Computational Complexity,TP301.6
 Design and Implementation of H.264Algorithm Based on SIMD DSP,TN919.81
 Research on Scheduling Algorithms and Performance of Crossbar Switch Fabric with Single Buffer at Crosspoint,TP393.02
 Design and implementation of Nonbinary decoder of LDPC codes,TN911.22
 Enhanced Ordinal Optimization: A Theoretical Study and Applications,TP391.9
 The Study on Several Algorithms for Semidefinite Programming,O221.2
 Two numerical solution methods for semidefinite programming,O221.2
 Preparations for the Conference and mediumsized multiobjective programming model problem Construction and Analysis,O221.6
 Error Analysis in Stochastic Programming,O221.5
 Two Methods Based on Filter for Solving Nonlinear Programming Problems,O221.2
 Rural Postman Problem varying network and ant colony algorithm cutting plane,O221.4
 A Filter Linesearch Interior Point Method for Nonlinear Constrained Optimization Problem,O221.2
 The Natures of Strong Quasiconcave Function and Its Apply in Utility Function,O221.6
 Optimality Conditions and Duality for Nonsmooth Multiobjective Programming with Generalized Binvariant Functions,O221.6
 Study of the Algorithm for Nonlinear Bilevel Programming,O221.2
 Weak Quasi Combined Homotopy algorithm for non  convex optimization under normal cone condition,O221.2
 DC planning global optimization algorithm,O221
 Trust Region Method of New Conic Model for Nonlinearly Equality Constrained Optimization,O221.2
CLC: > Mathematical sciences and chemical > Mathematics > Operations Research > Planning Theory ( mathematical programming) > Linear programming
© 2012 www.DissertationTopic.Net Mobile
