Computational complexity in dynamic systems: A rigorous rejection of P = NP in chess, genetics, and the stock market

Authors

https://doi.org/10.48314/caa.vi.45

Abstract

This paper provides a rigorous analysis of the computational complexity in three dynamic systems—chess with rule-changing power, genetic sequence alignment with random mutations, and stock market prediction with manipulative players—to argue that P ̸= NP. We emphasize that the temporal patterns (e.g., move sequences in chess, evolutionary timelines in genetics, and time-series price movements in the stock market) in these systems cannot be reduced to polynomial-time computable problems, due to their inherent exponential or super-polynomial complexity.

In the chess scenario, rule changes are constrained to preserve EXPTIMEcompleteness. In genetics, multiple sequence alignment (MSA) remains NP-complete even under stochastic mutations. In the stock market, predicting short-term time-series patterns is NP-hard or worse, as market efficiency implies P = NP. Formal arguments, including reductions and complexity class separations, demonstrate that these temporal dynamics resist polynomial-time solutions. A chart visualizes the exponential state space growth, reinforcing the rejection of P = NP.

Keywords:

Computational complexity, Dynamic systems, Temporal patterns, Exponential state space

References

  1. [1] Sipser, M. (1996). Introduction to the theory of computation. ACM sigact news, 27(1), 27–29. https://dl.acm.org/doi/pdf/10.1145/230514.571645
  2. [2] Chandra, A. K., Kozen, D. C., & Stockmeyer, L. J. (1981). Alternation. Journal of the acm (JACM), 28(1), 114–133. https://dl.acm.org/doi/pdf/10.1145/322234.322243
  3. [3] Hartmanis, J., & Stearns, R. E. (1965). On the computational complexity of algorithms. Transactions of the american mathematical society, 117, 285–306. https://www.jstor.org/stable/1994208
  4. [4] Fraenkel, A. S., & Lichtenstein, D. (1981). Computing a perfect strategy for n× n chess requires time exponential in n. International colloquium on automata, languages, and programming (pp. 278–293). Springer. https://doi.org/10.1007/3-540-10843-2_23
  5. [5] Wang, L., & Jiang, T. (1994). On the complexity of multiple sequence alignment. Journal of computational biology, 1(4), 337–348. https://doi.org/10.1089/cmb.1994.1.337
  6. [6] Just, W. (2001). Computational complexity of multiple sequence alignment with SP-score. Journal of computational biology, 8(6), 615–623. https://doi.org/10.1089/106652701753307511
  7. [7] Ramadevi, B., & Bingi, K. (2022). Chaotic time series forecasting approaches using machine learning techniques: A review. Symmetry, 14(5), 955. https://doi.org/10.3390/sym14050955
  8. [8] Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990). Basic local alignment search tool. Journal of molecular biology, 215(3), 403–410. https://doi.org/10.1016/S0022-2836(05)80360-2
  9. [9] Papadimitriou, C. H. (1994). On the complexity of the parity argument and other inefficient proofs of existence. Journal of computer and system sciences, 48(3), 498–532. https://doi.org/10.1016/S0022-0000(05)80063-7
  10. [10] Aspnes, J., Fischer, D. F., Fischer, M. J., Kao, M. Y., & Kumar, A. (2004). Towards understanding the predictability of stock markets from the perspective of computational complexity. In New directions in statistical physics: econophysics, bioinformatics, and pattern recognition (pp. 129–151). Springer. https://doi.org/10.1007/978-3-662-08968-2_8
  11. [11] Maymin, P. Z. (2011). Markets are efficient if and only if P= NP. Algorithmic finance, 1(1), 1–11. https://doi.org/10.3233/AF-2011-007
  12. [12] Stockmeyer, L. J. (1976). The polynomial-time hierarchy. Theoretical computer science, 3(1), 1–22. https://doi.org/10.1016/0304-3975(76)90061-X
  13. [13] Fama, E. F. (1991). Efficient capital markets: II. The journal of finance, 46(5), 1575–1617. https://doi.org/10.1111/j.1540-6261.1991.tb04636.x
  14. [14] Impagliazzo, R., Paturi, R., & Zane, F. (2001). Which problems have strongly exponential complexity? Journal of computer and system sciences, 63(4), 512–530. https://doi.org/10.1006/jcss.2001.1774

Downloads

Published

2025-03-12

Issue

Vol. 2 No. 1 (2025): Complexity Analysis and Applications

Section

Special Issue: Actual Problems of Mathematical Physics and Bio-Physics

Categories

How to Cite

Hayawi, A. (2025). Computational complexity in dynamic systems: A rigorous rejection of P = NP in chess, genetics, and the stock market. Complexity Analysis and Applications, 2(1), 71-74. https://doi.org/10.48314/caa.vi.45

Similar Articles

You may also start an advanced similarity search for this article.