Computer Science – Computational Complexity
Scientific paper
2006-06-12
Computer Science
Computational Complexity
17 pages; presented at the July 2005 ACiD workshop at Durham, England; Included both American and British commonwealth spellin
Scientific paper
In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as \textbf{P, NP, L and NL}. ~ However, research on the descriptive complexity of optimisation problems has been limited. Optimisation problems corresponding to the \textbf{NP} class have been characterised in terms of logic expressions by Papadimitriou and Yannakakis, Panconesi and Ranjan, Kolaitis and Thakur, Khanna et al, and by Zimand. Gr\"{a}del characterised the polynomial class \textbf{P} of decision problems. In this paper, we attempt to characterise the optimisation versions of \textbf{P} via expressions in second order logic, many of them using universal Horn formulae with successor relations. The polynomially bound versions of maximisation (maximization) and minimisation (minimization) problems are treated first, and then the maximisation problems in the "not necessarily polynomially bound" class.
No associations
LandOfFree
Syntactic Characterisations of Polynomial-Time Optimisation Classes (Syntactic Characterizations of Polynomial-Time Optimization Classes) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Syntactic Characterisations of Polynomial-Time Optimisation Classes (Syntactic Characterizations of Polynomial-Time Optimization Classes), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Syntactic Characterisations of Polynomial-Time Optimisation Classes (Syntactic Characterizations of Polynomial-Time Optimization Classes) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-647767