Most architectures are designed to mitigate the usually undesirable phenomenon of device wearout. We take a contrarian view and harness this phenomenon to create hardware security mechanisms that resist attacks by statistically enforcing an upper bound on hardware uses, and consequently attacks. For example, let us assume that a user may log into a smartphone a maximum of 50 times a day for 5 years, resulting in approximately 91,250 legitimate uses. If we assume at least 8-character passwords and we require login (and retrieval of the storage decryption key) to traverse hardware that wears out in 91,250 uses, then an adversary has a negligible chance of successful brute-force attack before the hardware wears out, even assuming real-world password cracking by professionals. M-way replication of our hardware and periodic re-encryption of storage can increase the daily usage bound by a factor of M.

Abstract. A set A is m-reducible (or Karp-reducible) to B if and only if there is a polynomial-time computable function f such that, for all x, x ∈ A if and only if f(x) ∈ B. Two sets are: • 1-equivalent if and only if each is m-reducible to the other by one-one reductions; • p-invertible equivalent if and only if each is m-reducible to the other by one-one, polynomial-time invertible reductions; and • p-isumorphic if and only if there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible. In this paper we show the following characterization. Theorem. The following are equivalent: (a) P = PSPACE. (b) Every two 1-equivalent sets are p-isomorphic. (c) Every two p-invertible equivalent sets are p-isomorphic.

Gold (1967) discovered a fundamental enumeration technique, the socalled identification-by-enumeration, a simple but powerful class of algorithms for learning from examples (inductive inference). We introduce a variety of more sophisticated (and more powerful) enumeration techniques and characterize their power. We conclude with the thesis that enumeration techniques are even universal in that each solvable learning problem in inductive inference can be solved by an adequate enumeration technique. This thesis is technically motivated and discussed.

The authors introduce symmetric perfect generic sets. These sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. We then show that the Berman–Hartmanis isomorphism conjecture holds relative to any sp-generic oracle, i.e., for any symmetric perfect generic set A, all ${\bf NP}^A $-complete sets are polynomial-time isomorphic relative to A. Prior to this work, there were no known oracles relative to which the isomorphism conjecture held. As part of the proof that the isomorphism conjecture holds relative to symmetric perfect generic sets, it is also shown that ${\bf P} = {textbf{Few}}{\bf P}^{\bf A} $ for any symmetric perfect generic A.

Berman and Hartmanis [1977] conjectured that there is a polynomial-time computable isomorphism between any two languages complete for NP with respect to polynomial-time computable many-one (Karp) reductions.Joseph and Young [1985] gave a structural definition of a class of NP-complete sets-the k-creative sets-and defined a class of sets (the K; 's) that are necessarily ~-creative.They went on to conjecture that certain of these K}'s are not isomorphic to the standard NP-complete sets.Clearly, the Berman-Hartmanis and Joseph-Young conjectures cannot both be correct.We introduce a family of strong one-way functions, the scrambling functions.If f is a scrambling function, then K} is not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails.Indeed, if scrambling functions exist, then the isomorphism also fails at higher complexity classes such as EXP and NEXP.As evidence for the existence of scrambling functions, we show that much more powerful one-way functions-the annihikzting functions-exist relative to a random oracle.Random oracles are the first examples of oracles relative to which the isomorphism conjecture fails with respect to higher classes such as EXP and NEXP.

Most theories of learning consider inferring a function f from either (1) observations about f or, (2) questions about f. We consider a scenario whereby the learner observes fand asks queries to some set A. EX[A] is the set of concept classes EX-learnable by an inductive inference machine with oracle A. A and F are EX-equivalent if EX[A] = EX[B]. The equivalence classes induced are the degrees of inferability. We prove several results about these degrees: (1) There are an uncountable number of degrees. (2) For A r.e., REC e BC[A] iff O'' ≤T A´, and there is evidence this holds for all sets A. (3) For A, B r.e., A ≡T B iff EX[A] = EX[B]. (4) There exists A, B low2 r.e., A|RB, EX[A] = EX[B]. (hence (3) is optimal).

The authors introduce symmetric perfect generic sets. these sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. They then show that the Berman-Hartmanis (1977) isomorphism conjecture holds relative to any sp-generic oracle, i.e., for any symmetric perfect generic set A, all NP/sup A/-complete sets are polynomial-time isomorphic relative to A. As part of the proof that the isomorphism conjecture holds relative to symmetric perfect generic sets they also show that P/sup A/=FewP/sup A/ for any symmetric perfect generic/sup /A.>

A set A is m-reducible (or Karp-reducible) to B if and only if there is a polynomial-time computable function f such that for all x, x in A if and only if f(x) in B. Two sets are 1-equivalent if each is m-reducible to the other by one-one reductions; p-invertible equivalent iff each is m-reducible to the other by one-one, polynomial-time invertible reductions; and p-isomorphic iff there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible. It is proved that the following statements are equivalent: (1) P=PSPACE. (2) Every two 1-equivalent sets are p-isomorphic. (3) Every two p-invertible equivalent sets are p-isomorphic.>

Berman and Hartmanis [BH77] conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete (“Karp” complete) for NP. Joseph and Young [JY85] discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets (the Kkƒ's) are not isomorphic to the standard NP-complete sets for some one-way functions ƒ. These two conjectures cannot both be correct.

We show that if A and B are independent random sets, then ${\bf P}^A \cap {\bf P}^B = {\bf {BPP}}$ with probability one.

An m-degree is a collection of sets equivalent under polynomial-time many-one (Karp) reductions; for example, the complete sets for NP or PSPACE are m-degrees. An m-degree is collapsing iff its members are p-isomorphic, i.e., equivalent under polynomial time, 1-1, onto, polynomial time invertible reductions. L. Berman and J. Hartmanis showed that all the then known natural NP-complete sets are isomorphic, and conjectured that the m-degree of the NP-complete sets collapses, in essence claiming that there is only one NP-complete set. However, until now no nontrivial collapsing m-degree was known to exist. In this paper we provide the first examples of such degrees, In particular, we show that there is a collapsing degree which is btt-complete for EXP (the exponential time decidable sets) and that, for every set A, there is a collapsing degree which is hard for A. We also obtain analogous results for noncollapsing degrees.

We construct an oracle relative to which ${\bf P} \ne \bf {NP}$ and there are no sparse sets in $\bf {NP}$–$\bf {P}$. The well-known construction of Baker, Gill and Solovay [SIAM J. Comput., 4 (1975), pp. 431–442] gives an oracle relative to which there is a sparse set in $\bf {NP}$–${\bf P}$. Together, these results show that simple modifications of conventional proof techniques cannot establish whether or not sparse sets exist in $\bf {NP}$–$\bf {P}$, even if one assumes ${\bf P} \ne \bf {NP}$.

This paper deals with forcing in arithmetic (as first introduced by Feferman [2]) and its connections with recursive function theory. We define for each n ≥ 1 the class of weakly n-generic sets. We prove that these classes merge with the classes of n-generic sets to form the hierarchy suggested by the terminology. Our notation is the same as that of Jockusch [5].

We give two counterexamples to the random oracle hypothesis as formalized by Bennett and Gill[2]. We then discuss the future of the random oracle hypothesis in light of these examples We believe that these examples will severely test any new candidate for a formal random oracle hypothesis.