Search results for "computational complexity."
showing 10 items of 245 documents
The Reconstruction of Polyominoes from Approximately Orthogonal Projections
2001
The reconstruction of discrete two-dimensional pictures from their projection is one of the central problems in the areas of medical diagnostics, computer-aided tomography, pattern recognition, image processing, and data compression. In this note, we determine the computational complexity of the problem of reconstruction of polyominoes from their approximately orthogonal projections. We will prove that it is NP-complete if we reconstruct polyominoes, horizontal convex polyominoes and vertical convex polyominoes. Moreover we will give the polynomial algorithm for the reconstruction of hv-convex polyominoes that has time complexity O(m3n3).
Mappings of finite distortion: The sharp modulus of continuity
2003
We establish an essentially sharp modulus of continuity for mappings of subexponentially integrable distortion.
Verification of scope-dependent hierarchical state machines
2008
AbstractA hierarchical state machine (Hsm) is a finite state machine where a vertex can either expand to another hierarchical state machine (box) or be a basic vertex (node). Each node is labeled with atomic propositions. We study an extension of such model which allows atomic propositions to label also boxes (Shsm). We show that Shsms can be exponentially more succinct than Shsms and verification is in general harder by an exponential factor. We carefully establish the computational complexity of reachability, cycle detection, and model checking against general Ltl and Ctl specifications. We also discuss some natural and interesting restrictions of the considered problems for which we can …
Robust adaptive algorithm with low computational cost
2006
An adaptive algorithm, which is robust to impulsive noise, is proposed. The cost function underlying this algorithm contains a parameter that controls the immunity to impulsive noise and can be easily adapted. Moreover, weight updating involves a nonlinear function, which recently has been shown to have an efficient hardware implementation. The proposed adaptive algorithm has been successfully tested in terms of accuracy and convergence on a system-identification simulation.
LCRT: A ToA Based Mobile Terminal Localization Algorithm in NLOS Environment
2009
©2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. Article also available from publisher: http://dx.doi.org/10.1109/VETECS.2009.5073644 Non line-of-sight (NLOS) propagation in range measurement is a key problem for mobile terminal localization. This paper proposes a low computational residual test (LCRT) algorithm that can identify the number of line-of-sight (LOS) transmissions and reduce the computational com…
Non-intersecting Complexity
2006
A new complexity measure for Boolean functions is introduced in this article. It has a link to the query algorithms: it stands between both polynomial degree and non-deterministic complexity on one hand and still is a lower bound for deterministic complexity. Some inequalities and counterexamples are presented and usage in symmetrisation polynomials is considered.
No-Forcing and No-Matching Theorems for Classical Probability Applied to Quantum Mechanics
2013
Correlations of spins in a system of entangled particles are inconsistent with Kolmogorov's probability theory (KPT), provided the system is assumed to be non-contextual. In the Alice-Bob EPR paradigm, non-contextuality means that the identity of Alice's spin (i.e., the probability space on which it is defined as a random variable) is determined only by the axis \alphai chosen by Alice, irrespective of Bob's axis \betaj (and vice versa). Here, we study contextual KPT models, with two properties: (1) Alice's and Bob's spins are identified as Aij and Bij, even though their distributions are determined by, respectively, \alphai alone and \betaj alone, in accordance with the no-signaling requir…
Superresolved imaging of remote moving targets.
2006
We present a superresolving approach that allows one to exceed the diffraction limit and recover highly resolved contours of moving targets from a sequence of low-resolution images. The presented approach is suitable for remote sensing applications. The resolution decoding algorithm that is used to recover the high-resolution features of the target can be run partially via optical means and that way can be used to reduce the required computational complexity.
Optimal Impulse Control Problems and Linear Programming
2009
Optimal impulse control problems are, in general, difficult to solve. A current research goal is to isolate those problems that lead to tractable solutions. In this paper, we identify a special class of optimal impulse control problems which are easy to solve. Easy to solve means that solution algorithms are polynomial in time and therefore suitable to the on-line implementation in real-time problems. We do this by using a paradigm borrowed from the Operations Research field. As main result, we present a solution algorithm that converges to the exact solution in polynomial time. Our approach consists in approximating the optimal impulse control problem via a binary linear programming proble…
The Crane Beach Conjecture
2002
A language L over an alphabet A is said to have a neutral letter if there is a letter e/spl isin/A such that inserting or deleting e's from any word in A* does not change its membership (or non-membership) in L. The presence of a neutral letter affects the definability of a language in first-order logic. It was conjectured that it renders all numerical predicates apart from the order predicate useless, i.e., that if a language L with a neutral letter is not definable in first-order logic with linear order then it is not definable in first-order. Logic with any set /spl Nscr/ of numerical predicates. We investigate this conjecture in detail, showing that it fails already for /spl Nscr/={+, *…