We consider a simple model for a class of discrete control processes, motivated in part by recent work about the behavior of imperfect random sources in computer algorithms. The process produces a string of characters from {0, 1} of length n and is a “success” or “failure” depending on whether the string produced belongs to a prespecified set L. In an uninfluenced process each character is chosen by a fair coin toss, and hence the probability of success is |L|/2n. We are interested in the effect on the probability of success in the presence of a player (controller) who can intervene in the process by specifying the value of certain characters in the string. We answer the following questions in both worst and average case: (1) how much can the player increase the probability of success given a fixed number of interventions? (2) in terms of |L| what is the expected number of interventions needed to guarantee success? In particular our results imply that if |L|/2n = 1/w(n) where w(n) tends to infinity with n (so the probability of success with no interventions is o(1)) then with Ο(√nlogw(n)) interventions the probability of success is 1-o(1).

In this paper we propose two new multi-layer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes "exist" only on one layer, we prove a tight area x (number of contact cuts) = Θ(n2) trade-off for embedding any degree 4 n-node planar graph in two layers. For the second model in which nodes "exist" simultaneously on all layers, we prove a number of bounds on the area needed to embed graphs using no contact cuts. For example we prove that any n-node graph which is the union of two planar subgraphs can be embedded on two layers in O(n2) area without contact cuts. This bound is tight even if more layers and an unbounded number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers in O(n1.6) area without contact cuts. These results use some interesting new results on embedding graphs in a single layer. In particular we give an O(n2) area embedding of planar graphs such that each edge makes a constant number of turns, and each exterior vertex has a path to the perimeter of the grid making a constant number of turns. We also prove a tight Ω(n3) lower bound on the area of grid n-permutation networks.

We define the set of planar boolean formulae, and then show that the set of true quantified planar formulae is polynomial space complete and that the set of satisfiable planar formulae is NP-complete. Using these results, we are able to provide simple and nearly uniform proofs of NP-completeness for planar node cover, planar Hamiltonian circuit and line, geometric connected dominating set, and of polynomial space completeness for planar generalized geography. The NP-completeness of planar node cover and planar Hamiltonian circuit and line were first proved elsewhere [M. R. Garey and D. S. Johnson, The rectilinear Steiner tree is NP-complete, SIAM J. Appl. Math., 32 (1977), pp. 826–834] and [M. R. Garey, D. S. Johnson and R. E. Tarjan, The planar Hamilton circuit problem is NP-complete, SIAM J. Comp., 5 (1976), pp. 704–714].

There are no known polynomial time algorithms for graph isomorphism. For certain classes of graphs, however, efficient algorithms have been found. In particular, there is a polynomial time algorithm for isomorphism of planar graphs [4,5].

It is shown that, given an arbitrary GO position on an n × n board, the problem of determining the winner is Pspace hard. New techniques are exploited to overcome the difficulties arising from the planar nature of board games. In particular, it is proved that GO is Pspace hard by reducing a Pspace-complete set, TQBF, to a game called generalized geography, then to a planar version of that game, and finally to GO.

A great deal of effort has been spent in the search for optimal and computationally feasible game strategies. In some cases (e.g. Bridge-it, Nim), such strategies have been found, \vhile in others the search has been unsuccessful. Recently, it has become possible to provide compelling evidence that such strategies may not always exist. Even and Tarjan [1] and Schaefer [2] have shown that determining which player has a winning strategy in certain combinatorial games is a polynomial space complete problem [3]. (See also [4;5].)