A central problem in the study of complexity is the measure of nonuniform complexity classes. BPPP/poly has been proved by Aldman, and EXPSPACEP/poly by Kannan. We propose the definition of approximate acceptance with...A central problem in the study of complexity is the measure of nonuniform complexity classes. BPPP/poly has been proved by Aldman, and EXPSPACEP/poly by Kannan. We propose the definition of approximate acceptance with which we discuss the nonuniform complexity of the K sized complete subgraph problem. The method of modal theory is used and the K sized complete subgraph problemP/poly, co NPP/poly and NPP/poly is proved. This paper solves the Karp Lipton′s open problem: “NPP/poly?”展开更多
Aim To present a quantitative method for structural complexity analysis and evaluation of information systems. Methods Based on Petri net modeling and analysis techniques and with the aid of mathematical tools in ge...Aim To present a quantitative method for structural complexity analysis and evaluation of information systems. Methods Based on Petri net modeling and analysis techniques and with the aid of mathematical tools in general net theory(GNT), a quantitative method for structure description and analysis of information systems was introduced. Results The structural complexity index and two related factors, i.e. element complexity factor and connection complexity factor were defined, and the relations between them and the parameters of the Petri net based model of the system were derived. Application example was presented. Conclusion The proposed method provides a theoretical basis for quantitative analysis and evaluation of the structural complexity and can be applied in the general planning and design processes of the information systems.展开更多
For reducing the computational complexity of the problem of joint transmit and receive antenna selection in Multiple-Input-Multiple-Output (MIMO) systems, we present a concise joint transmit/receive antenna selection ...For reducing the computational complexity of the problem of joint transmit and receive antenna selection in Multiple-Input-Multiple-Output (MIMO) systems, we present a concise joint transmit/receive antenna selection algorithm. Using a novel partition of the channel matrix, we drive a concise formula. This formula enables us to augment the channel matrix in such a way that the computational complexity of the greedy Joint Transmit/Receive Antenna Selection (JTRAS) algorithm is reduced by a factor of 4n L , where n L is the number of selected antennas. A decoupled version of the proposed algorithm is also proposed to further improve the efficiency of the JTRAS algorithm, with some capacity degradation as a tradeoff. The computational complexity and the performance of the proposed approaches are evaluated mathematically and verified by computer simulations. The results have shown that the proposed joint antenna selection algorithm maintains the capacity perormance of the JTRAS algorithm while its computational complexity is only 1/4n L of that of the JTRAS algorithm. The decoupled version of the proposed algorithm further reduces the computational complexity of the joint antenna selection and has better performance than other decoupling-based algorithms when the selected antenna subset is small as compared to the total number of antennas.展开更多
Along with the rapid development of air traffic, the contradiction between conventional air traffic management(ATM)and the increasingly complex air traffic situations is more severe,which essentially reduces the opera...Along with the rapid development of air traffic, the contradiction between conventional air traffic management(ATM)and the increasingly complex air traffic situations is more severe,which essentially reduces the operational efficiency of air transport systems. Thus,objectively measuring the air traffic situation complexity becomes a concern in the field of ATM. Most existing studies focus on air traffic complexity assessment,and rarely on the scientific guidance of complex traffic situations. According to the projected time of aircraft arriving at the target sector boundary,we formulated two control strategies to reduce the air traffic complexity. The strategy of entry time optimization was applied to the controllable flights in the adjacent upstream sectors. In contrast,the strategy of flying dynamic speed optimization was applied to the flights in the target sector. During the process of solving complexity control models,we introduced a physical programming method. We transformed the multi-objective optimization problem involving complexity and delay to single-objective optimization problems by designing different preference function. Actual data validated the two complexity control strategies can eliminate the high-complexity situations in reality. The control strategy based on the entry time optimization was more efficient than that based on the speed dynamic optimization. A basic framework for studying air traffic complexity management was preliminarily established. Our findings will help the implementation of a complexity-based ATM.展开更多
This paper presents an improved Voice Activity Detection （VAD） algorithm which uses the Signal-to-Noise Ratio （SNR） measure. We assume that noise Power Spectral Density （PSD） in each spectral bin follows a Rayle...This paper presents an improved Voice Activity Detection （VAD） algorithm which uses the Signal-to-Noise Ratio （SNR） measure. We assume that noise Power Spectral Density （PSD） in each spectral bin follows a Rayleigh distribution. Rayleigh distributions with its asymmetric tail characteristics give a better description of the noise PSD distribution than Gaussian distribution. Under this asstlmption, a new threshold updating expression is derived. Since the analytical integral of the false alarm probability, the threshold updating expression can be represented without the inverse complementary error function and low computational complexity is achieved in our system. Experimental results show that the proposed VAD outperforms or at least is comparable with the VAD scheme presented by Davis under several noise environments and has a lower computational complexity.展开更多
In this paper, the complexity of intra coding is first analyzed so as to achieve a weight of complexity measurement for each intra mode. Then, a new complexity scalable control algorithm for intra coding in H. 264 is ...In this paper, the complexity of intra coding is first analyzed so as to achieve a weight of complexity measurement for each intra mode. Then, a new complexity scalable control algorithm for intra coding in H. 264 is proposed, based on the rearrangement of the order of candidate modes and an efficient complexity allocation and control （CAAC） scheme at the macroblock （MB） level. The candidate modes of each MB are rearranged according to the local-edge information. Experimental results show that our proposed algorithm can make an appropriate cut-off point of the candidate modes sequence adaptively according to the current energy condition of a mobile device, so as to adjust the complexity at any level while maximizing the video quality, which can prolong the operational lifetime of the battery with minimum degradation in video quality.展开更多
Software protection technology has been universally emphasized, with the development of reverse engineering and static analysis techniques. So, it is important to research how to quantitatively evaluate the security o...Software protection technology has been universally emphasized, with the development of reverse engineering and static analysis techniques. So, it is important to research how to quantitatively evaluate the security of the protected software. However, there are some researchers evaluating the security of the proposed protect techniques directly by the traditional complexity metrics, which is not suffident. In order to better reflect security from software complexity, a multi-factor complexity metric based on control flow graph （CFG） is proposed, and the corresponding calculating procedures are presented in detail. Moreover, complexity density models are constructed to indicate the strength of software resisting reverse engineering and code analysis. Instance analysis shows that the proposed method is simple and practical, and can more objectively reflect software security from the perspective of the complexity.展开更多
A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictio...A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictions for good quality of service. Firstly, a set of reachable paths to each intermediate node from the source node and the sink node based on adjacent matrix transformation are calculated respectively. Then a temporal optimal path is selected by adopting the proposed heuristic method according to a non-linear cost function. When the total number of the accumulated nodes by bidirectional searching reaches n-2, the paths from two directions to an intermediate node should be combined and several paths via different nodes from the source node to the sink node can be obtained, then an optimal path in the whole set of paths can be taken as the output route. Some simulation examples are included to show the effectiveness and efficiency of the proposed method. In addition, the proposed algorithm can be implemented with parallel computation and thus, the new algorithm has better performance in time complexity than other algorithms. Mathematical analysis indicates that the maximum complexity in time, based on parallel computation, is the same as the polynomial complexity of O(kn2-3kn+k), and some simulation results are shown to support this analysis.展开更多
The approach of nonconforming finite element method admits users to solve the partial differential equations with lower complexity,but the accuracy is usually low.In this paper,we present a family of highaccuracy nonc...The approach of nonconforming finite element method admits users to solve the partial differential equations with lower complexity,but the accuracy is usually low.In this paper,we present a family of highaccuracy nonconforming finite element methods for fourth order problems in arbitrary dimensions.The finite element methods are given in a unified way with respect to the dimension.This is an effort to reveal the balance between the accuracy and the complexity of finite element methods.展开更多
Complexity measures for keystream multisequences over Z/(N) play a crucial role in designing good stream cipher systems. This correspondence shows a general upper bound on k-error joint N-adic complexity of periodic m...Complexity measures for keystream multisequences over Z/(N) play a crucial role in designing good stream cipher systems. This correspondence shows a general upper bound on k-error joint N-adic complexity of periodic multisequences over Z/(N), and establishes the existence of periodic N-adic multisequences over Z/(N) which simultaneously possess maximal joint N-adic complexity and large k-error joint N-adic complexity. Under some conditions the overwhelming majority of all T-periodic N-adic multisequences over Z/(N) with maximal joint N-adic complexity logN(NT- 1)have a k-error joint N-adic complexity close to logN(NT- 1).展开更多
The authors present an algorithm which is a modilication of the Nguyen-Stenle greedy reduction algorithm due to Nguyen and Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for ...The authors present an algorithm which is a modilication of the Nguyen-Stenle greedy reduction algorithm due to Nguyen and Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for arbitrary rank lattices with quadratic bit complexity on the size of the input vectors. The total bit complexity of the algorithm is O（n^2·（4n!）^n·（n!/2^n）^n/2·（4/3）^n（n-1）/2）.log^2 A）where n is the rank of the lattice and A is maximal norm of the input base vectors. This is an O（log^2 A） algorithm which can be used to compute Minkowski reduced bases for the fixed rank lattices. A time complexity n!. 3n（log A）^O（1） algorithm which can be used to compute the successive minima with the help of the dual Hermite-Korkin-Zolotarev base was given by Blomer in 2000 and improved to the time complexity n!- （log A）^O（1） by Micciancio in 2008. The algorithm in this paper is more suitable for computing the Minkowski reduced bases of low rank lattices with very large base vector sizes.展开更多
文摘A central problem in the study of complexity is the measure of nonuniform complexity classes. BPPP/poly has been proved by Aldman, and EXPSPACEP/poly by Kannan. We propose the definition of approximate acceptance with which we discuss the nonuniform complexity of the K sized complete subgraph problem. The method of modal theory is used and the K sized complete subgraph problemP/poly, co NPP/poly and NPP/poly is proved. This paper solves the Karp Lipton′s open problem: “NPP/poly?”
文摘Aim To present a quantitative method for structural complexity analysis and evaluation of information systems. Methods Based on Petri net modeling and analysis techniques and with the aid of mathematical tools in general net theory(GNT), a quantitative method for structure description and analysis of information systems was introduced. Results The structural complexity index and two related factors, i.e. element complexity factor and connection complexity factor were defined, and the relations between them and the parameters of the Petri net based model of the system were derived. Application example was presented. Conclusion The proposed method provides a theoretical basis for quantitative analysis and evaluation of the structural complexity and can be applied in the general planning and design processes of the information systems.
文摘For reducing the computational complexity of the problem of joint transmit and receive antenna selection in Multiple-Input-Multiple-Output (MIMO) systems, we present a concise joint transmit/receive antenna selection algorithm. Using a novel partition of the channel matrix, we drive a concise formula. This formula enables us to augment the channel matrix in such a way that the computational complexity of the greedy Joint Transmit/Receive Antenna Selection (JTRAS) algorithm is reduced by a factor of 4n L , where n L is the number of selected antennas. A decoupled version of the proposed algorithm is also proposed to further improve the efficiency of the JTRAS algorithm, with some capacity degradation as a tradeoff. The computational complexity and the performance of the proposed approaches are evaluated mathematically and verified by computer simulations. The results have shown that the proposed joint antenna selection algorithm maintains the capacity perormance of the JTRAS algorithm while its computational complexity is only 1/4n L of that of the JTRAS algorithm. The decoupled version of the proposed algorithm further reduces the computational complexity of the joint antenna selection and has better performance than other decoupling-based algorithms when the selected antenna subset is small as compared to the total number of antennas.
基金supported by the National Natural Science Foundation of China (Nos.U1833103, 71801215, U1933103)the Fundamental Research Funds for the Central Universities (No.3122019129)。
文摘Along with the rapid development of air traffic, the contradiction between conventional air traffic management(ATM)and the increasingly complex air traffic situations is more severe,which essentially reduces the operational efficiency of air transport systems. Thus,objectively measuring the air traffic situation complexity becomes a concern in the field of ATM. Most existing studies focus on air traffic complexity assessment,and rarely on the scientific guidance of complex traffic situations. According to the projected time of aircraft arriving at the target sector boundary,we formulated two control strategies to reduce the air traffic complexity. The strategy of entry time optimization was applied to the controllable flights in the adjacent upstream sectors. In contrast,the strategy of flying dynamic speed optimization was applied to the flights in the target sector. During the process of solving complexity control models,we introduced a physical programming method. We transformed the multi-objective optimization problem involving complexity and delay to single-objective optimization problems by designing different preference function. Actual data validated the two complexity control strategies can eliminate the high-complexity situations in reality. The control strategy based on the entry time optimization was more efficient than that based on the speed dynamic optimization. A basic framework for studying air traffic complexity management was preliminarily established. Our findings will help the implementation of a complexity-based ATM.
基金Supported by the National Natural Science Foundation of China (No. 60874060)
文摘This paper presents an improved Voice Activity Detection （VAD） algorithm which uses the Signal-to-Noise Ratio （SNR） measure. We assume that noise Power Spectral Density （PSD） in each spectral bin follows a Rayleigh distribution. Rayleigh distributions with its asymmetric tail characteristics give a better description of the noise PSD distribution than Gaussian distribution. Under this asstlmption, a new threshold updating expression is derived. Since the analytical integral of the false alarm probability, the threshold updating expression can be represented without the inverse complementary error function and low computational complexity is achieved in our system. Experimental results show that the proposed VAD outperforms or at least is comparable with the VAD scheme presented by Davis under several noise environments and has a lower computational complexity.
基金Supported by the National High Technology Research and Development Program of China （2008AA01A313 ）, the National Natural Science Foundation of China （60772069）, and a Grant from the Centre for Signal Processing of the Hang Kong Polytechnic University （1-BB9c）.
文摘In this paper, the complexity of intra coding is first analyzed so as to achieve a weight of complexity measurement for each intra mode. Then, a new complexity scalable control algorithm for intra coding in H. 264 is proposed, based on the rearrangement of the order of candidate modes and an efficient complexity allocation and control （CAAC） scheme at the macroblock （MB） level. The candidate modes of each MB are rearranged according to the local-edge information. Experimental results show that our proposed algorithm can make an appropriate cut-off point of the candidate modes sequence adaptively according to the current energy condition of a mobile device, so as to adjust the complexity at any level while maximizing the video quality, which can prolong the operational lifetime of the battery with minimum degradation in video quality.
基金Key Project of the National Eleventh-Five Year Research Program of China(No.2006BAD10A07)
文摘Software protection technology has been universally emphasized, with the development of reverse engineering and static analysis techniques. So, it is important to research how to quantitatively evaluate the security of the protected software. However, there are some researchers evaluating the security of the proposed protect techniques directly by the traditional complexity metrics, which is not suffident. In order to better reflect security from software complexity, a multi-factor complexity metric based on control flow graph （CFG） is proposed, and the corresponding calculating procedures are presented in detail. Moreover, complexity density models are constructed to indicate the strength of software resisting reverse engineering and code analysis. Instance analysis shows that the proposed method is simple and practical, and can more objectively reflect software security from the perspective of the complexity.
文摘A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictions for good quality of service. Firstly, a set of reachable paths to each intermediate node from the source node and the sink node based on adjacent matrix transformation are calculated respectively. Then a temporal optimal path is selected by adopting the proposed heuristic method according to a non-linear cost function. When the total number of the accumulated nodes by bidirectional searching reaches n-2, the paths from two directions to an intermediate node should be combined and several paths via different nodes from the source node to the sink node can be obtained, then an optimal path in the whole set of paths can be taken as the output route. Some simulation examples are included to show the effectiveness and efficiency of the proposed method. In addition, the proposed algorithm can be implemented with parallel computation and thus, the new algorithm has better performance in time complexity than other algorithms. Mathematical analysis indicates that the maximum complexity in time, based on parallel computation, is the same as the polynomial complexity of O(kn2-3kn+k), and some simulation results are shown to support this analysis.
基金supported by National Natural Science Foundation of China (Grant No.11101415)the National Center for Mathematics and Interdisciplinary Sciences,CAS
文摘The approach of nonconforming finite element method admits users to solve the partial differential equations with lower complexity,but the accuracy is usually low.In this paper,we present a family of highaccuracy nonconforming finite element methods for fourth order problems in arbitrary dimensions.The finite element methods are given in a unified way with respect to the dimension.This is an effort to reveal the balance between the accuracy and the complexity of finite element methods.
基金supported by the National Natural Science Foundation of China under Grant Nos.61271271 and 61370089100 Talents Program of Chinese Academy of Sciencethe Fundamental Research Funds for the Central Universities under Grant No.2012HGBZ0622
文摘Complexity measures for keystream multisequences over Z/(N) play a crucial role in designing good stream cipher systems. This correspondence shows a general upper bound on k-error joint N-adic complexity of periodic multisequences over Z/(N), and establishes the existence of periodic N-adic multisequences over Z/(N) which simultaneously possess maximal joint N-adic complexity and large k-error joint N-adic complexity. Under some conditions the overwhelming majority of all T-periodic N-adic multisequences over Z/(N) with maximal joint N-adic complexity logN(NT- 1)have a k-error joint N-adic complexity close to logN(NT- 1).
基金supported by the National Natural Science Foundation of China (No.10871068)the Danish National Research Foundation and National Natural Science Foundation of China Joint Grant (No.11061130539)
文摘The authors present an algorithm which is a modilication of the Nguyen-Stenle greedy reduction algorithm due to Nguyen and Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for arbitrary rank lattices with quadratic bit complexity on the size of the input vectors. The total bit complexity of the algorithm is O（n^2·（4n!）^n·（n!/2^n）^n/2·（4/3）^n（n-1）/2）.log^2 A）where n is the rank of the lattice and A is maximal norm of the input base vectors. This is an O（log^2 A） algorithm which can be used to compute Minkowski reduced bases for the fixed rank lattices. A time complexity n!. 3n（log A）^O（1） algorithm which can be used to compute the successive minima with the help of the dual Hermite-Korkin-Zolotarev base was given by Blomer in 2000 and improved to the time complexity n!- （log A）^O（1） by Micciancio in 2008. The algorithm in this paper is more suitable for computing the Minkowski reduced bases of low rank lattices with very large base vector sizes.
