We present direct performance measurements for four popular scientific simulations on the Knights Landing (KNL) platform. Performance numbers for Broadwell processors are provided for contrast. The applications (NAMD, LAMMPS, GROMACS and CP2K) were selected from among the ten most used in the QCT developer cloud as well as best representative of workloads used by many users and, given their diversity, should be representative of typical high performance computing workloads. All runs were performed with publicly available codes without modification and so results should be expected to improve as developers gain access to Knights Landing (KNL) processor. Current results are promising, with execution on a single KNL processor showing speedups up to 1.5x with respect to a dual socket Broadwell.

We present direct performance measurement for eight popular HPC applications on the Knights Landing (KNL) platform. Performance numbers for Haswell processors are provided for contrast. The applications (DGEMM. SGEMM, STREAM, IOR, HPCG, Quantum Espresso, WRF and HPL) were selected from among the ten most used in the QCT developer cloud as well as good representative of workloads used by large number of users and, given their diversity, should be representative of typical HPC workloads. All runs were performed with publicly available codes without modification and so results should be expected to improve as developers gain access to KNL. Current results are promising, with execution on a single KNL processor showing speedups up to 1.7x with respect to a dual socket Haswell.

In this paper a new property of sets, near-testability, is introduced. A set S is near-testable$(S \in NT)$ if the membership relation for all immediate neighbors is polynomially computable; i.e., if the function $t(x) = \chi _S (x) + \chi _S (x - 1)(\bmod 2)$ is polynomially computable. The near-testable sets form a subclass of the class $ \oplus P$ (parity polynomial time), introduced by Papadimitriou and Zachos, and Goldschlager and Parberry. $ \oplus P$ has a complete set $ \oplus SAT$ that has recently been shown by Valiant and Vazirani to be hard for $NP$ under randomized polynomial-time reductions. It is proved that there is a uniform polynomial one-one reduction that takes every set in $ \oplus P$ to a near-testable set, and it is shown that the image of $ \oplus SAT$ under this reduction (which we call $NTSAT$) is polynomially isomorphic to $ \oplus SAT$. As corollaries it is shown that $NTSAT$ is complete for both $NT$ and for $ \oplus SAT$, that $NTSAT$ is hard for $NP$ under randomized polynomial-time reductions, and that the existence of one-way functions implies the existence of sets that are near-testable but not polynomially decidable. It is then asked whether near-testability is preserved under p-isomorphisms. This leads to a generalization, $NT^ * $, of $NT$ similar to those introduced by Meyer and Paterson and by Ko for self-reducible sets. With this more general definition, $NT^ * $ is shown to be closed under polynomial-time isomorphisms while remaining a subclass of $ \oplus P$. It is conjectured that it is a proper subclass. In fact it is shown that, relative to a random oracle, the containments $P \subseteq NT \subseteq NT^ * \subseteq \oplus P$ are proper with probability one. It is also shown that, relative to a random oracle, with probability one $NT$ and $NT^ * $ are incomparable with both $NP$ and with $coNP$. Finally, the effects that the distribution and density of elements have on the complexity of near-testable sets are considered.

Sets whose members are enumerated by some Turing machine are called recursively enumerable. We define a set to be polynomially enumerable by iteration if its members are efficiently enumerated by iterated application of some Turing machine. We prove that many complex sets—including all exponential-time complete sets, all NP-complete sets yet obtained by direct construction, and the complements of all such sets—are polynomially enumerable by iteration. These results follow from more general results. In fact, we show that all recursively enumerable sets that are ⪯p1si-self-reducible are polynomially enumerable by iterations, and that all recursive sets that are p1si-self-reducible are bi-enumerable. We also show that when the ⪯p1si-self-reduction is via a function whose inverse is computable in polynomial time, then the above results hold with the polynomial enumeration given by a function whose inverse is computable in polynomial time. In the final section of the paper we show that no NP-complete set can be iteratively enumerated in lexicographically increasing order unless the polynomial time hierarchy collapses to NP. We also show that the sets that are monotonically bi-enumerable are “essentially” the same as the sets in parity polynomial time.

In this abstract and discussion of forthcoming papers, we will be concerned with variations on a common theme: without assuming a solution to P vs NP, what can one say of a general nature that relates structural properties of general classes of sets in NP to reducibilities among these sets? By “structural” we mean, in ways that will become clearer as we proceed, properties which arise from general definitions rather than properties which may arise from a perhaps more “natural” computational point of view. Although quite a bit is known about such questions relative to oracles or relative to the assumption that P @@@@ NP, in so far as possible we wish to obtain absolute results; that is results which are about sets in NP (not relativized) and which can be obtained without assuming a solution to P vs NP. In a final section summarizing our results we will make some general comments about the historical antecedents and possible future significance of this approach.

Abstract In this paper we continue, from [2], the development of provably recursive analysis, that is, the study of real numbers defined by programs which can be proven to be correct in some fixed axiom systemS. In particular we develop the provable analogue of an effective operator on the set of recursive real numbers, namely, a provably correct operator on the set of provably recursive real numbers. In Theorems 1 and 2 we exhibit a provably correct operator on which is discontinuous at 0; we thus disprove the analogue of the Ceitin-Moschovakis theorem of recursive analysis, which states that every effective operator on is (effectively) continuous. Our final theorems show, however, that no provably correct operator on can be proven (inS) to be discontinuous.

In this paper we study two alternative approaches for investigating whether NP complete sets have fast algorithms. One is to ask whether there are long initial segments on which such sets are easily decidable by relatively short programs. The other approach is to ask whether there are weak fragments of arithmetic for which it is consistent to believe that P = NP. We show, perhaps surprisingly, that the two questions are equivalent: It is consistent to believe that P = NP in certain models of weak arithmetic theories iff it is true (in the standard model of computation) that there are infinitely many initial segments on which satisfiability is polynomially decidable by programs that are much shorter than the length of the initial segment.

Although there has been considerable additional work discussing limitations of formal proof techniques for Computer Science ([YO-73&77], [HAR-76], [HAR&HO-77], [HAJ-77&79], [GO-79]), these papers show only very general consequences of incompleteness: the stated results hold for all sufficiently powerful formal systems for Computer Science. Only the work of O'Donnell and of Lipton directly addresses the question of just how powerful formal axioms for Computer Science should be, and these two authors make rather radically different suggestions.

Restricted classes of programming systems (Gödel numberings) are studied, where a programming system is in a given class if every programming system can be translated into it by functions in a given restricted class. For pairs of systems in various “natural” classes, results are given on the existence of isomorphisms (one-to-one and onto translations) between them from the corresponding classes of functions. The results with the most computational significance concern polynomial time programming systems. It is shown that if $\mathcal{P} = \mathcal{N}\mathcal{P}$ then every two polynomial time programming systems are isomorphic via a polynomial time computable function. If $\mathcal{P} \ne \mathcal{N}\mathcal{P}$ this result points the way to the possible existence of “natural” but intractable computational problems concerning programming systems. Results are also given concerning the relationship between the complexity of certain important and commonly used properties of programming systems (such as effective composition of programs) and the complexity of translations into the systems.

The extent to which it is possible, given a program p for computing a function f, to find an optimal program p' which also computes f and is either provably equivalent to p or else provably an optimal program is discussed The methods and problems come chiefly from abstract recurs~on-theoretlc complexity theory, but some of the results may be wewed as directly challenging the intuitive interpretation of earlier results in this area

We study restricted classes of programming systems (Godel numberings), where a programming system is in a given class if every programming system can be translated into it by functions in a given restricted class. For pairs of systems in various “natural” classes we give results on the existence of isomorphisms (one-to-one and onto translations) between them from the appropriate class of functions. Our results with the most computational significance concern polynomial time programming systems. We show that if P=NP then every two polynomial time programming systems are isomorphic via a polynomial time computable function. IfP

The relationship between computational complexity and hierarchies of computable Functions is explored.It is shown that known results of hierarchy theory have interesting applications to the Blum theory of computational complexity and, conversely, the Blum theory has applications to hierarchy theory.For example, it is shown that the Blum Speed-up Theorem guarantees the existence of nondegenerate hierarchies of computable functions through all the Church-Kleene constructive ordinal numbers without obtaining all total recursive functions in the hierarchy.In the other direction, a theorem of Kreisel and Parikh on the nonuniqueness of hierarchies forces a number of "irregularities" in the McCreight-Meyer notion of "class-determining measured sets."A variation of the well-known Borodin-Constable Gap Theorem is presented.In toto, still more evidence is presented for the claim originally advanced by Young that it is reasonable to expect an interplay between theories of computational complexity and known results in "pure" reeursion theory.

Since the publication in 1967 of the two papers [1] and [2] by Manuel Blum, the techniques and results of “pure” recursion theory, particularly the recursion theorem and priority methods, have come to play an increasingly important role in studies of computational complexity. This paper gives a typical application of the recursion theorem with a fairly intricate diagonalization to answer a question raised by Blum in [3]. Roughly, we prove the existence of functions which have the property that if we are given any program for computing the function and want to pass to a program which computes the function much more efficiently, then we can only do so at the expense of obtaining a much larger program: the function which describes the necessary increase in the size of the more efficient program must grow more rapidly than any recursive function.