P vs np is An Exponential Problem, So Solution Can’t Be Proved In Polynomial Time

International Journal of Computer Science and Engineering

© 2019 by SSRG - IJCSE Journal

Volume 6 Issue 5

Year of Publication : 2019

Authors : Ravi Raja, Piyush sharma, Abhijeet singh

10.14445/23488387/IJCSE-V6I5P103

How to Cite?

Ravi Raja, Piyush sharma, Abhijeet singh, "P vs np is An Exponential Problem, So Solution Can’t Be Proved In Polynomial Time," SSRG International Journal of Computer Science and Engineering , vol. 6,  no. 5, pp. 10-12, 2019. Crossref, https://doi.org/10.14445/23488387/IJCSE-V6I5P103

Abstract:

p vs np is a problem that has been there for centuries as a part of complexity theory. We are not certain about if p is equal or not equal to np. P is a set of problems that can be solved and verified in polynomial time and NP is the set of problems that can verified in polynomial time, but we are not certain whether we will find there solution in polynomial time using a deterministic algorithm or not, although we can find the solution using a lucky algorithm . If p is not equal to np then we can be in peace knowing that all our decrypted data is safe. And if p is equal to np then none of our encrypted data is safe because in case of p is equal to np, anything that can be verified in polynomial time, can be solved in polynomial time, like password, encrypted data, account number, access code etc. In this paper we will prove that presently it is not possible to prove that p is equal to np and nor it is possible to prove that p is not equal to np, because p vs np is itself an exponential problem or so called exp problem.

Keywords:

complexity theory, Polynomial time problem, non-deterministic polynomial time problem, lucky algorithm, exponential time problem

References:

[1] M. Agrawal, N. Kayal, and N. Saxena, Primes is in P, Ann. Math. 160 (2004), 781–793.
[2] N. Alon and R.B. Boppana, The monotone circuit complexity of boolean functions, Combinatorica (1987), 1–22.
[3] T. Baker, J. Gill, and R. Solovay, Relativizations of the P =? NP question, SICOMP: SIAM Journal on Computing, 1975.
[4] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer- 19 Verlag, New York, 1998.
[5] M. Blum and R. Impagliazzo, Generic oracles and oracle classes, in Proceedings of the 28th Annual Symposium on Foundations of Computer Science, A.K. Chandra, ed., IEEE Computer Society Press, Los Angeles, 1987, 118–126. THE P VERSUS NP PROBLEM
[6] R.B. Boppana and M. Sipser, The complexity of finite functions, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, J. Van Leeuwen, ed., Elsevier and The MIT Press, Cambridge, MA, 1990, 759–804.
[7] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition, 28 McGraw Hill, New York, 2001.
[8] A. Cobham, The intrinsic computational difficulty of functions, in Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science, Y. Bar-Hille, ed., Elsevier/North-Holland, Amsterdam, 1964, 24–30.
[9] S. Cook, The complexity of theorem-proving procedures, in Conference Record of Third Annual 33 ACM Symposium on Theory of Computing, ACM, New York, 1971, 151–158.
[10] S. Cook, Computational complexity of higher type functions, in Proceedings of the International Congress of Mathematicians, Kyoto, Japan, Springer-Verlag, Berlin, 1991, 55–69.