Search

Network virtualization (NV) is widely accepted as one enabling technology for future network, which enables multiple virtual networks (VNs) with different paradigms and protocols to coexist on the shared substrate network (SN). One key challenge in NV is VN embedding (VNE), which maps a VN onto the shared SN. Since VNE is NP-hard, existing efforts mainly focus on proposing heuristic algorithms that try to achieve feasible VNE in reasonable time, consequently the resulted embedding is not optimal. To tackle this difficulty, we propose a candidate assisted (CAN-A) optimal VNE algorithm with lower computational complexity. The key idea of the CAN-A algorithm lies in constructing the candidate substrate node subset and the candidate substrate path subset before embedding. This reduces the mapping execution time substantially without performance loss. In the following embedding, four types of node and link constraints are considered in the CAN-A algorithm, making it more applicable to realistic networks. Simulation results show that the execution time of CAN-A is hugely cut down compared with pure VNE-MIP algorithm. CAN-A also outperforms the typical heuristic algorithms in terms of other performance indices, such as the average VN request acceptance ratio and the average virtual link propagation delay.

This paper focuses on the classification of faults in an electromechanical switch machine, which is an equipment used for handling railroad switches. In this paper, we introduce the use of Set-Membership concept, derived from the adaptive filter theory, into the training procedure of type-1 and singleton/non-singleton fuzzy logic systems, in order to reduce computational complexity and to increase convergence speed. We also present different criteria for using along with Set-Membership. Furthermore, we discuss the usefulness of delta rule delta, local Lipschitz estimation, variable step size, and variable step size adaptive techniques to yield additional improvement in terms of computational complexity reduction and convergence speed. Based on data set provided by a Brazilian railway company, which covers the four possible faults in a switch machine, we present performance analysis in terms of classification ratio, convergence speed, and computational complexity reduction. The reported results show that the proposed models result in improved convergence speed, slightly higher classification ratio, and remarkable computation complexity reduction when we limit the number of epochs for training, which may be required due to real-time constraint or low computational resource availability.

Computing geodesic distances on 2-manifold meshes is a fundamental problem in computational geometry. To date, two notable classes of exact algorithms, namely, the Mitchell–Mount–Papadimitriou (MMP) algorithm and the Chen–Han (CH) algorithm, have been widely studied. For an arbitrary triangle mesh with n vertices, these algorithms have space complexity of O ( n 2 ) . In this paper, we prove that both algorithms have Θ ( n 1.5 ) space complexity on a completely regular triangulation (i.e., all triangles are equilateral).

This paper proposes a fast recursive algorithm for Group-wise Space-Time Block Code (G-STBC), which takes full advantage of the Alamouti structure in the equivalent channel matrix to reduce the computational complexity. With respect to the existing efficient algorithms for G-STBC, the proposed algorithm achieves better performance and usually requires less computational complexity., Comment: TCOM

The partner units problem (PUP) is an acknowledged hard benchmark problem for the Logic Programming community with various industrial application fields like surveillance, electrical engineering, computer networks or railway safety systems. Although it is already known for a while that the PUP is NP-complete in its general form, complexity for subproblems reflecting the real problems in industrial fields remained widely unclear so far. In this article we provide all missing complexity results. For the subclass of the PUP that belongs to the complexity class P we present a polynomial-time algorithm and give in-depth algorithmic complexity results. We prove that the Partner Units Problem (PUP) is NP-complete for various important subclasses.We present a poly-time algorithm for a PUP subclass which lies in P.We give in-depth worst-case complexity results for the presented algorithm.

We analyze the complexity of the LLL algorithm, invented by Lenstra, Lenstra, and Lovasz as a a well-known lattice reduction (LR) algorithm which is previously known as having the complexity of O(N 4 logB) multiplications (or, O(N 5 (logB) 2 ) bit operations) for a lattice basis matrix H(∈ R M×N ) where B is the maximum value among the squared norm of columns of H. This implies that the complexity of the lattice reduction algorithm depends only on the matrix size and the lattice basis norm. However, the matrix structures (i.e., the correlation among the columns) of a given lattice matrix, which is usually measured by its condition number or determinant, can affect the computational complexity of the LR algorithm. In this paper, to see how the matrix structures can affect the LLL algorithm’s complexity, we derive a more tight upper bound on the complexity of LLL algorithm in terms of the condition number and determinant of a given lattice matrix. We also analyze the complexities of the LLL updating/downdating schemes using the proposed upper bound.

Control of hybrid systems faces computational complexity as a main challenging problem. To reduce the computational burden, multi-parametric programming has been proposed to obtain the explicit solution of the optimal control problems for some classes of hybrid systems. This strategy provides the solution as a function of the state variables which can be obtained in an off-line fashion. A shortcoming of this technique is that the complexity of the explicit solution is again prohibitive for large problems. The main contribution of this paper is the introduction of an approximation algorithm for solving a general class of multi-parametric mixed-integer linear programming (mp-MILP) problems. The algorithm selects those binary sequences that make significant improvement in the objective function, if considered. It is shown that significant reduction in computational complexity can be achieved by introducing adjustable level of suboptimality. A family of suboptimal controllers is obtained by the proposed approach for which the level of error and complexity can be adjusted by a tuning parameter. It is shown that no part of the parameter space is disregarded during the approximation. Also it is proved that the error in the achieved approximate solutions is a monotonically increasing function of the tuning parameter. Assuming that the closed-loop stability is ensured by including some constraints in the formulation of hybrid control, it will be preserved by the suboptimal low-complexity controllers. Illustrative examples are presented to demonstrate the achieved complexity reduction.

Minimal solutions play a crucial role in describing all solutions of relational equations. For this reason, the problem of computing minimal solutions has for long been examined. The literature contains several algorithms for computing minimal solutions. Recently, contributions regarding computational complexity of the problem itself appeared. The complexity aspect is clearly of fundamental importance. However, the existing results contain serious flaws. In this paper, we inspect the existing contributions, clarify the flaws, examine the problem of complexity of computing minimal solutions, prove that there is no efficient algorithm computing all minimal solutions, and discuss further ramifications of our observations.

We revisit the classical resource allocation problem with general convex objective functions, subject to an integer knapsack constraint. This class of problems is fundamental in discrete optimization and arises in a wide variety of applications. In this paper, we propose a novel polynomial-time divide-and-conquer algorithm (called the multi-phase algorithm) and prove that it has a computational complexity of O ( n log ? n log ? N ) , which outperforms the best known polynomial-time algorithm with O ( n ( log ? N ) 2 ) .

This paper considers the computational complexity of the design of voting rules, which is formulated by simple games. We prove that it is an NP-complete problem to decide whether a given simple game is stable, or not.

We investigate the complexity of primal logic with disjunction according to the Kripke semantics as defined in 1] and the quasi-boolean semantics as defined in 2]. We show that the validity problem is coNP -complete, even for variable-free sequents. For quasi-boolean semantics, the satisfiability problem is shown to be NP -complete (even for variable-free sequents), whereas for Kripke semantics it is shown to be coNP -complete for variable-free sequents and ? 2 p -complete in the general case. The evaluation problem is in P for quasi-boolean semantics, but coNP -complete for Kripke semantics. We investigate the complexity of primal logic with disjunction.We show that different semantics yield to very different complexities.We improve the known complexity result for the validity problem.We prove complexity results for the satisfiability problem.We prove complexity results for the formula evaluation problem.

The k-Clique problem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most well-known NP-complete and W[1]-complete problems. Moreover, its average-case complexity analysis has created a long thread of research already since the 1970s. Here, we continue this line of research by studying the dependence of the average-case complexity of the k-Clique problem on the parameter k. To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that k-Clique admits both analogues for Erd\H{o}s-R\'{e}nyi random graphs of arbitrary density. We also show that k-Clique is unlikely to admit neither of these analogs for some specific computable input distribution.

We study two generalizations of the classical problem of fast exponentiation, namely: Bellman’s problem on computational complexity (the minimal number of multiplications) based only on the variables of a normalized monomial of m variables and Knuth’s problem on the complexity of the simultaneous calculation of a system of m powers of one variable. Some results for these problems are surveyed in the paper. The asymptotic complexity bounds for Bellman’s and Knuth’s problems are improved for the cases when m and complexity behave similarly (have the same growth order). The upper and lower complexity bounds for almost all sets of exponents for Bellman’s and Knuth’s problems that are established provide the complexity growth asymptotics for a wide range of relations between parameters (the number of variables or the computed exponents, the maximal power, and the product of all powers). Moreover, they guarantee the ratio of the upper and lower bounds not exceeding 5/3 for all relations between the parameters.

This paper dose the theoretical analysis for solving the algorithm complexity of a neural network using rational cubic spline weight functions with linear denominator. It concludes that the time complexity of the training algorithm has linear relations with the neural network’s input dimensions, output dimensions as well as the number of samples.

This paper presents a detailed study of the graph based algorithm used to generate geometric moment invariant functions. The graph based algorithm has been found to suffer from high computational complexity. One major cause of this problem is that the algorithm generates too many graphs that produce zero moment invariant functions. Hence, we propose an algorithm to determine and eliminate the zero moment invariant generating graphs and thereby generate non-zero moment invariant functions with reduced computational complexity. The correctness of the algorithm has been verified and discussed with suitable induction proofs and sample graphs. Asymptotic analysis has been presented to clearly illustrate the reduction in computational complexity achieved by the proposed algorithm. It has been found and illustrated with examples that the computational time for identifying non-zero invariants could be largely reduced with the help of our proposed algorithm.

In modern years, there has been growing importance in the design, analysis and to resolve extremely complex problems. Because of the complexity of problem variants and the difficult nature of the problems they deal with, it is arguably impracticable in the majority time to build appropriate guarantees about the number of fitness evaluations needed for an algorithm to and an optimal solution. In such situations, heuristic algorithms can solve approximate solutions; however suitable time and space complication take part an important role. In present, all recognized algorithms for NP-complete problems are requiring time that's exponential within the problem size. The acknowledged NP-hardness results imply that for several combinatorial optimization problems there are no efficient algorithms that realize a best resolution, or maybe a close to best resolution, on each instance. The study Computational Complexity Analysis of Selective Breeding algorithm involves both an algorithmic issue and a theoretical challenge and the excellence of a heuristic.

A novel effective decoding algorithm for LDPC codes is proposed, which significantly simplifies the check node update computation of the Sum-Product Algorithm (SPA). Through simplified Taylor Series algorithm, It made index operation for multiplication and addition operations in the check node update. Compared with the existing approximations, the proposed method is less computational complexity than SPA algorithm, simulation results show that the proposed algorithm can achieve an error performance better than the Min-sum (MS) algorithm with small increase computational complexity.

In this study, the problem of low complexity multiple-input-multiple-out signal detection based on belief propagation (BP) is addressed. The authors propose an edge selection approach that works on factor graph model to cut down the number of circles and high complexity of standard BP algorithm. The message passing from factor nodes to variable nodes is updated by only partial edges, and the mean feedback method is designed to compensate the information loss brought by the edge selection. Both binary and high-order modulations are considered, and the scheme of mapping between bit soft output and modulation symbols when computing the feedback information is discussed. In addition, a minimum mean-square error filter initialised algorithm is proposed, in which the initial message of BP detection is exploited. Both binary and high-order modulations are discussed as well when the authors design this initial message. Simulation results along with convergence and complexity analyses verify that the proposed edge selection approach can achieve good performance with low complexity, and significantly outperform the existing methods with comparative complexity. Moreover, our approach has asymptotic optimality and is a self-adapting scheme, which can achieve the trade-off between performance and complexity by varying the number of selected edges.

In computer science, the theory of computational complexity was developed to evaluate the hardness of problems, regarding the number of steps to obtain a solution; for the basic results of that theory we refer to [147]. The model of computations, used in that theory, is either the Turing machine or any other equivalent model. The input and output of the Turing machine should be encoded as finite strings of bits. Such an encoding can be used to represent the objects of discrete nature, and the theory of computational complexity is favorable, e.g., to the investigation of problems of single-objective combinatorial optimization [150, 151]. However, the Turing machine model is not suitable for the algorithms using real numbers. Therefore alternative complexity theories have been developed for the investigation of problems of continuous nature. For the fundamentals of the complexity of real number algorithms we refer to [19, 218], and for the complexity of problems of mathematical programming to [143, 150, 151].

We study the complexity of Bongartz's algorithm for determining a maximal common direct summand of a pair of modules M, N over k-algebra Λ; in particular, we estimate its pessimistic computational complexity Orm6n2n + m log n, where m = dimkM ≤ n = dimkN and r is a number of common indecomposable direct summands of M and N. We improve the algorithm to another one of complexity Orm4n2n+m log m and we show that it applies to the isomorphism problem having at least an exponential complexity in a direct approach. Moreover, we discuss a performance of both algorithms in practice and show that the “average” complexity is much lower, especially for the improved one which becomes a part of QPA package for GAP computer algebra system.

Non-orthogonal multiple access is one of the key techniques developed for the future 5G communication systems among which, the recent proposed sparse code multiple access (SCMA) has attracted a lots of researchers' interests. By exploring the shaping gain of the multi-dimensional complex codewords, SCMA is shown to have a better performance compared with some other non-orthogonal schemes such as low density signature (LDS). However, although the sparsity of the codewords makes the near optimal message passing algorithm (MPA) possible, the decoding complexity is still very high. In this paper, we propose a low complexity decoding algorithm based on list sphere decoding. Complexity analysis and simulation results show that the proposed algorithm can reduce the computational complexity substantially while achieve the near maximum likelihood (ML) performance.

A novel algorithm is proposed for blind estimation of the spreading sequence in direct-sequence spread-spectrum (DSSS) communication systems. This algorithm is based on the maximum likelihood decision rule. Due to high computational complexity, the maximum likelihood method is feasible only for spreading sequence with very short periods. The novel algorithm has two steps for estimation. At first, a prior estimation of the spreading sequence is obtained via a simple algorithm which has a very low computational complexity. In the second step, using the prior estimation and the maximum likelihood decision rule, the estimation accuracy increases greatly. The proposed algorithm can reach the performance of the eigen value decomposition (EVD) method with low computational complexity.

Adaptive filters for Volterra system identification must deal with two difficulties: large filter length M (resulting in high computational complexity and low convergence rate) and high correlation in the input sequence. The second problem is minimized by using the recursive least-squares algorithm (RLS), however, its large computation complexity (O(M2)) might be prohibitive in some applications. We propose here a low-complexity RLS algorithm, based on the dichotomous coordinate descent algorithm (DCD), showing that in some situations the computational complexity is reduced to O(M). The new algorithm is compared to the standard RLS, normalized least-mean squares (NLMS) and affine projections (AP) algorithms.

Binary sequences with high linear complexity are of interest in cryptography. The linear complexity should remain high even when a small number of changes are made to the sequence. The error linear complexity spectrum of a sequence reveals how the linear complexity of the sequence varies as an increasing number of the bits of the sequence are changed. We present an algorithm which computes the error linear complexity for binary sequences of period /spl lscr/=2/sup n/ using O(/spl lscr/(log/spl lscr/)/sup 2/) bit operations. The algorithm generalizes both the Games-Chan (1983) and Stamp-Martin (1993) algorithms, which compute the linear complexity and the k-error linear complexity of a binary sequence of period /spl lscr/=2/sup n/, respectively. We also discuss an application of an extension of our algorithm to decoding a class of linear subcodes of Reed-Muller codes.

For linear systems with integer inputs, the model predictive control problem with output reference tracking is formulated as an integer least-squares (ILS) problem. The ILS problem is solved using a modified sphere decoding algorithm, which is a particular branch-and-bound method. To reduce the computational complexity of the sphere decoder, a reduction algorithm is added as a preprocessing stage to reshape the search space in which the integer solution lies. The computational complexity of the proposed algorithm is modest, enabling its implementation in a real-time system even when considering long prediction horizons. A variable-speed drive system with a three-level voltage source inverter serves as an illustrative example to demonstrate the effectiveness of the proposed algorithm. acceptedVersion

There are two main families of algorithms that tackle the problem of sparse system identification: the proportionate family and the one that employs sparsity-promoting penalty functions. Recently, a new approach was proposed with the l0-IPAPA algorithm, which combines proportionate updates with sparsity-promoting penalties. This paper proposes some modifications to the l0-IPAPA algorithm in order to decrease its computational complexity while preserving its good convergence properties. Among these modifications, the inclusion of a data-selection mechanism provides promising results. Some enlightening simulation results are provided in order to verify and compare the performance of the proposed algorithms.

The exact average complexity analysis of the basic sphere decoder for general space-time codes applied to multiple-input multiple-output MIMO wireless channel is known to be difficult. In this work, we shed the light on the computational complexity of sphere decoding for the quasi-static, lattice space-time LAST coded MIMO channel. Specifically, we drive an upper bound of the tail distribution of the decoder's computational complexity. We show that when the computational complexity exceeds a certain limit, this upper bound becomes dominated by the outage probability achieved by LAST coding and sphere decoding schemes. We then calculate the minimum average computational complexity that is required by the decoder to achieve near optimal performance in terms of the system parameters. Our results indicate that there exists a cut-off rate multiplexing gain for which the average complexity remains bounded.Copyright © 2012 John Wiley & Sons, Ltd.

The correct computation of orbits of discrete dynamical systems on the interval is considered. Therefore, an arbitrary-precision floating-point approach based on automatic error analysis is chosen and a general algorithm is presented. The correctness of the algorithm is shown and the computational complexity is analyzed. There are two main results. First, the computational complexity measure considered here is related to the Lyapunov exponent of the dynamical system under consideration. Second, the presented algorithm is optimal with regard to that complexity measure.

In this letter, we introduce a fast and computationally efficient iterative algorithm for joint zero diagonalization of a set of complex-valued target matrices. The proposed algorithm is actually a low complexity version of FJZD algorithm, it has a computational complexity of O(K N2), where K and N are the number and dimension of the target matrices respectively. Moreover, the proposed algorithm is superior to FJZD in terms of interference to signal ratio. Simulation results demonstrate the good performance of the proposed algorithm.

Smoothed analysis is a new way of analyzing algorithms introduced by Spielman and Teng (J. ACM, 2004). Classical methods like worst-case or average-case analysis have accompanying complexity classes, like P and Avg−P, respectively. While worst-case or average-case analysis give us a means to talk about the running time of a particular algorithm, complexity classes allows us to talk about the inherent difficulty of problems. Smoothed analysis is a hybrid of worst-case and average-case analysis and compensates some of their drawbacks. Despite its success for the analysis of single algorithms and problems, there is no embedding of smoothed analysis into computational complexity theory, which is necessary to classify problems according to their intrinsic difficulty. We propose a framework for smoothed complexity theory, define the relevant classes, and prove some first results.

One of the possible realizations of the branch-and-bound method on multiprocessor systems with distributed memory, the front-end algorithm is addressed. The complexity of the front-end algorithm is studied for a family of Boolean knapsack problems with one constraint under the assumption that the number of processors is not limited. Formulas for the order of complexity growth with an increase in dimension of the problems from the addressed family are obtained for the front-end algorithm. The asymptotic acceleration behavior and efficiency of resource use with an increase in the number of variables are studied.

The study of simple stochastic games (SSGs) was initiated by Condon for analyzing the computational power of randomized space-bounded alternating Turing machines. The game is played by two players, MAX and MIN, on a directed multigraph, and when the play terminates at a sink vertex s, MAX wins from MIN a payoff p(s)@?[0,1]. Condon proved that the problem SSG-VALUE-given a SSG, determine whether the expected payoff won by MAX is greater than 1/2 when both players use their optimal strategies-is in [email protected]?coNP. However, the exact complexity of this problem remains open, as it is not known whether the problem is in P or is hard for some natural complexity class. In this paper, we study the computational complexity of a strategy improvement algorithm by Hoffman and Karp for this problem. The Hoffman-Karp algorithm converges to optimal strategies of a given SSG, but no non-trivial bounds were previously known on its running time. We prove a bound of O(2^n/n) on the convergence time of the Hoffman-Karp algorithm, and a bound of O(2^0^.^7^8^n) on a randomized variant. These are the first non-trivial upper bounds on the convergence time of these strategy improvement algorithms.

We initiate a parameterized complexity study of the NP-hard problem to tile a positive integer matrix with rectangles, keeping the number of tiles and their maximum weight small. We show that the problem remains NP-hard even for binary matrices only using 1×1 and 2×2-squares as tiles and provide insight into the influence of naturally occurring parameters on the problem’s complexity.

In this paper, we proposed the low computational complexity soft-decision e-BCH decoding algorithm based on the Chase algorithm. In order to make the test patterns, it is necessary to re-order the least reliable received symbols. In the process of ordering and finding optimal decoding symbols, high computational complexity is required. Therefore, this paper proposes the method of low computational complexity algorithm for soft-decision e-BCH decoding process.

In this paper, we propose an adaptive de-interlacing algorithm that is based on the degree of local complexity. The conventional intra field de-interlacing algorithms show the different performance according to the ways which find the edge direction. Furthermore, FDD (Fine Directional De-interlacing) algorithm has the better performance than other algorithms but the computational complexity of FDD algorithm is too high. In order to alleviate these problems, the proposed algorithm selects the most efficient de-interacing algorithm among LA (Line Average), MELA (Modified Edge-based Line Average), and LCID (Low-Complexity Interpolation Method for De-interlacing) algorithms which have low complexity and good performance. The proposed algorithm is trained by the DoLC (Degree of Local Complexity) for selection of the algorithms mentioned above. Simulation results show that the proposed algorithm not only has the low complexity but also performs better objective and subjective image quality performances compared with the conventional intra-field methods.

We preliminarily recap what is meant by complexity and non-Turing computation, by way of explanation of our title, 'Computational Complexity in Non-Turing Models of Computation'. Based on investigation of a motivating example, we argue that traditional complexity theory does not adequately capture the true complexity of certain non-Turing computers, and, hence, that an extension of the theory is needed in order to accommodate such machines. We propose a framework of complexity that is not computation-model-dependent-that, rather, is extensible so as to accommodate diverse computational models-, and that allows meaningful comparison of computers' respective complexities, whether or not the comparison be with respect to different resources, and whether or not the computers be instances of different models of computation. Whilst, we suggest, complexity theory is-without some modification-of limited applicability to certain non-standard models, we hope that the ideas described here go some way to showing how such modification can be made, and that members of the non-Turing-computation community-not least participants of Quantum Physics and Logic/Development of Computational Models 2008-find these ideas both useful and interesting.

We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.

This paper presents a novel real-time algorithm for reducing and dynamically controlling the computational complexity of an H.264 video encoder implemented in software. A fast Mode Decision algorithm, based on a Pareto optimal MacroBlock classification scheme, is combined with a Dynamic Complexity Control algorithm that adjusts the MB Class decisions such that a constant frame rate is achieved. The average coding efficiency of the proposed algorithm was found to be similar to that of conventional encoding operating at half the frame rate. The proposed algorithm was found to provide lower average bit rate and distortion than Static Complexity Scaling. University College Dublin

For range based positioning the least square (LS) criterion and its produced solution exhibit superb estimation performance, but generally at a very high computational complexity. In this letter we consider the issue how to approach such LS solution in estimation performance at low computational complexity. We propose a novel algorithm that is based on the equations linearized from range measurement equations and implements a weighted least square criterion in a computationally efficient way. The proposed algorithm involves a quadratic equation linking the linearization-caused extra variable and the position to be estimated, thus results in a closed form solution.We analyze and simulate its estimation performance, and evidently show that the proposed algorithm can very closely approach the LS solution in estimation performance at a significantly low computational complexity.

This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N (input scale of problem). To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method: 1) to decrease computation in enumeration; 2) to efficiently obtain computational complexity for any N-vehicle case; 3) to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.

Factorization is notoriously difficult. Though the problem is not known to be NP-hard, neither efficient, algorithmic solution nor technologically practicable, quantum-computer solution has been found. This apparent complexity, which renders infeasible the factorization of sufficiently large values, makes secure the RSA cryptographic system. Given the lack of a practicable factorization system from algorithmic or quantum-computing models, we ask whether efficient solution exists elsewhere; this motivates the analogue system presented here. The system’s complexity is prohibitive of its factorizing arbitrary, natural numbers, though the problem is mitigated when factorizing n = pq for primes p and q of similar size, and, hence, when factorizing RSA keys. Ultimately, though, we argue that the system’s polynomial time and space complexities are testament not to its power, but to the inadequacy of traditional, Turing-machine-based complexity theory; we propose precision complexity (defined in our previous paper4)) as a more relevant measure, and advocate, more generally, non-standard complexity analyses for non-standard computers.

A reduction operation and the design of a reduced wise algorithm over a set of known algorithms of unvarying complexity are addressed. A direct convolution algorithm and the best-known algorithms based on fast discrete orthogonal transforms (with Cooley-Tukey and Good-Thomas decompositions and the Rader algorithm for short lengths) are used as a support set of known algorithms. It is shown that their combined use in the reduced wise algorithm decreases the computational complexity of the resulting convolution algorithm as compared to that of the algorithms in the support set.

Sign-selection uses a set of subcarrier signs to reduce the peak-to-average power ratio (PAR) of orthogonal-frequency-division multiplexing (OFDM). However, the computational complexity (worst-case) is exponential in N, the number of subcarriers. Suboptimal sign-selection algorithms, achieving different tradeoffs between the PAR reduction and complexity, have thus been developed. For example, the derandomization method achieves high PAR reduction of O(log N) with relatively high complexity of O(N2). On the other hand, selective mapping (SLM) and partial transmit sequences (PTS) sacrifice the achievable PAR reduction for lower complexity. In this paper, we develop two new cross-entropy (CE)-based sign-selection algorithms. Our algorithms simultaneously updates the probabilities of the signs of all subcarriers. The first algorithm obtains a PAR lower than the above methods with a complexity level of O(N2). However, if the number of iterations is fixed, this algorithm obtains the same PAR reduction as derandomization, but with O(N log N) complexity. Practical PAR reduction algorithms require that the extra cost of PAR reduction must be small. Therefore, we propose the second algorithm, which adaptively adjusts the probability of "elite" samples, and stops whenever a PAR threshold is reached. Our second algorithm achieves up to 95 % complexity savings over the first (with only a 0.4-dB PAR reduction loss). The simulations confirm the complexity advantages of the proposed algorithms compared to SLM and derandomization.

The sphere decoding algorithm is widely used for maximum likelihood (ML) detection in multiple-input multiple-output (MIMO) systems, wherein the K-best sphere decoding algorithm is well appreciated for its fixed complexity and throughput. However, to achieve near-ML performance, K needs to be sufficiently large, which leads to large computational complexity in path expansion, sorting, and path updating. In this paper, we propose two efficient decoding schemes that can significantly reduce the average K value and thus the total computational complexity without sacrificing performance. We further present a novel sorting architecture that can save about 70% of the sorting operations compared with the bubble sort method. It is estimated that, for the example 4×4 64 QAM MIMO system, 68% of the total computational complexity can be saved over the conventional design by applying all the proposed techniques.