Computational Complexity

Complex systems (CS) involve many elements that interact at different scales in time and space. The challenges in modeling CS led to the development of novel computational tools with applications in a wide range of scientific areas. The computational problems posed by CS exhibit intrinsic difficulties that are a major concern in Computational Complexity Theory.

This Special Issue (SI) focused on new theoretical and practical findings, and computational methods, applicable to difficult problems, whose solution demands extensive and powerful resources, approaching the limits of the available computer systems. It comprises 12 selected papers that are presented in the sequel in alphabetic order.

In the paper “A Comparison of Classification Methods for Telediagnosis of Parkinson’s Disease”, Haydar Ozkan presents a novel telemedicine technology aimed to remotely detect Parkinson’s Disease by means of dysphonia features. Several feature transformation and machine-learning methods were implemented and tested [1].

The paper “A Complexity-Based Approach for the Detection of Weak Signals in Ocean Ambient Noise”, by Shashidhar Siddagangaiah, Yaan Li, Xijing Guo, Xiao Chen, Qunfei Zhang, Kunde Yang and Yixin Yang, proposes using dynamical and statistical complexity to detect the presence of weak ship noise embedded in ambient noise. They demonstrate that complexity performs better than the traditional spectrogram-based methods [2].

The paper “Empirical Laws and Foreseeing the Future of Technological Progress”, by António M. Lopes, J. A. Tenreiro Machado and Alexandra M. Galhano, revisits the Moore’s law (ML) as one of many empirical expressions that is used to characterize natural and artificial phenomena. The ML addresses technological progress and is expected to predict future trends. Data series of multiple sources, available for scientific and computational processing, can be described by means of mathematical expressions that, in some cases, follow simple expressions and empirical laws. However, the extrapolation toward the future is considered with skepticism by the scientific community, particularly in the case of phenomena involving complex behavior. The authors address these issues in the light of entropy and pseudo-state space. Their statistical and dynamical techniques lead to a more assertive perspective on the adoption of a given candidate law [3].

In “Entropy Complexity and Stability of a Nonlinear Dynamic Game Model with Two Delays”, Zhihui Han, Junhai Ma, Fengshan Si and Wenbo Ren propose a duopoly game model with double delays in hydropower market. They analyze the influence of time delay parameters on the system complexity [4].

In “Normalized Minimum Error Entropy Algorithm with Recursive Power Estimation”, Namyong Kim and Kihyeon Kwon present a normalized version of the minimum error entropy algorithm. The step size of the algorithm is normalized with the power of input entropy that is estimated recursively for reducing its computational complexity [5].

The manuscript “Evolution Characteristics of Complex Fund Network and Fund Strategy Identification”, by Honglin Yang, Penglan Fang, Hong Wan, Yucan Liu and Hui Lei, introduces a novel network-based quantitative method to help investors identifying the actual strategy of open-ended funds. By using a minimum spanning tree and planar maximally-filtered graph, they build a network of open-ended funds in China’s market and investigate the evolution characteristics of the networks over multiple time periods and timescales [6].

In “Forecasting Energy Value at Risk Using Multiscale Dependence Based Methodology”, Kaijian He, Rui Zha, Yanhui Chen and Kin Keung Lai formulate a multiscale dependence-based methodology to analyze the dependence structure and to estimate the downside portfolio risk measures in energy markets. They present a bivariate empirical mode decomposition, and demonstrate that the methodology improves performance significantly in terms of accuracy and reliability measures [7].

In “Perturbation of Fractional Multi-Agent Systems in Cloud Entropy Computing”, by Rabha W. Ibrahim, Hamid A. Jalab and Abdullah Gani, the authors introduce a new perturbed algorithm based on the fractional Poisson process. The discrete dynamics are suggested by using fractional entropy and fractional Tsallis entropy [8].

In the paper “Multi-Level Formation of Complex Software Systems”, by Hui Li, Li-Ying Hao and Rong Chen, the authors develop a multi-level formation model for complex software systems. Simulations based on the proposed model showed realistic structural properties of software networks, such as power-law, clustering and modularization. The ideas can be helpful for understanding software evolution and for software engineering practices [9].

The article “Operational Complexity of Supplier-Customer Systems Measured by Entropy? Case Studies”, by Ladislav Lukáš and Jiří Hofman, addresses a unified entropy-based approach for the quantitative measurement of operational complexity of company supplier-customer relations. Results of supplier-customer system analysis from selected Czech small and medium-sized enterprises are presented in various computational and managerial decision making details [10].

In “Selected Remarks about Computer Processing in Terms of Flow Control and Statistical Mechanics”, Dominik Strzałka proposes a new description of algorithms’ performance by computational complexity and processing, taking into account the existing references between the idea of Turing machines and their physical implementations [11].

The paper “Tea Category Identification Using a Novel Fractional Fourier Entropy and Jaya Algorithm”, by Yudong Zhang, Xiaojun Yang, Carlo Cattani, Ravipudi Venkata Rao, Shuihua Wang and Preetha Phillips, proposes a tea-category identification system that can automatically determine tea category from images captured by a digital camera. Apart from the traditional color histogram features, they introduce fractional Fourier entropy for extracting additional features. Several tests demonstrate the effectiveness of the technique [12].

The guest editors hope that the selected papers will help scholars and researchers to push forward the progress in the emerging area of computational complexity.