Complexity classes and theories of finite models

LetL ^* be accepted in timef(n) by a nondeterministic Turing machine. Then there is a monadic existential second-order sentence in the language of + such that for everyx^*,xL if and only if a certain structureU _x ^f of cardinalityf(|x|) satisfies . It follows that ifL is accepted in nondeterministic timen ^d, d a natural number, then there is a sentence whose relational symbols ared-ary or less, whose finite spectrum isL. This research was partially supported by NSF Grants MCS78-01832 and MCS-8002695.     

A decision procedure for combinations of propositional temporal logic and other specialized theories

We present a decision procedure for formulae of discrete linear time propositional temporal logic whose propositional part may include assertions in a specialized theory. The combined decision procedure may be viewed as an extension of known decision procedures for quantifier-free theories to theories including temporal logic connectives. A combined decision procedure given by Pratt restricted to linear time temporal logic, runs in polynomial space relative to an oracle for the underlying theory. Our procedure differs from this one in that it can handle assertions containing arbitrary mixtures of global variables, whose values cannot change with time, and state variables, whose values can change with time. This new procedure can also handle assertions containing functions and predicates whose interpretations do not change with time. However, it requires the computation of least and greatest fixed points and has a worse asymptotic running time than that of Pratt. This new procedure has been implemented and seems efficient enough to be practical on simple formulae, although an upper bound derived for the worst case running time is triple exponential in the length of the formula. The techniques used appear to apply to logics other than temporal logic which have decision procedures based on tableaux. Most of this work was done while the author was at SRI International, Menlo Park, California, and at the University of Illinois, Urbana, Illinois, U.S.A. This work was partially supported by the National Science Foundation under grants MCS 81-09831 and MCS 83-07755.     

Digital convexity, straightness, and convex polygons

New schemes for digitizing regions and arcs are introduced. It is then shown that under these schemes, Sklansky's definition of digital convexity is equivalent to other definitions. Digital convex polygons of n vertices are defined and characterized in terms of geometric properties of digital line segments. Also, a linear time algorithm is presented that, given a digital convex region, determines the smallest integer n such that the region is a digital convex n-gon.     

DRM, Complexity, and Correctness

Steve Bellovin looks at the complex code behind Microsoft Vista and its DRM mechanisms. Increased amounts of code add to insecurity, but the real danger with DRM is with increased interaction among different pieces of code. A lot of new mechanisms have been introduced; more seriously, a lot of new communications paths and dependencies have been introduced. Worst of all, these paths and mechanisms are solving a new problem, one with which the profession has very little experience. Did Microsoft get it right?     

Digital and cellular convexity

We introduce a new definition of cellular convexity on square mosaics. We also define digital convexity for 4-connected sets of points on a square lattice. Using these definitions we show that a cellular complex is cellularly convex if and only if the digital region determined by the complex is digitally convex. We also show that a digital region is digitally convex if and only if the minimum-perimeter polygon (MPP) enclosing the digital region contains only the digital region. This result is related to a property of the MPP of the half-cell expansion of the complex determined by the digital region.     

Complexity,Confusion, and Perceptual Grouping. Part II: Mapping Complexity

International Journal of Computer Vision - Intermediate-level vision is central to form perception, and we outline an approach to intermediate-level segmentation based on complexity analysis. In...     

Incompleteness,Complexity, Randomness and Beyond

Gödel's Incompleteness Theorems have the same scientific status as Einstein's principle of relativity, Heisenberg's uncertainty principle, and Watson and Crick's double helix model of DNA. Our aim is to discuss some new faces of the incompleteness phenomenon unveiled by an information-theoretic approach to randomness and recent developments in quantum computing.     

Information, Architecture, Complexity

The study of the relationship between information, architecture and complexity can be accomplished through the study of patterns of relationships, opening up the field for the understanding of architecture as organization.     

Multivariate Bernstein polynomials and convexity

It is well-known that in two or more variables Bernstein polynomials do not preserve convexity. Here we present two variations, one stronger than the classical notion, the other one weaker, which are preserved and do coincide with classical convexity in the univariate case. Moreover, it will be shown that even the weaker notion is sufficient for the monotonicity of successive Bernstein polynomials, strengthening the well-known result that monotonicity holds for classically convex functions.     

Global convexity of curves and polygons

In this paper we consider a definition of convexity given by Schoenberg and show the connection with other definitions of convexity used by several authors. The representations of curves which preserve the convexity of the control polygon are analyzed and described.     

Differentiability and convexity of fuzzy mappings

Goetschel and Voxman [1] have introduced the notion of a derivative for fuzzy mappings of one variable in a manner different from the usual one. In this paper, we define a differentiable fuzzy mapping of several variables in ways that parallel the definition, proposed by Goetschel and Voxman [1], for a fuzzy mapping of one variable, and then study some basic differentiability properties of fuzzy mappings from the standpoint of convex analysis.     

Hardness Hypotheses, Derandomization, and Circuit Complexity

We consider hypotheses about nondeterministic computation that have been studied in different contexts and shown to have interesting consequences:

Complexity, class dynamics, and distance learning

Classroom participants learn early on that each classroom has its own dynamic comprised of personalities, motivation levels, skills, and other variables. This paper explores features of complexity theory—nonlinearity and emergent self-organization—relevant to dynamics in physical or virtual classrooms. These central notions of complexity theory and their importance in composition classrooms help explain why students in virtual classrooms are often less successful than their physical classroom counterparts in negotiating the eddies of virtual interactions. The paper closes with a brief consideration of how teachers can interrogate all the elements of teaching and classroom context (whether physical or virtual) to influence the emergent dynamic of our classrooms.     

On the convexity and concavity of compliances

Compliances, which are measures of inverse stiffness, are sometimes used in the objective function, or as constraint functions, in structural optimization.It is known that if compliances are expressed as functions of thickness variablest _j, e.g. cross-sectional areas of truss elements, then these functions become convex.In this paper it is shown that if compliances are expressed as functions of reciprocal thickness variablesx _j = 1/t _j, then these functions become concave.Based on this result, it is further shown that a well-known structural optimization method is globally convergent when applied to minimum weight problems subject to constraints on compliances under multiple load cases.     

SOCIETAL SYSTEMS Planning,Policy and Complexity

The contribution of systems theory is reexamined from an organizational view. Its influence on artificial intelligence (and on computer science) is examined through the examples of analogical problem solving and cooperative distributed problem solving.