Page 1 Next

Displaying 1 – 20 of 24

Showing per page

O složitosti

Pavel Pudlák (1988)

Pokroky matematiky, fyziky a astronomie

On Existentially First-Order Definable Languages and Their Relation to NP

Bernd Borchert, Dietrich Kuske, Frank Stephan (2010)

RAIRO - Theoretical Informatics and Applications

Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals  iff L is existentially but not quantifierfree definable in FO[<, min, max, +1, −1]. Furthermore, no such class lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.

On maximal QROBDD’s of boolean functions

Jean-Francis Michon, Jean-Baptiste Yunès, Pierre Valarcher (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).

On maximal QROBDD's of Boolean functions

Jean-Francis Michon, Jean-Baptiste Yunès, Pierre Valarcher (2010)

RAIRO - Theoretical Informatics and Applications

We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).

On the Average Case Complexity of Some P-complete Problems

Maria Serna, Fatos Xhafa (2010)

RAIRO - Theoretical Informatics and Applications

We show that some classical P-complete problems can be solved efficiently in average NC. The probabilistic model we consider is the sample space of input descriptions of the problem with the underlying distribution being the uniform one. We present parallel algorithms that use a polynomial number of processors and have expected time upper bounded by (e ln 4 + o(1))log n, asymptotically with high probability, where n is the instance size.

On the Complexity of the Hidden Weighted Bit Function for Various BDD Models

Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener (2010)

RAIRO - Theoretical Informatics and Applications

Ordered binary decision diagrams (OBDDs) and several more general BDD models have turned out to be representations of Boolean functions which are useful in applications like verification, timing analysis, test pattern generation or combinatorial optimization. The hidden weighted bit function (HWB) is of particular interest, since it seems to be the simplest function with exponential OBDD size. The complexity of this function with respect to different circuit models, formulas, and various...

On the computational complexity of (O,P)-partition problems

Jan Kratochvíl, Ingo Schiermeyer (1997)

Discussiones Mathematicae Graph Theory

We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.

On the expressive power of the shuffle operator matched with intersection by regular sets

Joanna Jȩdrzejowicz, Andrzej Szepietowski (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form L R , with a shuffle language L and a regular language R , contains non-semilinear languages and does not form a family of mildly context- sensitive languages.

On the expressive power of the shuffle operator matched with intersection by regular sets

Joanna Jędrzejowicz, Andrzej Szepietowski (2010)

RAIRO - Theoretical Informatics and Applications

We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form L R , with a shuffle language L and a regular language R, contains non-semilinear languages and does not form a family of mildly context- sensitive languages.

On the hierarchies of Δ20-real numbers

Xizhong Zheng (2007)

RAIRO - Theoretical Informatics and Applications

A real number x is called Δ20 if its binary expansion corresponds to a Δ20-set of natural numbers. Such reals are just the limits of computable sequences of rational numbers and hence also called computably approximable. Depending on how fast the sequences converge, Δ20-reals have different levels of effectiveness. This leads to various hierarchies of Δ20 reals. In this survey paper we summarize several recent developments related to such kind of hierarchies shown by the author and his collaborators. ...

On the parameterized complexity of approximate counting

J. Andrés Montoya (2011)

RAIRO - Theoretical Informatics and Applications

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class # W [ P ] , the parameterized analogue of # P . We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.

Currently displaying 1 – 20 of 24

Page 1 Next