Search results for "complex"
showing 10 items of 5889 documents
On the Complexity of Solving Subtraction Games
2018
We study algorithms for solving Subtraction games, which sometimes are referred to as one-heap Nim games. We describe a quantum algorithm which is applicable to any game on DAG, and show that its query compexity for solving an arbitrary Subtraction game of $n$ stones is $O(n^{3/2}\log n)$. The best known deterministic algorithms for solving such games are based on the dynamic programming approach. We show that this approach is asymptotically optimal and that classical query complexity for solving a Subtraction game is generally $\Theta(n^2)$. This paper perhaps is the first explicit "quantum" contribution to algorithmic game theory.
Some complexity and approximation results for coupled-tasks scheduling problem according to topology
2016
International audience; We consider the makespan minimization coupled-tasks problem in presence of compatibility constraints with a specified topology. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We study several problems in framework of classic complexity and approximation for which the compatibility graph is bipartite (star, chain,. . .). In such a context, we design some efficient polynomial-time approximation algorithms for an intractable scheduling problem according to some parameters.
Right-jumps and pattern avoiding permutations
2015
We study the iteration of the process "a particle jumps to the right" in permutations. We prove that the set of permutations obtained in this model after a given number of iterations from the identity is a class of pattern avoiding permutations. We characterize the elements of the basis of this class and we enumerate these "forbidden minimal patterns" by giving their bivariate exponential generating function: we achieve this via a catalytic variable, the number of left-to-right maxima. We show that this generating function is a D-finite function satisfying a nice differential equation of order~2. We give some congruence properties for the coefficients of this generating function, and we sho…
Multi-scale analysis of the European airspace using network community detection
2014
We show that the European airspace can be represented as a multi-scale traffic network whose nodes are airports, sectors, or navigation points and links are defined and weighted according to the traffic of flights between the nodes. By using a unique database of the air traffic in the European airspace, we investigate the architecture of these networks with a special emphasis on their community structure. We propose that unsupervised network community detection algorithms can be used to monitor the current use of the airspaces and improve it by guiding the design of new ones. Specifically, we compare the performance of three community detection algorithms, also by using a null model which t…
Properties of a Class of Toeplitz Words
2021
We study the properties of the uncountable set of Stewart words. These are Toeplitz words specified by infinite sequences of Toeplitz patterns of the form $\alpha\beta\gamma$, where $\alpha,\beta,\gamma$ is any permutation of the symbols 0,1,?. We determine the critical exponent of the Stewart words, prove that they avoid the pattern $xxyyxx$, find all factors that are palindromes, and determine their subword complexity. An interesting aspect of our work is that we use automata-theoretic methods and a decision procedure for automata to carry out the proofs.
Cyclic Complexity of Words
2014
We introduce and study a complexity function on words $c_x(n),$ called \emph{cyclic complexity}, which counts the number of conjugacy classes of factors of length $n$ of an infinite word $x.$ We extend the well-known Morse-Hedlund theorem to the setting of cyclic complexity by showing that a word is ultimately periodic if and only if it has bounded cyclic complexity. Unlike most complexity functions, cyclic complexity distinguishes between Sturmian words of different slopes. We prove that if $x$ is a Sturmian word and $y$ is a word having the same cyclic complexity of $x,$ then up to renaming letters, $x$ and $y$ have the same set of factors. In particular, $y$ is also Sturmian of slope equ…
A subquadratic algorithm for minimum palindromic factorization
2014
We give an $\mathcal{O}(n \log n)$-time, $\mathcal{O}(n)$-space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string $S [1..n]$, in $\mathcal{O}(n \log n)$ time our algorithm returns the minimum number of palindromes $S_1,\ldots, S_\ell$ such that $S = S_1 \cdots S_\ell$. We also show that the time complexity is $\mathcal{O}(n)$ on average and $\Omega(n\log n)$ in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.
Finite state verifiers with constant randomness
2014
We give a new characterization of $\mathsf{NL}$ as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. It turns out that allowing two-way interaction with the prover does not change the class of verifiable languages, and that no polynomially bounded amount of randomness is useful for constant-memory computers when used as language recognizers, or public-coin verifiers. A corollary of our main result is that the class of outcome problems corresponding to O(log n)-space …
Optimal one-shot quantum algorithm for EQUALITY and AND
2017
We study the computation complexity of Boolean functions in the quantum black box model. In this model our task is to compute a function $f:\{0,1\}\to\{0,1\}$ on an input $x\in\{0,1\}^n$ that can be accessed by querying the black box. Quantum algorithms are inherently probabilistic; we are interested in the lowest possible probability that the algorithm outputs incorrect answer (the error probability) for a fixed number of queries. We show that the lowest possible error probability for $AND_n$ and $EQUALITY_{n+1}$ is $1/2-n/(n^2+1)$.
The quantum query complexity of certification
2009
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.