We survey the current state of research on the knapsack problem in online and semi-online environments. In particular, we summarize what is known about models where different assumptions commonly made in online computation are relaxed: namely that online algorithms do not know the complete instances they are processing; have to make decisions that are irrevocable; and deal with an input chosen by a malicious adversary.

Abstract We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of n items with a size and a value each, and an algorithm has to decide whether or not and how often to pack each item into a knapsack of bounded capacity. The items are given online and the total size of the packed items must not exceed the knapsack’s capacity, while the objective is to maximize the total value of the packed items. While each item can only be packed once in the classical knapsack problem (also called the 0-1 knapsack problem), the unbounded version allows for items to be packed multiple times. We show that the simple unbounded knapsack problem, where the size of each item is equal to its value, allows for a competitive ratio of 2. We also analyze randomized algorithms and show that, in contrast to the 0-1 knapsack problem, one uniformly random bit cannot improve an algorithm’s performance. More randomness lowers the competitive ratio to less than 1 . 736 , but it can never be below 1 . 693 . In the advice complexity setting, we measure how many bits of information (so-called advice bits) the algorithm has to know to achieve some desired solution quality. For the simple unbounded knapsack problem, one advice bit lowers the competitive ratio to $$\varvec{3/2}$$ 3 / 2 . While this cannot be improved with fewer than $$\varvec{\log }_{\varvec{2}} \varvec{n} $$ log 2 n advice bits for instances of length n , a competitive ratio of $$\varvec{1}\varvec{+}\varvec{\varepsilon }$$ 1 + ε can be achieved with $$\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$$ O ( ε - 1 · log ( n ε - 1 ) ) advice bits for any $$\varvec{\varepsilon }\varvec{>}\varvec{0}$$ ε > 0 . We further show that no amount of advice bounded by a function $$\varvec{f(n)}$$ f ( n ) allows an algorithm to be optimal. We also study the online general unbounded knapsack problem and show that it does not allow for any bounded competitive ratio for both deterministic and randomized algorithms, as well as for algorithms using fewer than $$\varvec{\log }_{\varvec{2}} \varvec{n}$$ log 2 n advice bits. We also provide a surprisingly simple algorithm that uses $$\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$$

We call any consistent and sufficiently powerful formal theory that enables to algorithmically verify whether a text is a proof algorithmically verifiable mathematics (av-mathematics). We study the fundamental question whether nondeterminism is more powerful than determinism for polynomial time computations in the framework of av-mathematics. Our goal is to show strong indications that nondeterminism is more powerful than determinism for polynomial time computations. To do that, we do not consider decision problems only, but also compression algorithms. We show that at least one of the following three claims must be true: non-determinism is more powerful than determinism for polynomial-time compression for each polynomial-time compression algorithm there exists another one of the same asymptotic time complexity that compresses infinitely many strings logarithmically stronger Another surprising consequence of P = NP would be that time-bounded Kolmogorov complexity for any polynomial bound can be computed by deterministic algorithms in polynomial time.

In the Online Simple Knapsack Problem we are given a knapsack of unit size 1. Items of size smaller or equal to 1 are presented in an iterative fashion and an algorithm has to decide whether to permanently reject or include each item into the knapsack without any knowledge about the rest of the instance. The goal is then to pack the knapsack as full as possible. In this work, we introduce a third option additional to those of packing and rejecting an item, namely that of reserving an item for the cost of a fixed fraction α of its size. An algorithm may pay this fraction in order to postpone its decision on whether to include or reject the item until after the last item of the instance was presented. While the classical Online Simple Knapsack Problem does not admit any constantly bounded competitive ratio in the deterministic setting, we find that adding the possibility of reservation makes the problem constantly competitive, with varying competitive ratios depending on the value of α. We give upper and lower bounds for the whole range of reservation costs, with tight bounds for costs up to 1/6 - an area that is strictly 2-competitive - , for costs between √2-1 and 1 - an area that is strictly (2+α)-competitive up to ϕ -1, and strictly 1/(1-α)-competitive above ϕ-1, where ϕ is the golden ratio. With our analysis, we find a counterintuitive characteristic of the problem: Intuitively, one would expect that the possibility of rejecting items becomes more and more helpful for an online algorithm with growing reservation costs. However, for higher reservation costs above √2-1, an algorithm that is unable to reject any items tightly matches the lower bound and is thus the best possible. On the other hand, for any positive reservation cost smaller than 1/6, any algorithm that is unable to reject any items performs considerably worse than one that is able to reject.

A dominating set S of a graph is a set of vertices such that each vertex is in S or has a neighbor in S. The goal of the dominating set problem is to find such a set of minimum cardinality. In the online setting, the graph is revealed vertex by vertex, together with edges to all previously revealed vertices. Advice complexity is a framework to measure the amount of information an online algorithm is lacking. Here, an online algorithm reads advice bits from an infinite binary tape prepared beforehand by an all-knowing oracle. The advice complexity is the total number of advice bits read during the computation. Besides giving some insight into what makes an online problem hard, advice complexity can also be used as a means for proving lower bounds on the competitive ratio achievable by randomized online algorithms. We analyze the advice complexity of the online dominating set problem. For general graphs, we show tight upper and lower bounds for optimality. Then, we use a result for c-competitiveness to prove that no randomized online algorithm can be better than n1−ε-competitive, for any ε>0. Finally, we analyze the advice complexity of various graph classes for optimality.

It is well known that the set of powers of any given order, for example squares, in a regular language need not be regular. Nevertheless, finite automata can identify them via their roots. More precisely, we recall that, given a regular language L, the set of square roots of L is regular. The same holds true for the nth roots for any n and for the set of all nontrivial roots; we give a concrete construction for all of them. Using the above result, we obtain decision algorithms for many natural problems on powers. For example, it is decidable, given two regular languages, whether they contain the same number of squares at each length. Finally, we give an exponential lower bound on the size of automata identifying powers in regular languages. Moreover, we highlight interesting behavior differences between taking fractional powers of regular languages and taking prefixes of a fractional length. Indeed, fractional roots in a regular language can typically not be identified by finite automata.

In reoptimization, we consider the following scenario: Given an instance of a hard optimization problem together with an optimal solution for it, we want to solve a locally modified instance of the problem. It has recently been shown for several hard optimization problems that their corresponding reoptimization variants remain 𝒩𝒫-hard or even hard to approximate whereas they often admit improved approximation ratios. In this paper, we investigate a generalization of the reoptimization concept where we are given not only one optimal solution but multiple optimal solutions for an instance. We prove, for some variants of the Steiner tree problem and the traveling salesman problem, that the known reoptimization hardness results carry over to this generalized setting. Moreover, we consider the performance of local search strategies on reoptimization problems. We show that local search does not work for solving TSP reoptimization, even in the presence of multiple solutions.

The ambiguity of a nondeterministic finite automaton (NFA) $N$ for input size $n$ is the maximal number of accepting computations of $N$ for an input of size $n$. For all $k,r \in \mathbb{N}$ we construct languages $L_{r,k}$ which can be recognized by NFA's with size $k \cdot$poly$(r)$ and ambiguity $O(n^k)$, but $L_{r,k}$ has only NFA's with exponential size, if ambiguity $o(n^k)$ is required. In particular, a hierarchy for polynomial ambiguity is obtained, solving a long standing open problem (Ravikumar and Ibarra, 1989, Leung, 1998).

The sizes of permutation networks and planar permutation networks for special sets of permutations are investigated. Several asymptotically optimal estimations for distinct subsets of the set of all permutations are established here. The two main results are as follows: A consequence of our results is the construction of a 4-degree network which can simulate each communication step of any hypercube algorithm using edges from at most a constant number of different dimensions in one communication step in $O(\log\log N)$ communication steps. An essential improvement of gossiping in vertex-disjoint path mode in bounded-degree networks follows.

We present a new technique for differentiating deterministic from nondeterministic communication complexity. As a consequence we give almost tight lower bounds for the nondeterministic communication complexity with a restricted number of advice bits. In particular, for any function $t : \mathbb{N} \rightarrow \mathbb{N}$ with $t(n) \leq n/2$ we construct a family $(L_{n,t(n)} : n \in \mathbb{N})$ of languages such that $L_{n,t(n)} \subseteq \{0,1\}^{2n}$, ${\rm nc}(L_{n,t(n)}) = O(t(n) \cdot \log_2 \frac{n}{t(n)})$ and ${\rm nc}(\overline{L_{n,t(n)}}) = O\bigl(\frac{n}{t(n) \cdot \log_2 \frac{n}{t(n)}} + \log_2 t(n)\bigr)$, but ${\rm nc}_{o(t(n))}(L_{n,t(n)}) = \Omega\bigl(\frac{n}{\log_2 \frac{n}{t(n)}}\bigr)$. Here ${\rm nc}_r(L)$ is the nondeterministic communication complexity of L, assuming that at most r advice bits are utilized. Thus, in contrast to probabilistic communication complexity, a small reduction in the number of advice bits results in almost maximal communication. As a special case we obtain a family $L_n \subseteq \{0,1\}^{2n}$ of languages with {\rm nc}_{o(\sqrt{n}/\log_2 n)}(L_n) &=& \Omega\biggl(\frac{n}{\log_2 n}\biggr),\\ {\rm nc}(L_n) + {\rm nc}(\overline{L_n}) &=& O(\sqrt{n}), and hence nondeterministic communication with slightly restricted access to advice bits is almost quadratically weaker than nondeterminism that always gives correct answers (from the set {yes, no, ?}). As a consequence we obtain an almost optimal separation between Monte-Carlo communication and "correct" nondeterminism and answer a question of Beame and Lawry.

The investigation of the computational power of randomized computations is one of the central tasks of current complexity and algorithm theory. In this paper for the first time a "strong" separation between the power of determinism, Las Vegas randomization, and nondeterminism for a computing model is proved. The computing models considered here are finite automata with two-dimensional input tapes (i.e., finite automata recognizing picture languages).

We present a new technique to differentiate deterministic from nondeterministic communication complexity.As a consequence we give almost tight lower bounds for the nondeterministic communication complexity with a restricted number of advice bits (i.e., nondeterministic guesses).In particular, for any function t : N + N (with t(k) < k/2) we construct a family (L~,t(k) : m c N) of languages such that (a) L~,,f~J'~{O, I} 'k, (b) ncc,(~)(L,,,(k)) = O(t(k)), (c) nc%, k(bc,t(k)) = 0("~k ), (d) but IIC%(t(k)/ bg2 k)(~k,t(k)) = '( Iog2(,&t(k)) )" (ncc, (L) is the nondeterministic communication complexity of L, assuming that at most r advice bits are used for any input.) Thus, in contrast to probabilistic communication complexity, a small reduction in the number of advice bits results in almost maximal communication, even if the original number of advice bits is super-logarithmic.

The lower bounds on communication complexity measures of language generation by Parallel Communicating Grammar Systems (PCGS) are investigated. The first result shows that there exists a language that can be generated by some dag-PCGS (PCGS with communication structures realizable by directed acyclic graphs) consisting of 3 grammars, but by no PCGS with tree communication structure. The second result shows that dag-PCGS have their communication complexity of language generation either constant or linear.

Instead of some ad hoc reductions of the intellectual capacities of human beings an alternative approach to artificial intelligence is suggested that consists of the expansion of the capabilities of well-known (theoretical models of) symbol systems. By some computationally realistic axioms, an abstract computational device—the abstract symbol system—is defined. Then some specific types of the abstract symbol system are defined, namely the static and the dynamic ones, and the corresponding computational powers and complexities are examined and compared. A formal proof is given that a kind of abstract symbol system—the dynamic symbol system—can execute in real time (after some training and some increasing of its own architectural complexity) all Turing machine computations