Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Descriptive Complexity

Sortuj według:

Ogranicz wyniki do:

Tree-width in Algebraic Complexity

Meer K.

Fundamenta Informaticae

2010

Vol. 98, nr 4

391-409

The paper surveys some of the author's work studying the algorithmic importance of the tree-width notion in algebraic frameworks. Two approaches are described. The first gives an algorithmicmeta-theoremfor certain logically characterized propertieswithin the Blum-Shub-Smale BSS model of computation over the reals. The second reports on recent joint work with P. Koiran relating Boolean complexity and Valiant’s approach to study families of polynomial systems over infinite fields and their complexity. We define particular families of polynomials via bounding the tree-width of suitably attached graphs and study the expressive power of the resulting families. The work described here is partially co-authoredwith and partially verymuch influenced by previous work of Janos A. Makowsky.

Program Schemes, Queues, the Recursive Spectrum and Zero-one Laws

Stewart I.A.

Fundamenta Informaticae

2009

Vol. 91, nr 2

411-435

We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted, so that the resulting class is denoted NPSQ+(1), is such that the class of problems accepted by these program schemes is exactly the class of recursively enumerable problems. The class of problems accepted by the program schemes of the class NPSQ(1) where only access to a queue, and not the additional numeric universe, is allowed is exactly the class of recursively enumerable problems that are closed under extensions. We define an infinite hierarchy of classes of program schemes for which NPSQ(1) is the first class and the union of the classes of which is the class NPSQ.We show that the class of problems accepted by the program schemes of NPSQ is the union of the classes of problems defined by the sentences of all vectorized Lindstr¨om logics formed using operators whose corresponding problems are recursively enumerable and closed under extensions, and, as a result, has a zero-one law. Moreover, we also show that this class of problems can be realized as the class of problems defined by the sentences of a particular vectorized Lindstr¨om logic. Finally, we show how our results can be applied to yield logical characterizations of complexity classes and provide logical analogues to a number of inequalities and hypotheses from computational complexity theory involving (non-deterministic) complexity classes ranging from NP through to ELEMENTARY.

Polynomial-Time Maximisation Classes: Syntactic Hierarchy

Bueno O., Manyem P.

Fundamenta Informaticae

2008

Vol. 84, nr 1

111-133

In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as P, NP, L and NL. However, research on the descriptive complexity of optimisation problems has been limited. In a previous paper [13], we characterised the optimisation versions of P via expressions in second order logic, using universal Horn formulae with successor relations. In this paper, we study the syntactic hierarchy within the class of polynomially bound maximisation problems. We extend the result in the previous paper by showing that the class of polynomially-bound NP (not just P) maximisation problems can be expressed in second-order logic using Horn formulae with successor relations. Finally, we provide an application - we show that the Bin Packing problem with online LIB constraints can be approximated to within a Q(logn) bound, by providing a syntactic characterisation for this problem.