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 First-order reduction Computationalcomplexity
CLC: O221.1
Type: Master's thesis
Year: 2013
Downloads: 0
Quote: 0
Read: Download Dissertation


In finite model theory, descriptive complexity theory as the link which con-nects 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 poly-nomial hierarchy, is precisely the class of languages expressible by statements of second-order 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 mathe-matical logic.While not all problems can be captured by a corresponding logic, these exam-ples which cannot be captured by logic are all important and oriented. In computa-tional 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 in-expressibility 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 NP-complete class plays one of the most useful roles in classifying the complexity of compu-tational problems. This is not only because any problem in NP can be reduced to an NP-complete problem, but also for that if any NP-complete problem can be solved by polynomial-time algorithm, then all NP problems will be solvable in polynomial-time. Although it is widely thought that NP-complete problems do not have polynomial-time algorithms, so far there is no proof for the conjecture. In this case, identifying the class of NP-Complete 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

  1. On Measurement and Computation,O413
  2. The Research of Fetal Ecg Signal Extraction Method and Application,TN911.7
  3. Study on Rate Control and Parallel Process for H.264/AVC Video Coding,TN919.81
  4. The Research on the Models of Non-classical Computation and Their Computational Complexity,TP301.6
  5. Design and Implementation of H.264Algorithm Based on SIMD DSP,TN919.81
  6. Research on Scheduling Algorithms and Performance of Crossbar Switch Fabric with Single Buffer at Crosspoint,TP393.02
  7. Design and implementation of Non-binary decoder of LDPC codes,TN911.22
  8. Enhanced Ordinal Optimization: A Theoretical Study and Applications,TP391.9
  9. The Study on Several Algorithms for Semidefinite Programming,O221.2
  10. Two numerical solution methods for semidefinite programming,O221.2
  11. Preparations for the Conference and medium-sized multi-objective programming model problem Construction and Analysis,O221.6
  12. Error Analysis in Stochastic Programming,O221.5
  13. Two Methods Based on Filter for Solving Nonlinear Programming Problems,O221.2
  14. Rural Postman Problem varying network and ant colony algorithm cutting plane,O221.4
  15. A Filter Line-search Interior Point Method for Nonlinear Constrained Optimization Problem,O221.2
  16. The Natures of Strong Quasiconcave Function and Its Apply in Utility Function,O221.6
  17. Optimality Conditions and Duality for Non-smooth Multi-objective Programming with Generalized B-invariant Functions,O221.6
  18. Study of the Algorithm for Nonlinear Bilevel Programming,O221.2
  19. Weak Quasi Combined Homotopy algorithm for non - convex optimization under normal cone condition,O221.2
  20. DC planning global optimization algorithm,O221
  21. 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