"Tetravex is a widely played one person computer game in which you are given $n^2$ unit tiles, each edge of which is labelled with a number. The objective is to place each tile within a $n$ by $n$ square such that all neighbouring edges are labelled with an identical number. Unfortunately, playing Tetravex is computationally hard. More precisely, we prove that deciding if there is a tiling of the Tetravex board is NP-complete. Deciding where to place the tiles is therefore NP-hard. This may help to explain why Tetravex is a good puzzle. This result compliments a number of similar results for one person games involving tiling. For example, NP-completeness results have been shown for: the offline version of Tetris, KPlumber (which involves rotating tiles containing drawings of pipes to make a connected network), and shortest sliding puzzle problems. It raises a number of open questions. For example, is the infinite version Turing-complete? How do we generate Tetravex problems which are truly puzzling as random NP-complete problems are often surprising easy to solve? Can we observe phase transition behaviour? What about the complexity of the problem when it is guaranteed to have an unique solution? How do we generate puzzles with unique solutions?"

"Determining whether an unordered collection of overlapping substrings (called shingles) can be uniquely decoded into a consistent string is a problem that lies within the foundation of a broad assortment of disciplines ranging from networking and information theory through cryptography and even genetic engineering and linguistics. We present three perspectives on this problem: a graph theoretic framework due to Pevzner, an automata theoretic approach from our previous work, and a new insight that yields a time-optimal streaming algorithm for determining whether a string of $n$ characters over the alphabet $Sigma$ can be uniquely decoded from its two-character shingles. Our algorithm achieves an overall time complexity $Theta(n)$ and space complexity $O(|Sigma|)$. As an application, we demonstrate how this algorithm can be extended to larger shingles for efficient string reconciliation."

"This paper presents a study on two data structures that have been used to model several problems in computer science: and/or graphs and x-y graphs. An and/or graph is an acyclic digraph containing a source, such that every vertex v has a label f(v) in {and,or} and edges represent dependency relations between vertices: a vertex labeled and depends on all of its out-neighbors, while a vertex labeled or depends on only one of its out-neighbors. X-y graphs are defined as a natural generalization of and/or graphs: every vertex vi of an x-y graph has a label xi-yi to mean that vi depends on xi of its yi out-neighbors. We analyze the complexity of the optimization problems Min-and/or and Min-x-y, which consist of finding solution subgraphs of optimal weight for and/or and x-y graphs, respectively. Motivated by the large applicability as well as the hardness of Min-and/or and Min-x-y, we study new complexity aspects of such problems, both from a classical and a parameterized point of view. …"

"In this paper, first we give a sequential linear-time algorithm for the longest path problem in meshes. This algorithm can be considered as an improvement of [13]. Then based on this sequential algorithm, we present a constant-time parallel algorithm for the problem which can be run on every parallel machine."

So, things can be arbitrarily complex. But here’s a more interesting question: how complex can we prove something to be? The answer is one of the most astounding facts I know. It’s called Chaitin’s incompleteness theorem. It says, very roughly:

There’s a number L such that we can’t prove the Kolmogorov complexity of any specific string of bits is bigger than L.

Make sure you understand this. For any number,
we can prove there are infinitely many bit strings with Kolmogorov complexity bigger than that. But we can’t point to any particular bit string and prove its Kolmogorov complexity is bigger than L!

"Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. This book gives a lucid and playful explanation of the field, starting with P and NP-completeness. The authors explain why the P vs. NP problem is so fundamental, and why it is so hard to resolve. They then lead the reader through the complexity of mazes and games; optimization in theory and practice; randomized algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing. At every turn, they use a minimum of formalism, providing explanations that are both deep and accessible. The book is intended for graduates and undergraduates, scientists from other areas who have long wanted to understand this subject, and experts who want to fall in love with this field all over again."

"The main source of this speed penalty is an insistence that the result of a matrix multiply should follow R’s rules for handling infinity, NaN (not-a-number), and NA.  These rules correspond to what happens with ordinary arithmetic operations on modern computers, which follow a standard for floating-point arithmetic in which, for example, 0/0 is NaN.  You might therefore think that nothing special is needed to arrange for matrix multiplies to produce NaNs as required.  However, R does matrix multiplications using the BLAS library, which comes in many versions, some of which may try to speed things up by avoiding “unnecessary” operations such as multiplication by zero — assuming that that will always result in zero.  However, zero times NaN or infinity is supposed to be NaN, not zero."

The situation is different with ITTM’s. As a matter of fact, any non-halting ITTM will eventually repeat configurations once and, hence, forever. This is simply a matter of countability. The number of tape/state configurations is 2ℵ0 (“2 to the Aleph Naught”), an uncountable cardinal. But eventually, a non-halting machine will run for 22ℵ0 steps, an even larger cardinal. By the transfinite pigeonhole principle, the tape must repeat configurations by then. So why doesn’t this allow the naive solution to the Halting Problem to work for ITTMs? The answer is, checking for repeat configurations is far more difficult when configurations can be infinite. Even just checking whether two particular tape configurations are identical (nevermind the non-trivial question of how infinitely many infinite previous steps should be stored in memory), could require the tape-reader to traverse the entire infinite tape.

Humans need to solve computationally intractable problems such as visual search, categorization, and simultaneous learning and acting, yet an increasing body of evidence suggests that their solutions to instantiations of these problems are near optimal. Computational complexity advances an explanation to this apparent paradox: only a small portion of instances of such problems are actually hard, and successful heuristics exploit structural properties of the typical instance to selectively improve parts that are likely to be sub-optimal. We hypothesize that these two ideas largely account for the good performance of humans on computationally hard problems. We tested part of this hypothesis by studying the solutions of 28 participants to 28 instances of the Euclidean Traveling Salesman Problem ... We found a significant improvement between the first and last trials and that solutions are significantly different from random tours that follow the convex hull and do not have self-crossings.

The first part of a six part (!) dialogue (tri-alogue?) between three emoticons, about computational complexity.

"We give a space-optimal algorithm with update time O(log^2(1/eps)loglog(1/eps)) for (1+eps)-approximating the pth frequency moment, 0 < p < 2, of a length-n vector updated in a data stream. This provides a nearly exponential improvement in the update time complexity over the previous space-optimal algorithm of [Kane-Nelson-Woodruff, SODA 2010], which had update time Omega(1/eps^2)."

"We provide several basic results. We obtain an efficient algorithm for determining the heapa- bility of a sequence, and also prove that the question of whether a sequence can be arranged in a complete binary heap is NP-hard. Regarding subsequences we show that, with high probability, the longest heapable subsequence of a random permutation of n numbers has length (1 − o(1))n, and a subsequence of length (1 − o(1))n can in fact be found online with high probability. We similarly show that for a random permutation a subsequence that yields a complete heap of size αn for a constant α can be found with high probability. Our work highlights the interesting structure underlying this class of subsequence problems, and we leave many further interesting variations open for future work."

"The results imply that several families of constraint satisfaction problems exhibit a complexity dichotomy: the problems are in P or NP-hard, depending on the choice of the allowed relations."

Merely by existing, all physical systems register information. And by evolving dynamically in time, they transform and process that information. The laws of physics determine the amount of information that a physical system can register (number of bits) and the number of elementary logic operations that a system can perform (number of ops). The universe is a physical system. This paper quantifies the amount of information that the universe can register and the number of elementary operations that it can have performed over its history. The universe can have performed no more than $10^{120}$ ops on $10^{90}$ bits.

"We study several problems related to finding reset words in deterministic finite automata. In particular, we establish that the problem of deciding whether a shortest reset word has length k is complete for the complexity class DP. This result answers a question posed by Volkov. For the search problems of finding a shortest reset word and the length of a shortest reset word, we establish membership in the complexity classes FP^NP and FP^NP[log], respectively. Moreover, we show that both these problems are hard for FP^NP[log]. Finally, we observe that computing a reset word of a given length is FNP-complete."

"The Lin-Kernighan heuristic is known to be one of the most successful heuristics for the Traveling Salesman Problem (TSP). It has also proven its efficiency in application to some other problems. In this paper we discuss possible adaptations of TSP heuristics for the Generalized Traveling Salesman Problem (GTSP) and focus on the case of the Lin-Kernighan algorithm. At first, we provide an easy-to-understand description of the original Lin-Kernighan heuristic. Then we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the Lin-Kernighan adaptation and some other GTSP heuristics. It appears that our adaptation of the Lin-Kernighan algorithm for the GTSP reproduces the success of the original heuristic. Different variations of our adaptation outperform all other heuristics in a wide range of trade-offs between solution quality and running time, making Lin-Kernighan the state-of-the-art GTSP local search."

"The main goal of the paper is to introduce methods which compute B\'ezier curves faster than Casteljau's method does. These methods are based on the spectral factorization of a $n\times n$ Bernstein matrix, $B^e_n(s)= P_nG_n(s)P_n^{-1}$, where $P_n$ is the $n\times n$ lower triangular Pascal matrix. So we first calculate the exact optimum positive value $t$ in order to transform $P_n$ in a scaled Toeplitz matrix, which is a problem that was partially solved by X. Wang and J. Zhou (2006). Then fast Pascal matrix-vector multiplications and strategies of polynomial evaluation are put together to compute B\'ezier curves. Nevertheless, when $n$ increases, more precise Pascal matrix-vector multiplications allied to affine transformations of the vectors of coordinates of the control points of the curve are then necessary to stabilize all the computation."