The distinction between computing answers and checking answers is fundamental to computational complexity theory, and is reflected in the relationship of NP to P. The plausibility of computing the answers to many memb...
详细信息
Estelle is a formal description technique, based on an extended state transition model, by the International Orangization for Standardization (ISO) for specifying protocols and services. The Estelle Development System...
详细信息
It is shown that if there is a polynomial-time algorithm that tests k(n)=O(log n) points for membership in a set A by making only k(n)-1 adaptive queries to an oracle set X, then A belongs to NP/poly intersection co-N...
详细信息
It is shown that if there is a polynomial-time algorithm that tests k(n)=O(log n) points for membership in a set A by making only k(n)-1 adaptive queries to an oracle set X, then A belongs to NP/poly intersection co-NP/poly (if k(n)=O(1) then A belong to P/poly). In particular, k(n)=O(log n) queries to an NP-complete set (k(n)=O(1) queries to an NP-hard set) are more powerful than k(n)-1 queries, unless the polynomial hierarchy collapses. Similarly, if there is a small circuit that tests k(n) points for membership in A by making only k(n)-1 adaptive queries to a set X, then there is a correspondingly small circuit that decides membership in A without an oracle. An investigation is conducted of the quantitatively stronger assumption that there is a polynomial-time algorithm that tests 2/sup k/ strings for membership in A by making only k queries to an oracle X, and qualitatively stronger conclusions about the structure of A are derived: A cannot be self-reducible unless A in P, and A cannot be NP-hard unless P=NP. Similar results hold for counting classes. In addition, relationships between bounded-query computations, lowness, and the p-degrees are investigated.< >
The MARUTI operating system is designed to support hard real-time applications on distributed computer systems while providing a fault-tolerant operation. Its design is object oriented, and the communication mechanism...
详细信息
The MARUTI operating system is designed to support hard real-time applications on distributed computer systems while providing a fault-tolerant operation. Its design is object oriented, and the communication mechanism allows transparent use of the resources of a distributed system. Fault tolerance is provided through a consistent set of mechanisms that support a number of policies. Most important, MARUTI supports guaranteed-service scheduling, by which jobs that are accepted by the system are guaranteed to meet the time constraints of the computation requests with a specified degree of fault tolerance. As a consequence, MARUTI applications can be executed in a predictable fashion. The development of current hard real-time applications requires that the analyst estimate the resource requirements for all parts of the computation and then makes sure that the resources are available to meet the time constraints, which tends to be a cumbersome process. As a part of the MARUTI system, a set of tools which support the hard real-time applications during various phases of their life cycle has been developed. The present version of MARUTI has been implemented as a prototype running on a Unix platform. Experiences with the development of this prototype are also presented.< >
作者：
A. BasuJ. AloimonosComputer Vision Laboratory
Center for Automation Research and Computer Science Department and Institute for Advanced Computer Studies University of Maryland College Park MD USA
The problem of finding a collision-free path connecting two points (start and goal) in the presence of obstacles, with constraints on the curvature of the path, is examined. This problem of curvature-constrained motio...
详细信息
The problem of finding a collision-free path connecting two points (start and goal) in the presence of obstacles, with constraints on the curvature of the path, is examined. This problem of curvature-constrained motion planning arises when, for example, a vehicle with constraints on its steering mechanism needs to be maneuvered through obstacles. Though no lower bound on the difficulty of the problem in 2-D is known, exact algorithms given to date for the reachability questions are exponential. It is shown that a variation of the problem is NP-hard. Notably, however, the same variation to polynomially solvable motion planning problems does not make them intractable. In addition, it is proven that epsilon -approximations to this problem cannot exist unless the underlying decision problem is polynomially solvable. An algorithm which is expected to find a desired path, when one exists, with a required probability is presented. Results indicate that a variable-size discretization is necessary for the task, linking the required probability to the size of the discretization locally.< >
作者：
J. AloimonosComputer Vision Laboratory
Center for Automation Research Institute for Advanced Computer Studies and Computer Science Department University of Maryland College Park MD USA
The traditional view of the problem of computer vision as a recovery problem is questioned, and the paradigm of purposive-qualitative vision is offered as an alternative. This paradigm considers vision as a general re...
详细信息
The traditional view of the problem of computer vision as a recovery problem is questioned, and the paradigm of purposive-qualitative vision is offered as an alternative. This paradigm considers vision as a general recognition problem (recognition of objects, patterns or situations). To demonstrate the usefulness of the framework, the design of the Medusa of CVL is described. It is noted that this machine can perform complex visual tasks without reconstructing the world. If it is provided with intentions, knowledge of the environment, and planning capabilities, it can perform highly sophisticated navigational tasks. It is explained why the traditional structure from motion problem cannot be solved in some cases and why there is reason to be pessimistic about the optimal performance of a structure from motion module. New directions for future research on this problem in the recovery paradigm, e.g., research on stability or robustness, are suggested.< >
This paper discusses studies on the performance of a parallel iterative algorithm implemented on an array of transputers connected in a mesh configuration. The iterative algorithm under consideration is the finite dif...
详细信息
This paper discusses studies on the performance of a parallel iterative algorithm implemented on an array of transputers connected in a mesh configuration. The iterative algorithm under consideration is the finite difference method for the solution of partial differential equations. Analytical expressions for the execution times of the various steps of the algorithm are derived by studying its computation and communication characteristics. These expressions are validated by comparing the theoretical results of the performance with the experimental values obtained on a transputer array. Then the analytical model is used to estimate the performance of the algorithm for varying number of transputers in the array and for varying grid sizes. An important objective of this paper is to study the influence of the convergence detection overhead on the performance of the algorithm. We present an approach to minimize the overhead. Convergence detection is one of the dominant factors that affects the performance of the algorithm, since it involves a substantial amount of computation and communication. In order to reduce this overhead, the proposed algorithm checks convergence once in every certain number of iterations, k c . The method of determining an optimal value of k c is given. Further, the time taken for convergence detection is estimated for the best case, worst case, and average case situations.
暂无评论