2022, Vol. 3, Issue 1, Part A
Analysis and research on computational complexity
Author(s): Deepthi M
Abstract: Computational complexity is basically the amount time and space (resources) particular algorithm consume while executing. Measurement of this, would help us to predict how fast an algorithm can run, thus helping us to know how fast problem can be solved. The motive of this research paper is to present an outline of Computational complexity. We have mainly focused on defining intrinsic complexity of problem and defining their upper and lower bounds. Problems in computational complexity is based on inherent complexity. This difficulty is dependent on processing time of problem which depends on the steps involved to solve it. So, we begin with processing time, hardware complexity, delay and speed up [1, 2, 3]. We have also discussed Computational classes. They are said to be main part of Complexity theory. It is basically set of problems which uses same amount of resources [4, 5, 6]. As there are many problems in computational complexity and everything can’t be covered, definability and named problems will be our focal point. We also go through probabilistic and parallel computation. P and NP problems is heart of computational complexity. P problems are the ones that can be solved pretty quickly [7, 8, 9], while NP problems aren’t. So, we finally conclude by considering many problems found in system & classifying them.
Pages: 38-43 | Views: 932 | Downloads: 472
Download Full Article: Click Here
How to cite this article:
Deepthi M. Analysis and research on computational complexity. Int J Res Circuits Devices Syst 2022;3(1):38-43.
