Specific systems for the development of user interfaces (Uls) are used today for coping with the increasing problems of human-computer communication. Some of those systems are based on well-defined models for humancomputer interaction. Important requirements of such systems are: consideration of standards, most notably graphics functionality and windowing functionality, openness to all interaction styles, and provision of comfortable design tools that allow UI prototyping. An evaluation of the existing systems reveals that they fulfill only some of those requirements. We present a layered model for the interface between an application's functionality and its UI, which explicitly takes care of standards. Based on this model we implement a system for efficient design and administration of Uls. An internal interface among all tools, namely, a PROLOG-like formalism used for the description of UI objects, is of central importance. This formalism makes all tools independent from the dialog objects, hence our system is truly open. The core of our system consists of a comfortable graphically interactive editor for UI design and an interpreter. The interpreter is mainly responsible for the presentation of Uls which are described according to this formalism. The output of the editor will be a description of Uls according to the formalism. Our oal is the development of a functionally complete object-oriented set of formalism-based tools; these tools will also use artificial intelligence techniques for an adaptation of Uls to user needs.

A general theory of public-key cryptography is developed that is based on the mathematical framework of complexity theory. Two related approaches are taken to the development of this theory, and these approaches correspond to different but equivalent formulations of the problem of cracking a public-key cryptosystem (PKCS). The first approach is to model the cracking problem as a partial decision problem called a “promise problem.” Every NP-hard promise problem is shown to be uniformly NP-hard, and a number of results and a conjecture about promise problems are shown to be equivalent to separability assertions for sets in NP that are the natural analogues of well-known results in classical recursion theory. The conjecture, if it is true, implies nonexistence of PKCS having NP-hard cracking problems. The second approach represents the cracking problem of a PKCS as a partial computational problem directly. Using this approach, it is shown that one-way functions exist if and only if ${\text{P}} \ne {\text{UP}}$ and that one-way functions with greater cryptographic significance exist if and only if NP contains disjoint P-inseparable sets. The paper concludes with a discussion of almost-everywhere security measures for PKCS.

We study relationships between ${\bf P}$, $NP$ , and the unambiguous and random time classes, ${\bf U}$, and ${\bf R}$. Questions concerning these relationships are motivated by complexity issues in public-key cryptosystems. We prove that there exists a recursive oracle A such that ${\bf P}^A \ne {\bf U}^A \ne {\bf NP}^A $, and such that the first inequality is “strong,” i.e., there exists a ${\bf P}^A $-immune set in ${\bf U}^A $. Further, we construct a recursive oracle B such that ${\bf U}^B $ contains an ${\bf R}^B $-immune set. As a corollary, we obtain ${\bf P}^B \ne {\bf R}^B \ne {\bf NP}^B $ and both inequalities are strong. By use of the techniques employed in the proof that ${\bf P}^A \ne {\bf U}^A \ne {\bf NP}^A $, we are also able to solve an open problem raised by Book, Long and Selman [Quantitative relativizations of complexity classes, SIAM J. Comput. 13 (1984), pp 461–487].

The first part of this paper gives results about promise problems. A "promise problem" is a formulation of a partial decision problem that is useful for describing cracking problems for public-key cryptosystems (PKCS). We prove that every NP-hard promise problem is uniformly NP-hard, and we show that a number of results and a conjecture about promise problems are equivalent to separability assertions that are the natural analogues of well-known results in classical recursion theory. The conjecture, if it is true, implies nonexistence of PKCS having NP-hard cracking problems. The second part of the paper studies more appropriate measures for PKCS. Among the results obtained are the following: One-way functions exist if an only if P /spl ne/ U and one-way functions f such that range f /spl epsiv/ P exist if and only if U /spl cap/ co-U /spl ne/ P. It will allow that there exist PKCS that cannot be cracked in polynomial time (and that satisfy other reasonable assumptions) only if P /spl ne/ U.