NP (search) problems allow easy correctness tests for solutions. Climbing algorithms allow also easy assessment of how close to yielding the correct answer is the configuration at any stage of their run. This offers a great flexibility, as how sensible is any deviation from the standard procedures can be instantly assessed.

Gödel Incompleteness Theorem leaves open a way around it, vaguely perceived for a long time but not clearly identified. (Thus, Gödel believed informal arguments can answer any math question.) Closing this loophole does not seem obvious and involves Kolmogorov complexity. (This is unrelated to, well studied before, complexity quantifications of the usual Gödel effects.) I consider extensions U of the universal partial recursive predicate (or, say, Peano Arithmetic). I prove that any U either leaves an n -bit input (statement) unresolved or contains nearly all information about the n -bit prefix of any r.e. real ρ (which is n bits for some ρ). I argue that creating significant information about a specific math sequence is impossible regardless of the methods used. Similar problems and answers apply to other unsolvability results for tasks allowing multiple solutions, for example, nonrecursive tilings.

The notion of Kolmogorov-Martin-Lof Random sequences is extended from computable to enumerable distributions. This allows definitions of various other properties, such as mutual information in infinite sequences. Enumerable distributions (as well as distributions faced in some finite multi-party settings) are semi measures, handling those requires care.

Abstract We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with Kolmogorov complexity of its (n×n)-squares. We construct tile sets for which this bound is tight: all (n×n)-squares in all tilings have complexity Ω(n). This adds a quantitative angle to classical results on non-recursivity of tilings—that we also develop in terms of Turing degrees of unsolvability.

Classical results on aperiodic tilings are rather complicated and not widely understood. In the present article, an alternative approach to these results is discussed in the hope of providing additional intuition, not apparent in classical works.

There appears to be a gap between usual interpretations of Godel Theorem and what is actually proven. Closing this gap does not seem obvious and involves complexity theory. (This is unrelated to, well studied before, complexity quantifications of the usual Godel effects.) Similar problems and answers apply to other unsolvability results for tasks where required solutions are not unique, such as, e.g., non-recursive tilings.

We study the minimal complexity of tilings of a plane with a given tile set. We note that any tile set admits either no tiling or some tiling with \ooo(n) Kolmogorov complexity of its (n\times n)-squares. We construct tile sets for which this bound is nearly tight: all tilings have complexity >n/r(n), given any unbounded computable monotone r. This adds a quantitative angle to classical results on non-recursivity of tilings -- that we also develop in terms of Turing degrees of unsolvability.

[Gacs, Kurdiumov, Levin, 78] proposed simple one-dimensional cellular automata with 2 states. In an infinite array they are self-stabilizing: if all but a finite minority of automata are in the same state, the minority states disappear. Implicit in the paper was a stronger result that a sufficiently small minority of states vanish even in a finite circular array. The following note makes this strengthening explicit.

The usual (i.e. easily computable) probability distributions share a remarkable feature. They are concentrated on strings which do not differ noticeably in any robust characteristic, except their informational size (Kolmogorov complexity). The formalization of this statement (below) distinguishes a class of homogeneous probability measures suggesting various applications. In particular, it may explain why the average case NP-completeness results are so measure-independent and may lead to their generalization to this wider and more invariant class of measures. It also demonstrates a sharp difference between the pseudorandom strings and the objects known before.

Pseudorandom generators are fundamental to many theoretical and applied aspects of computing. We show how to construct a pseudorandom generator from any one-way function. Since it is easy to construct a one-way function from a pseudorandom generator, this result shows that there is a pseudorandom generator if and only if there is a one-way function.

Below is a translation from my Russian paper. I added references, unavailable to me in Moscow. Similar results have been also given in [9] (see also [6]). Earlier relevant work (classical theorems like Compression, Speed-up, etc.) was done in [15,13,2,1,14,7]. I translated only the part with the statement of the results. Instead of the proof part, I appended a later (1979, unpublished) proof sketch of a slightly tighter version. The improvement is based on the results of Meyer and Winklmann [8] and Sipser [12]. Meyer and Winklmann extended earlier versions to machines with a separate input and working tape, thus allowing complexities smaller than the input length (down to its log). Sipser showed the space-bounded Halting Problem to require only additive constant overhead. The proof in the appendix below employs both advances to extend the original proofs to machines with a fixed alphabet and a separate input and working space. The extension has no (even logarithmic) restrictions on complexity and no overhead (beyond an additive constant). The sketch is very brief and a more detailed exposition is expected later [11].

We consider asynchronous general topology dynamic networks of identical nameless nodes with worst-case transient faults. Starting from any faulty configuration, our protocols self-stabilize any computation in time polynomial in the (unknown) network diameter. This version sacrifices some diversity of tasks and efficiency for simplicity and clarity of details. Appendix gives more efficient procedures in less detail.>

. Motivated by Manuel Blum's concept of instance checking, we consider new, very fast and generic mechanisms of checking computations. Our results exploit recent advances in interactive proof protocols [LFKN92], [Sha92], and especially the MIP = NEXP protocol from [BFL91]. We show that every nondeterministic computational task S(x; y), defined as a polynomial time relation between the instance x, representing the input and output combined, and the witness y can be modified to a task S 0 such that: (i) the same instances remain accepted; (ii) each instance/witness pair becomes checkable in polylogarithmic Monte Carlo time; and (iii) a witness satisfying S 0 can be computed in polynomial time from a witness satisfying S. Here the instance and the description of S have to be provided in error-correcting code (since the checker will not notice slight changes). A modification of the MIP proof was required to achieve polynomial time in (iii); the earlier technique yields N O(log log N)...

The task of transforming a weak one-way function (which may be easily inverted on all but a polynomial fraction of the range) into a strong one-way function (which can be easily inverted only on a negligible function of the range) is considered. The previously known transformation does not preserve the security (i.e. the running time of the inverting algorithm) within any polynomial. Its resulting function, F(x), applies the weak one-way function to many small (of length mod x mod /sup theta /, theta>

Distributed NP (DNP) problems are ones supplied with probability distributions of instances. It is shown that every DNP problem complete for P-time computable distributions is also complete for all distributions that can be sampled. This result makes the concept of average-case NP completeness robust and the question of the average-case complexity of complete DNP problems a natural alternative to P=?NP. Similar techniques yield a connection between cryptography and learning theory.

VLSI f-models which allow the switching time to decrease to f(D) when the length of all wires is restricted by D are called 'fast' if the decrease is slightly superlinear. The fast models are so strong and robust that their computational power cannot be increased by and combination of the following: (1) making zero the width of each wire of length d, except for its log d segment, thus eliminating layout and area considerations; (2) allowing wires to transmit log d bits simultaneously; (3) making the switching time f(d) of each node depend only on the length d of its own input wires, thus enabling small subcircuits to run faster; (4) changing f while preserving Sigma /sub k/ 1/f(k); (5) enabling the nodes to change connections arbitrarily in the run time. The authors construct a kind of operating system link server (linx, for short) that simulates all these powers online. The condition of superlinearity cannot be weakened.>

A central tool in constructing pseudorandom generators, secure encryption functions, and in other areas are “hard-core” predicates b of functions (permutations) ƒ, discovered in [Blum Micali 82]. Such b(x) cannot be efficiently guessed (substantially better than 50-50) given only ƒ(x). Both b, ƒ are computable in polynomial time.

We show that the existence of one-way functions is necessary and sufficient for the existence of pseudo-random generators in the following sense. Let ƒ be an easily computable function such that when x is chosen randomly: (1) from ƒ(x) it is hard to recover an x1 with ƒ(x1) = ƒ(x) by a small circuit, or; (2) ƒ has small degeneracy and from ƒ(x) it is hard to recover x by a fast algorithm. From one-way functions of type (1) or (2) we show how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa. Previous results show how to construct pseudo-random generators from one-way functions that have special properties ([Blum, Micali 82], [Yao 82], [Levin 85], [Goldreich, Krawczyk, Luby 88]).

The usual probability distributions are concentrated on strings that do not differ noticeably in any fundamental characteristics, except their informational size (Kolmogorov complexity). The formalization of this statement is given and shown to distinguish a class of homogeneous probability measures suggesting various applications. In particular, it could explain why the average case NP-completeness results are so measure-independent and could lead to their generalization to this wider and more invariant class of measures. It also demonstrates a sharp difference between recently discovered pseudorandom strings and the objects known before.>

NP-complete problems should be hard on some (may be extremely rare) instances. But on generic instances many such problems (especially related to random graphs) have been proven easy. We show the intractability of random instances of a graph coloring problem by modifying the NP-completeness theorem.

Many interesting combinatorial problems were found to be NP-complete. Since there is little hope to solve them fast in the worst case, researchers look for algorithms which are fast just “on average”. This matter is sensitive to the choice of a particular NP-complete problem and a probability distribution of its instances. Some of these tasks were easy and some not. But one needs a way to distinguish the “difficult on average” problems. Such negative results could not only save “positive” efforts but may also be used in areas (like cryptography) where hardness of some problems is a frequent assumption. It is shown below that the Tiling problem with uniform distribution of instances has no polynomial “on average” algorithm, unless every NP-problem with every simple probability distribution has it. It is interesting to try to prove similar statements for other NP-problems which resisted so far “average case” attacks.

One-way are those functions which are easy to compute, but hard to invert on a non-negligible fraction of instances. The existence of such functions with some additional assumptions was shown to be sufficient for generating perfect pseudorandom strings |Blum, Micali 82|, |Yao 82|, |Goldreich, Goldwasser, Micali 84|. Below, among a few other observations, a weaker assumption about one-way functions is suggested, which is not only sufficient, but also necessary for the existence of pseudorandom generators. The main theorem can be understood without reading the sections 3-6.

Many interesting combinatorial problems were found to be NP-complete. Since there is little hope to solve them fast in the worst case, researchers look for algorithms which are fast just “on average”. This matter is sensitive to the choice of a particular NP-complete problem and a probability distribution of its instances. Some of these tasks were easy and some not. But one needs a way to distinguish the “difficult on average” problems. Such negative results could not only save “positive” efforts but may also be used in areas (like cryptography) where hardness of some problems is a frequent assumption. A concept of “NP-complete random problems” proposed below may serve this purpose.

The Ellipsoid Algorithm (EA) for linear programming attracted recently great attention. EA was proposed in [N76] and developed in [K79, G81] and other works. It is a modification of Method of Centralized Splitting presented in [L65], which differs from EA in two essential respects. Firstly, [L65] uses simplexes instead of ellipsoids; it is admitted, secondly, that, several (q(n))splittings of the n-dimensional simplex may be needed before the remaining polyhedron can be enclosed into a simplex of a smaller volume. Only a very rough upper bound q(n) ≪ nlog(n)follows from the reasoning of [L65]. This does not imply polynomiality of the computation time, since n, log(n) splittings may make the simplex very complex. We prove below that, q(n)= 1. Let the problem be to find x∈Rn such that Ax ≫ 0, where A is an m × n matrix of rank n. We normalize solutions by a restriction (e - Ax) = 1 where e ≫ 0. On every step the algorithm considers a simplex BAx ≥ 0 containing all solutions, where B is a non-negative n × m matrix with det(BA) ≠ 0. Let us denote this simplex by ΔB, its volume by VB and its center by CB. Initially we take an arbitrary B and e = BT(1,..,1).