Abstract Motivation: We devise a computational model using protein–protein interactions. Results: Peptide–antibody interactions can be used to perform a large number of small logical operations in parallel. We show for example how a sequence of operations can be used to compare the number of occurrences of an element in two sets and how to estimate the number of occurrences of an element in a set. Similar to DNA-computing, these techniques could in principle be extended to solve instances of NP-complete problems. We give as an example a procedure to solve examples of the satisfiability problem. Contact: [email protected]; [email protected] * To whom correspondence should be addressed.

We consider the resource bounded measure of polynomial-time learnable subclasses of polynomial-size circuits. We show that if EXP/spl ne/MA, then every PAC-learnable subclass of P/poly has EXP-measure zero. We introduce a nonuniformly computable variant of resource bounded measure and show that, for every fixed polynomial q, any polynomial-time learnable subclass of circuits of size q has measure zero with respect to P/poly. We relate our results to the question whether Boolean Circuits are polynomial-time learnable.

Polynomial-time computable as well as polynomial-time samplable distributions play a central role in the theory of average-case complexity. It is known that for every constant k there are polynomial-time samplable distributions which dominate every distribution that is samplable in time O(n/sup k/). The result is based on the fact that there exists an enumeration of the O(n/sup k/)-time samplable distributions. No such enumeration is known for the polynomial-time computable distributions. In this note we show that never the less for every constant k there are polynomial-time computable distributions which dominate every distribution that is computable in time O(n/sup k/). Both results imply that a paddable set is polynomial-time on average under every polynomial-time samplable (polynomial-time computable) distribution if the set is polynomial time on average under a fixed polynomial-time samplable (polynomial-time computable) distribution. This is not true for sets in general, in particular there is no universal distribution for the set of polynomial-time computable distributions.

Let P/sub P-comp/ denote the sets that are solvable in polynomial time on average under every polynomial time computable distribution on the instances. In this paper we show that the truth-table closure of P/sub P-comp/ has measure 0 in EXP. Since, as we show, EXP is Turing reducible to P/sub P-comp/, the Turing closure has measure 1 in EXP and thus, P/sub P-comp/ is an example of a subclass of E such that the closure under truth-table reduction and the closure under Turing reduction have different measures in EXP. Furthermore, it is shown that there exists a set A in P/sub P-comp/ such that for every k, the class of sets L such that A is k-truth-table reducible to L has measure 0 in EXP.