We investigate neural circuits in the exacting setting that (i) the acquisition of a piece of knowledge can occur from a single interaction, (ii) the result of each such interaction is a rapidly evaluatable subcircuit, (iii) hundreds of thousands of such subcircuits can be acquired in sequence without substantially degrading the earlier ones, and (iv) recall can be in the form of a rapid evaluation of a composition of subcircuits that have been so acquired at arbitrary different earlier times.We develop a complexity theory, in terms of asymptotically matching upper and lower bounds, on the capacity of a neural network for executing, in this setting, the following action, which we call {\it association}: Each action sets up a subcircuit so that the excitation of a chosen set of neurons A will in future cause the excitation of another chosen set B.% As model of computation we consider the neuroidal model, a fully distributed model in which the quantitative resources n, the neuron numbers, d, the number of other neurons each neuron is connected to, and k, the inverse of the maximum synaptic strength, are all accounted for.A succession of experiences, possibly over a lifetime, results in the realization of a complex set of subcircuits. The composability requirement constrains the model to ensure that, for each association as realized by a subcircuit, the excitation in the triggering set of neurons A is quantitatively similar to that in the triggered set B, and also that the unintended excitation in the rest of the system is negligible. These requirements ensure that chains of associations can be triggeredWe first analyze what we call the Basic Mechanism, which uses only direct connections between neurons in the triggering set A and the target set B. We consider random networks of n neurons with expected number d of connections to and from each. We show that in the composable context capacity growth is limited by d2, a severe limitation if the network is sparse, as it is in cortex. We go on to study the Expansive Mechanism, that additionally uses intermediate relay neurons which have high synaptic weights. For this mechanism we show that the capacity can grow as dn, to within logarithmic factors. From these two results it follows that in the composable regime, for the realistic cortical estimate of d=n1/2, superlinear capacity of order n3/2in terms of the neuron numbers can be realized by the Expansive Mechanism, instead of the linear order n to which the Basic Mechanism is limited. More generally, for both mechanisms, we establish matching upper and lower bounds on capacity in terms of the parameters n, d, and the inverse maximum synaptic strength k.The results as stated above assume that in a set of associations, a target B can be triggered by at most one set A. It can be shown that the capacities are similar if the number m of As that can trigger a B is greater than one but small, but become severely constrained if m exceeds a certain threshold.

For certain subclasses of NP, $\oplus$P, or #P characterized by local constraints, it is known that if there exist any problems within that subclass that are not polynomial time computable, then all the problems in the subclass are NP-complete, $\oplus$P-complete, or #P-complete. Such dichotomy results have been proved for characterizations such as constraint satisfaction problems and directed and undirected graph homomorphism problems, often with additional restrictions. Here we give a dichotomy result for the more expressive framework of Holant problems. For example, these additionally allow for the expression of matching problems, which have had pivotal roles in the development of complexity theory. As our main result we prove the dichotomy theorem that, for the class $\oplus$P, every set of symmetric Holant signatures of any arities that is not polynomial time computable is $\oplus$P-complete. The result exploits some special properties of the class $\oplus$P and characterizes four distinct tractable subclasses within $\oplus$P. It leaves open the corresponding questions for NP, $\#$P, and $\#_k$P for $k\neq 2$.

It is suggested here that mammalian hippocampus serves as an allocator of neurons in cortex for memorizing new items. A construction of a shallow feedforward network with biologically plausible parameters is given that possesses the characteristics needed for such an allocator. In particular, the construction is stabilizing in that for inputs within a range of activity levels spanning more than an order of magnitude, the output will have activity levels differing as little as 1%. It is also noise tolerant in that pairs of input patterns that differ little will generate output patterns that differ little. Further, pairs of inputs that differ by much will be mapped to outputs that also differ sufficiently that they can be treated by cortex as distinct.

Living organisms function in accordance with complex mechanisms that operate in different ways depending on conditions. Darwin's theory of evolution suggests that such mechanisms evolved through variation guided by natural selection. However, there has existed no theory that would explain quantitatively which mechanisms can so evolve in realistic population sizes within realistic time periods, and which are too complex. In this article, we suggest such a theory. We treat Darwinian evolution as a form of computational learning from examples in which the course of learning is influenced only by the aggregate fitness of the hypotheses on the examples, and not otherwise by specific examples. We formulate a notion of evolvability that distinguishes function classes that are evolvable with polynomially bounded resources from those that are not. We show that in a single stage of evolution monotone Boolean conjunctions and disjunctions are evolvable over the uniform distribution, while Boolean parity functions are not. We suggest that the mechanism that underlies biological evolution overall is “evolvable target pursuit”, which consists of a series of evolutionary stages, each one inexorably pursuing an evolvable target in the technical sense suggested above, each such target being rendered evolvable by the serendipitous combination of the environment and the outcomes of previous evolutionary stages.

Over a lifetime, cortex performs a vast number of different cognitive actions, mostly dependent on experience. Previously it has not been known how such capabilities can be reconciled, even in principle, with the known resource constraints on cortex, such as low connectivity and low average synaptic strength. Here we describe neural circuits and associated algorithms that respect the brain's most basic resource constraints and support the execution of high numbers of cognitive actions when presented with natural inputs. Our circuits simultaneously support a suite of four basic kinds of task, each requiring some circuit modification: hierarchical memory formation, pairwise association, supervised memorization, and inductive learning of threshold functions. The capacity of our circuits is established by experiments in which sequences of several thousand such actions are simulated by computer and the circuits created tested for subsequent efficacy. Our underlying theory is apparently the only biologically plausible systems-level theory of learning and memory in cortex for which such a demonstration has been performed, and we argue that no general theory of information processing in the brain can be considered viable without such a demonstration.

Endowing computers with the ability to apply commonsense knowledge with human-level performance is a primary challenge for computer science, comparable in importance to past great challenges in other fields of science such as the sequencing of the human genome. The right approach to this problem is still under debate. Here we shall discuss and attempt to justify one approach, that of {\it knowledge infusion}. This approach is based on the view that the fundamental objective that needs to be achieved is {\it robustness} in the following sense: a framework is needed in which a computer system can represent pieces of knowledge about the world, each piece having some uncertainty, and the interactions among the pieces having even more uncertainty, such that the system can nevertheless reason from these pieces so that the uncertainties in its conclusions are at least controlled. In knowledge infusion rules are learned from the world in a principled way so that subsequent reasoning using these rules will also be principled, and subject only to errors that can be bounded in terms of the inverse of the effort invested in the learning process.

Complexity theory is built fundamentally on the notion of efficient reduction among computational problems. Classical reductions involve gadgets that map solution fragments of one problem to solution fragments of another in one-to-one, or possibly one-to-many, fashion. In this paper we propose a new kind of reduction that allows for gadgets with many-to-many correspondences, in which the individual correspondences among the solution fragments can no longer be identified. Their objective may be viewed as that of generating interference patterns among these solution fragments so as to conserve their sum. We show that such holographic reductions provide a method of translating a combinatorial problem to finite systems of polynomial equations with integer coefficients such that the number of solutions of the combinatorial problem can be counted in polynomial time if one of the systems has a solution over the complex numbers. We derive polynomial time algorithms in this way for a number of problems for which only exponential time algorithms were known before. General questions about complexity classes can also be formulated. If the method is applied to a #P-complete problem, then polynomial systems can be obtained, the solvability of which would imply P$^{{\tiny{#P}}}$ = NC2.

We provide evidence for the proposition that the computational complexity of individual problems, and of whole complexity classes, hinge on the existence of certain solvable polynomial systems that are unlikely to be encountered other than by systematic explorations for them. We consider a minimalist version of Cook's 3CNF problem, namely that of monotone planar 3 CNF formulae where each variable occurs twice. We show that counting the number of solutions of these modulo 2 is oplusP-complete (hence NP-hard) but counting them modulo 7 is polynomial time computable (sic). We also show a similar dichotomy for a vertex cover problem. To derive completeness results we use a new holographic technique for proving completeness results in oplusP for problems that are in P. For example, we can show in this way that oplus2CNF, the parity problem for 2CNF, is oplusP-complete. To derive efficient algorithms we use computer algebra systems to find appropriate holographic gates. In order to explore the limits of holographic techniques we define the notion of an elementary matchgrid algorithm to capture a natural but restricted use of them. We show that for the NP-complete general 3 CNF problem no such elementary matchgrid algorithm can exist. We observe, however, that it remains open for many natural #P-complete problems whether such elementary matchgrid algorithms exist, and for the general CNF problem whether non-elementary matchgrid algorithms exist

A central open question of computational neuroscience is to identify the data structures and algorithms that are used in mammalian cortex to support successive acts of the basic cognitive tasks of memorization and association. This letter addresses the simultaneous challenges of realizing these two distinct tasks with the same data structure, and doing so while respecting the following four basic quantitative parameters of cortex: the neuron number, the synapse number, the synapse strengths, and the switching times. Previous work has not succeeded in reconciling these opposing constraints, the low values of synapse strengths that are typically observed experimentally having contributed a particular obstacle. In this article, we describe a computational scheme that supports both memory formation and association and is feasible on networks of model neurons that respect the widely observed values of the four quantitative parameters. Our scheme allows for both disjoint and shared representations. The algorithms are simple, and in one version both memorization and association require just one step of vicinal or neighborly influence. The issues of interference among the different circuits that are established, of robustness to noise, and of the stability of the hierarchical memorization process are addressed. A calculus therefore is implied for analyzing the capabilities of particular neural systems and subsystems, in terms of their basic numerical parameters.

We introduce a new notion of efficient reduction among computational problems. Classical reductions involve gadgets that map local solutions of one problem to local solutions of another in one-to-one, or possibly many-to-one or one-to-many, fashion. Our proposed reductions allow for gadgets with many-to-many correspondences. Their objective is to preserve the sum of the local solutions. Such reductions provide a method of translating a combinatorial problem to a family of finite systems of polynomial equations with integer coefficients such that the number of solutions of the combinatorial problem can be counted in polynomial time if some system in the family has a solution over the complex numbers. We can derive polynomial time algorithms in this way for ten problems for which only exponential time algorithms were known before. General questions about complexity classes are also formulated. If the method is applied to a #P-complete problem then we obtain families of polynomial systems such that the solvability of any one member would imply P/sup #P/ = NC2.

article Share on Three problems in computer science Author: Leslie G. Valiant Harvard University Harvard UniversityView Profile Authors Info & Claims Journal of the ACMVolume 50Issue 1pp 96–99https://doi.org/10.1145/602382.602410Published:01 January 2003Publication History 22citation3,204DownloadsMetricsTotal Citations22Total Downloads3,204Last 12 Months68Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 × 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. Therefore, it is possible that, The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent with one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.

A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. In other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to Turing machines for any problem. The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.

An architecture is described for designing systems that acquire and ma nipulate large amounts of unsystematized, or so-called commonsense, knowledge. Its aim is to exploit to the full those aspects of computational learning that are known to offer powerful solutions in the acquisition and maintenance of robust knowledge bases. The architecture makes explicit the requirements on the basic computational tasks that are to be performed and is designed to make this computationally tractable even for very large databases. The main claims are that (i) the basic learning and deduction tasks are provably tractable and (ii) tractable learning offers viable approaches to a range of issues that have been previously identified as problematic for artificial intelligence systems that are programmed. Among the issues that learning offers to resolve are robustness to inconsistencies, robustness to incomplete information and resolving among alternatives. Attribute-efficient learning algorithms, which allow learning from few examples in large dimensional systems, are fundamental to the approach. Underpinning the overall architecture is a new principled approach to manipulating relations in learning systems. This approach, of independently quantified arguments, allows propositional learning algorithms to be applied systematically to learning relational concepts in polynomial time and in modular fashion.

Article Robust logics Share on Author: Leslie G. Valiant Division of Engineering and Applied Sciences, Harvard University, Cambridge, MA Division of Engineering and Applied Sciences, Harvard University, Cambridge, MAView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 642–651https://doi.org/10.1145/301250.301425Online:01 May 1999Publication History 12citation575DownloadsMetricsTotal Citations12Total Downloads575Last 12 Months13Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A method of combining learning algorithms is described that preserves attribute efficiency. It yields learning algorithms that require a number of examples that is polynomial in the number of relevant variables and logarithmic in the number of irrelevant ones. The algorithms are simple to implement and realizable on networks with a number of nodes linear in the total number of variables. They can be viewed as strict generalizations of Littlestone's Winnow algorithm, and, therefore, appropriate to domains having very large numbers of attributes, but where nonlinear hypotheses are sought.

Article Free Access Share on Rationality Author: Leslie G. Valiant Division of Applied Sciences, Harvard University, Cambridge, MA Division of Applied Sciences, Harvard University, Cambridge, MAView Profile Authors Info & Claims COLT '95: Proceedings of the eighth annual conference on Computational learning theoryJuly 1995 Pages 3–14https://doi.org/10.1145/225298.225299Online:05 July 1995Publication History 13citation475DownloadsMetricsTotal Citations13Total Downloads475Last 12 Months17Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Cognitive computation is discussed as a discipline that links together neurobiology, cognitive psychology and artificial intelligence.

Efficient distribution-free learning of Boolean formulas from positive and negative examples is considered. It is shown that classes of formulas that are efficiently learnable from only positive examples or only negative examples have certain closure properties. A new substitution technique is used to show that in the distribution-free case learning DNF (disjunctive normal form formulas) is no harder than learning monotone DNF. We prove that monomials cannot be efficiently learned from negative examples alone, even if the negative examples are uniformly distributed. It is also shown that, if the examples are drawn from uniform distributions, then the class of DNF in which each variable occurs at most once is efficiently weakly learnable (i.e., individual examples are correctly classified with a probability larger than 1/2 + 1/ p , where p is a polynomial in the relevant parameters of the learning problem). We then show an equivalence between the notion of weak learning and the notion of group learning , where a group of examples of polynomial size, either all positive or all negative, must be correctly classified with high probability.

In this paper, we prove the intractability of learning several classes of Boolean functions in the distribution-free model (also called the Probably Approximately Correct or PAC model) of learning from examples. These results are representation independent , in that they hold regardless of the syntactic form in which the learner chooses to represent its hypotheses. Our methods reduce the problems of cracking a number of well-known public-key cryptosystems to the learning problems. We prove that a polynomial-time learning algorithm for Boolean formulae, deterministic finite automata or constant-depth threshold circuits would have dramatic consequences for cryptography and number theory. In particular, such an algorithm could be used to break the RSA cryptosystem, factor Blum integers (composite numbers equivalent to 3 modulo 4), and detect quadratic residues. The results hold even if the learning algorithm is only required to obtain a slight advantage in prediction over random guessing. The techniques used demonstrate an interesting duality between learning and cryptography. We also apply our results to obtain strong intractability results for approximating a generalization of graph coloring.

Article Free Access Share on Crytographic limitations on learning Boolean formulae and finite automata Authors: M. Kearns Harvard University Harvard UniversityView Profile , L. G. Valiant Harvard University Harvard UniversityView Profile Authors Info & Claims STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computingFebruary 1989 Pages 433–444https://doi.org/10.1145/73007.73049Published:01 February 1989Publication History 144citation661DownloadsMetricsTotal Citations144Total Downloads661Last 12 Months75Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The computational complexity of learning Boolean concepts from examples is investigated. It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP. These classes include (a) disjunctions of two monomials, (b) Boolean threshold functions, and (c) Boolean formulas in which each variable occurs at most once. Relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.

Article Free Access Share on On the learnability of Boolean formulae Authors: M. Kearns Harvard University Harvard UniversityView Profile , M. Li Harvard University Harvard UniversityView Profile , L. Pitt University of Illinois University of IllinoisView Profile , L. Valiant Harvard University Harvard UniversityView Profile Authors Info & Claims STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computingJanuary 1987 Pages 285–295https://doi.org/10.1145/28395.28426Online:01 January 1987Publication History 157citation769DownloadsMetricsTotal Citations157Total Downloads769Last 12 Months62Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A randomized algorithm that sorts on an N node network with constant valence in O (log N ) time is given. More particularly, the algorithm sorts N items on an N -node cube-connected cycles graph, and, for some constant k , for all large enough α , it terminates within kα log N time with probability at least 1 - N - α .

It is shown that for any slice function of n variables the monotone circuit complexity exceeds the circuit complexity over a universal basis by at most a multiplicative constant factor and an additive term of order $O(n(\log n)^2 )$.

For all known NP-complete problems the number of solutions in instances having solutions may vary over an exponentially large range. Furthermore, most of the well-known ones, such as satisfiability, are parsimoniously interreducible, and these can have any number of solutions between zero and an exponentially large number. It is natural to ask whether the inherent intractability of NP-complete problems is caused by this wide variation. In this paper we give a negative answer to this using randomized reductions. We show that the problems of distinguishing between instances of SAT having zero or one solution, or finding solutions to instances of SAT having unique solutions, are as hard as SAT itself. Several corollaries about the difficulty of specific problems follow. For example if the parity of the number of solutions of SAT can be computed in RP then NP = RP. Some further problems can be shown to be hard for NP or DP via randomized reductions.

A projection of a Boolean function is a function obtained by substituting for each of its variables a variable, the negation of a variable, or a constant. Reducibilities among computational problems under this relation of projection are considered. It is shown that much of what is of everyday relevance in Turing-machine-based complexity theory can be replicated easily and naturally in this elementary framework. Finer distinctions about the computational relationships among natural problems can be made than in previous formulations and some negative results are proved.

We give a randomized algorithm that sorts on an N node network with constant valence in 0(log N) time. More particularly the algorithm sorts N items on an N node cube-connected cycles graph and for some constant k for all large enough α it terminates within kα log N time with probability at least 1−N−α.

In this paper we consider monotone Boolean circuits with three alternations, in the order “or”, “and”, “or.” Whenever the number of alternations is limited to a fixed constant the formula and circuit size measures are polynomially related to each other. We shall therefore refer to this measure interchangeably as ΣπΣ-formula size or ΣπΣ-circuit size. We shall prove that any such circuit or formula for detecting the existence of cliques in an N-node graph has at least 2Ω(Nε) gates for some ε > 0 independent of N.

It is shown that any multivariate polynomial of degree d that can be computed sequentially in C steps can be computed in parallel in $O((\log d)(\log C + \log d))$ steps using only $(Cd)^{O(1)} $ processors.

It is shown that for d-way shuffle graphs all oblivious algorithms for realizing permutations in logarithmic time send packets along routes twice as long as the diameter of the graph. This confirms the optimality of the strategy that sends packets to random nodes in a first phase and to the correct destinations in the second. For the shuffle-exchange graph the corresponding route length is shown to be strictly longer than for the 2-way shuffle.

Consider $N = 2^n $ nodes connected by wires to make an n-dimensional binary cube. Suppose that initially the nodes contain one packet each addressed to distinct nodes of the cube. We show that there is a distributed randomized algorithm that can route every packet to its destination without two packets passing down the same wire at any one time, and finishes within time $O(\log N)$ with overwhelming probability for all such routing requests. Each packet carries with it $O(\log N)$ bits of bookkeeping information. No other communication among the nodes takes place. The algorithm offers the only scheme known for realizing arbitrary permutations in a sparse N node network in $O(\log N)$ time and has evident applications in the design of general purpose parallel computers.

A projection of a Boolean function is a function obtained by substituting for each of its variables a variable, the negation of a variable, or a constant. Reducibilities among computational problems under this relation of projection are considered. It is shown that much of what is of everyday relevance in Turing-machine-based complexity theory can be replicated easily and naturally in this elementary framework. Finer distinctions about the computational relationships among natural problems can be made than in previous formulations and some negative results are proved.

An algorithm is given for routing in permutation networks-that is, for computing the switch settings that implement a given permutation. The algorithm takes serial timeO(n(logN)2) (for one processor with random access to a memory ofO(n) words) or parallel timeO((logn)3) (fornsynchronous processors with conflict-free random access to a common memory ofO(n) words). These time bounds may be reduced by a further logarithmic factor when all of the switch sizes are integral powers of two.

The problem of embedding the interconnection pattern of a circuit into a two-dimensional surface of minimal area is discussed. Since even for some natural patterns graphs containingmconnections may require Ω(m2) area, in order to achieve compact embeddings restricted classes of graphs have to be considered. For example, arbitrary trees (of bounded degree) can be embedded in linear area without edges crossing over. Planar graphs can be embedded efficiently only if crossovers are allowed in the embedding.

Among the most remarkable algorithms in algebra are Strassen's algorithm for the multiplication of matrices and the Fast Fourier Transform method for the convolution of vectors. For both of these problems the definition suggests an obvious algorithm that uses just the monotone operations + and ×. Schnorr [18] has shown that these algorithms, which use θ(n3) and Θ(n2) operations respectively, are essentially optimal among algorithms that use only these monotone operations.

The class of $# P$-complete problems is a class of computationally eqivalent counting problems (defined by the author in a previous paper) that are at least as difficult as the $NP$-complete problems. Here we show, for a large number of natural counting problems for which there was no previous indication of intractability, that they belong to this class. The technique used is that of polynomial time reduction with oracles via translations that are of algebraic or arithmetic nature.

It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations. Related counting problems are also considered. The reductions used are characterized by their nontrivial use of arithmetic.

The main purpose of this paper is to give techniques for analysing the probabilistic performance of certain kinds of algorithms, and hence to suggest some fast algorithms with provably desirable probabilistic behaviour. The particular problems we consider are: finding Hamiltonian circuits in directed graphs (DHC), finding Hamiltonian circuits in undirected graphs (UHC), and finding perfect matchings in undirected graphs (PM). We show that for each problem there is an algorithm that is extremely fast (0(n(log n)2) for DHC and UHC, and 0(nlog n) for PM), and which with probability tending to one finds a solution in randomly chosen graphs of sufficient density. These results contrast with the known NP-completeness of the first two problems [2,12] and the best worst-case upper bound known of 0(n2.5) for the last [9].

It is shown that every deterministic multitape Turing machine of time complexity t ( n ) can be simulated by a deterministic Turing machine of tape complexity t ( n )/log t ( n ). Consequently, for tape constructable t ( n ), the class of languages recognizable by multitape Turing machines of time complexity t ( n ) is strictly contained in the class of languages recognized by Turing machines of tape complexity t ( n ). In particular the context-sensitive languages cannot be recognized in linear time by deterministic multitape Turing machines.

We show that there is a combinational (acyclic) Boolean circuit of complexity 0(slog s), that can be made to compute any Boolean function of complexity s by setting its specially designated set of control inputs to appropriate fixed values. We investigate the construction of such “universal circuits” further so as to exhibit directions in which refinements of the asymptotic multiplicative constant factor in the complexity bound can be found. In this pursuit useful detailed guidance is provided by available lower bound arguments. In the final section we discuss some other problems in computational complexity that can be related directly to the graph-theoretic ideas behind our constructions. For motivation we start by illustrating some of the applications of universal circuits themselves.

Graphs that in a certain precise sense are rich in sets of vertex-disjoint paths are studied. Bounds are obtained on the minimum number of edges in such graphs, and these are used to deduce nonlinear lower bounds on the computational complexity of shifting, merging, and matching problems.

The purpose of this paper is to explore the possibility that purely graph-theoretic reasons may account for the superlinear complexity of wide classes of computational problems. The results are therefore of two kinds: reductions to graph theoretic conjectures on the one hand, and graph theoretic results on the other.

It ~S shown that to decide whether the language accepted by an arbitrary deterministic pushdown automaton is LL (k), or whether ~t m accepted by some one-counter or finite-turn pushdown machine, must be at least as difficult as to decide whether it is regular.The regularity problem itself is analyzed in detail, and Stearns' dec~mon procedure for this as improved by one level of exponentiatlon Upper bounds, close to known lower bounds, are obtained for the succinctness with which a pushdown automaton, and various restrictions of it, can express equivalent fimte-state machines

The worst-case time complexity of algorithms for multiprocessor computers with binary comparisons as the basic operations is investigated. It is shown that for the problems of finding the maximum, sorting, and merging a pair of sorted lists, if n, the size of the input set, is not less than k, the number of processors, speedups of at least $O(k/\log \log k)$ can be achieved with respect to comparison operations. The algorithm for finding the maximum is shown to be optimal for all values of k and n.

A deterministic pushdown automaton (dpda) is described as finite-turn if there is a bound on the number of times the direction of the stack movement can change in the set of all derivations from the starting configuration. The purpose of this paper is to show that there exists a procedure for deciding whether two such finite-turn machines recognize the same language. By virtue of a direct correspondence between a restricted class of one-turn dpda and deterministic two-tape acceptors (Valiant (1973)), our proof also provides a solution to the equivalence problem for the latter, alternative to that of Bird (1973). Since some of the ideas we introduce are not related exclusively to the finite-turn property, or even pushdown machines, it is hoped that our methods can be adapted for constructing equivalence tests for other classes of deterministic automata.