A Unified Complexity Theory Analyzing Medical and Chemical Algorithms

Aqib Ali  Buriro; Shazma  Tahseen; Syed Ahmed  Ali; Raheel  Sarwar

doi:10.62019/z0jsj813

Authors

Aqib Ali Buriro Mehran University of Engineering and Technology, Jamshoro, Pakistan.
Shazma Tahseen Liaquat University of Medical & Health Sciences (LUMHS) Jamshoro Sindh, Pakistan.
Syed Ahmed Ali Iqra University, Main Campus, Karachi, Pakistan.
Raheel Sarwar Iqra University, Main Campus, Karachi, Pakistan.

DOI:

https://doi.org/10.62019/z0jsj813

Keywords:

Computational, Complexity, Real-Time, Modeling, Execution, Time, Optimization, Dynamic Systems

Abstract

TThis study focus on exploring dynamic ways to unified , quantify a computational complexity theory which has traditionally been measured using asymptotic symbols such as Big- O, Big-Ɵ and Big-Ω .which only provides theoretical information behind the execution of an algorithm, neglecting a real-time situation where an algorithm can shows their actual behavior and also not able to reduce time and space complexity of an algorithm To solve this research gap, we introduce a unified complexity theory to measure actual complexity resource constraint by introducing a Universal Complexity Function. It is a mathematically formulated by comprising common factor that really impact on the execution of an algorithm such as time function, sequence of problem function and complexity difference functions. To utilize and provide our stance with respect to proposed model, we have implemented Python profiling devices like timeit and cProfile which gives us observational runtime information. This proposed model helps us to identify actual pattern which really impact on the health of an algorithm and help us to reduce them. We have also proposed indispensably optimization work ∫〖(f(t)-f(D)) 〗 to distinguish wasteful aspect and foresee execution design in both classical and AI-based calculations. Our proposed model is approved over 20 calculations; containing NP-hard issues, profound learning models, and quantum reenactments. It has come about as a solid relationship between the proposed measurements and commonsense calculation proficiency, uncovering impediments in conventional approaches and advertising a generalizable, measurable and versatile, and versatile system for cutting edge computational framework.

References

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.

[2] Knuth, D. E. (1997). The art of computer programming: Volume 1: Fundamental algorithms (3rd ed.). Addison-Wesley.

[3] Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1983). Data structures and algorithms. Addison-Wesley.

[4] Kolmogorov, A. N. (1965). Three approaches to the quantitative definition of information. Problems of Information Transmission, 1(1), 1–7.

[5] Tarjan, R. E. (1985). Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods, 6(2), 306–318. DOI: https://doi.org/10.1137/0606031

[6] Cook, S. A. (1971). The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing (pp. 151–158). DOI: https://doi.org/10.1145/800157.805047

[7] Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of Computer Computations (pp. 85–103). Plenum Press. DOI: https://doi.org/10.1007/978-1-4684-2001-2_9

[8] Arora, S., & Barak, B. (2009). Computational complexity: A modern approach. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9780511804090

[9] Python Software Foundation. (n.d.). timeit — Measure execution time of small code snippets. Python 3.9. https://docs.python.org/3/library/timeit.html

[10] Python Software Foundation. (n.d.). cProfile — Performance profiling. Python 3.9. https://docs.python.org/3/library/profile.html

[11] Dean, J., & Barroso, L. A. (2013). The tail at scale. Communications of the ACM, 56(2), 74–80. DOI: https://doi.org/10.1145/2408776.2408794

[12] Patterson, D. A., & Hennessy, J. L. (2017). Computer organization and design: RISC-V edition (2nd ed.). Morgan Kaufmann.

[13] Amdahl, G. M. (1967). Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the Spring Joint Computer Conference (pp. 483–485). DOI: https://doi.org/10.1145/1465482.1465560

[14] Domingos, P. (2012). A few useful things to know about machine learning. Communications of the ACM, 55(10), 78–87. DOI: https://doi.org/10.1145/2347736.2347755

[15] Li, L., Jamieson, K., Rostamizadeh, A., Gonina, E., Hardt, M., Recht, B., & Talwalkar, A. (2020). A system for massively parallel hyperparameter tuning. Communications of the ACM, 63(12), 90–99. DOI: https://doi.org/10.1145/3376902

[16] Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep learning. MIT Press.

[17] Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32. DOI: https://doi.org/10.1023/A:1010933404324

[18] Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273–297. DOI: https://doi.org/10.1023/A:1022627411411

[19] Hinton, G. E., & Salakhutdinov, R. R. (2006). Reducing the dimensionality of data with neural networks. Science, 313(5786), 504–507. DOI: https://doi.org/10.1126/science.1127647

[20] LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. Nature, 521(7553), 436–444. DOI: https://doi.org/10.1038/nature14539

[21] Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), 558–565. DOI: https://doi.org/10.1145/359545.359563

[22] Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2), 374–382. DOI: https://doi.org/10.1145/3149.214121

[23] Lamport, L. (1998). The part-time parliament. ACM Transactions on Computer Systems, 16(2), 133–169. DOI: https://doi.org/10.1145/279227.279229

[24] Ongaro, D., & Ousterhout, J. (2014). In search of an understandable consensus algorithm. In Proceedings of the 2014 USENIX Annual Technical Conference (pp. 305–319).

[25] Brewer, E. A. (2000). Towards robust distributed systems. In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing (PODC), 1. DOI: https://doi.org/10.1145/343477.343502

[26] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. DOI: https://doi.org/10.1007/BF01386390

[27] Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48–50. DOI: https://doi.org/10.1090/S0002-9939-1956-0078686-7

[28] Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1389–1401. DOI: https://doi.org/10.1002/j.1538-7305.1957.tb01515.x

[29] Ford Jr., L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399–404. DOI: https://doi.org/10.4153/CJM-1956-045-5

[30] Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2), 248–264. DOI: https://doi.org/10.1145/321694.321699

[31] Codd, E. F. (1970). A relational model of data for large shared data banks. Communications of the ACM, 13(6), 377–387. DOI: https://doi.org/10.1145/362384.362685

[32] Gray, J. N. (1978). Notes on database operating systems. In Operating Systems: An Advanced Course (pp. 393–481). DOI: https://doi.org/10.1007/3-540-08755-9_9

[33] Chamberlin, D. D., & Boyce, R. F. (1974). SEQUEL: A structured English query language. In Proceedings of the 1974 ACM SIGFIDET Workshop on Data Description, Access and Control (pp. 249–264). DOI: https://doi.org/10.1145/800296.811515

[34] Stonebraker, M., & Hellerstein, J. M. (2005). What goes around comes around. In Readings in Database Systems (4th ed.). MIT Press.

[35] Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., ... & Gruber, H. (2006). Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems, 26(2), 4. DOI: https://doi.org/10.1145/1365815.1365816

[36] DeCandia, G., Hastorun, D., Jampani, M., Kashin, G., Keith, R., Kerala, J., ... & Vogels, W. (2007). Dynamo: Amazon’s highly available key-value store. In Proceedings of the Twenty-First ACM SIGOPS Symposium on Operating Systems Principles (pp. 205–220). DOI: https://doi.org/10.1145/1294261.1294281

[37] Flynn, M. J. (1972). Some computer organizations and their effectiveness. IEEE Transactions on Computers, C-21(9), 948–960. DOI: https://doi.org/10.1109/TC.1972.5009071

[38] Dongarra, J. J., Hinds, A. R., & Siewiorek, D. P. (1987). LAPACK: A portable linear algebra library for high-performance computers. ACM SIGARCH Computer Architecture News, 15(5), 1–2.

[39] Asanovic, K., Bodik, R., Catanzaro, B. C., Johnson, J., Keutzer, K., Krste, N., ... & Williams, S. (2006). The landscape of parallel computing research: A view from Berkeley. Technical Report UCB/EECS-2006-183, EECS Department, University of California, Berkeley.

[40] Bell, G., & Gordon, R. L. (1971). The C.mmp/Hydra: An experimental computer system. In Proceedings of the AFIPS Spring Joint Computer Conference, 39, 923–930.

[41] Raghavan, P. (1988). Probabilistic construction of the Lovász local lemma. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (pp. 531–540).

[42] Motwani, R., & Raghavan, P. (1995). Randomized algorithms. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9780511814075

[43] Johnson, D. S. (1974). Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3), 256–278. DOI: https://doi.org/10.1016/S0022-0000(74)80044-9

[44] Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6), 1115–1145. DOI: https://doi.org/10.1145/227683.227684

[45] Hoare, C. A. R. (1969). An axiomatic basis for computer programming. Communications of the ACM, 12(10), 576–580. DOI: https://doi.org/10.1145/363235.363259

[46] Clarke, E. M., & Emerson, E. A. (1981). Design and synthesis of synchronization skeletons using branching time temporal logic. In International Workshop on Logics of Programs (pp. 52–71). Springer. DOI: https://doi.org/10.1007/BFb0025774

[47] Popek, G. J., & Goldberg, R. P. (1974). Formal requirements for virtualizable third generation architectures. Communications of the ACM, 17(7), 412–421. DOI: https://doi.org/10.1145/361011.361073

[48] Cerf, V. G., & Kahn, R. E. (1974). A protocol for packet network intercommunication. IEEE Transactions on Communications, 22(5), 637–648. DOI: https://doi.org/10.1109/TCOM.1974.1092259

[49] Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. In Proceedings of the Seventh International Conference on World Wide Web (pp. 107–117). DOI: https://doi.org/10.1016/S0169-7552(98)00110-X

[50] Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: An introduction. MIT Press. DOI: https://doi.org/10.1109/TNN.1998.712192