CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

P vs NP Solution – Advances in Computational Complexity, Status and Future Scope

by Amit Sharma, Sunil Kr. Singh
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 177 - Number 9
Year of Publication: 2019
Authors: Amit Sharma, Sunil Kr. Singh
10.5120/ijca2019919465

Amit Sharma, Sunil Kr. Singh . P vs NP Solution – Advances in Computational Complexity, Status and Future Scope. International Journal of Computer Applications. 177, 9 ( Oct 2019), 25-32. DOI=10.5120/ijca2019919465

@article{ 10.5120/ijca2019919465,
author = { Amit Sharma, Sunil Kr. Singh },
title = { P vs NP Solution – Advances in Computational Complexity, Status and Future Scope },
journal = { International Journal of Computer Applications },
issue_date = { Oct 2019 },
volume = { 177 },
number = { 9 },
month = { Oct },
year = { 2019 },
issn = { 0975-8887 },
pages = { 25-32 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume177/number9/30926-2019919465/ },
doi = { 10.5120/ijca2019919465 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:45:25.210144+05:30
%A Amit Sharma
%A Sunil Kr. Singh
%T P vs NP Solution – Advances in Computational Complexity, Status and Future Scope
%J International Journal of Computer Applications
%@ 0975-8887
%V 177
%N 9
%P 25-32
%D 2019
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The significance & stature of the P vs NP problem is so imperative that even the failed attempts at proof have furnished unprecedented breakthroughs and valuable insights. While the scientists and researchers do not expect the problem to be solved in foreseeable future, the P vs NP question has been the harbinger of advancement of the theory of computation and complexity theory in particular. Multitude of research papers have been published on number of topics which have begged numerous accolades and awards. This paper presents and highlights a non-technical review of series of complex mathematical research and enlists the notable awards & advances from each subsequent effort. The paper also presents the limitations of existing and proposed techniques and highlights the direction of active future research towards P vs NP solution.

References
  1. A. M. Turing, On computable numbers with an application to the entscheidungs problem, Proceedings of London Mathematical Society ser. 2, 1936.
  2. S. A. Cook , The complexity of theorem proving procedures, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971.
  3. Official problem description The P versus NP by Stephen Cook, www.claymath.org/millennium-problems/p-vs-np-problem, 2000.
  4. Kurt Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Volume of Monatshefte für Mathematik, 1931.
  5. A. Tarski, tr J.H. Woodger, The Concept of Truth in Formalized Languages , Logic, Semantics, Metamathematics, Hackett, 1983
  6. Alonzo Church, An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, Vol. 58, No. 2, 1936.
  7. Emil L. Post , Finite Combinatory Processes-Formulation I, The Journal of Symbolic Logic, Vol. 1, No. 3, 1936
  8. M. O. Rabin and D. Scott, Finite automata and their decision problem, IBM J. RES. 3, 1959.
  9. Jack Edmonds, Maximum matching and a polyhedron with 0,1-vertices, Journal of Research of the National Bureau of Standards Section B 69, 1965
  10. A. Cobham, The intrinsic computational complexity of functions, proc. Int. Congress on logic, methodology and philosophy of science, Amsterdam, 1965.
  11. J. Hartmanis and R. E. Stearns, On the Computational Complexity of Algorithms, trans. American Mathematics Society 117, 1965.
  12. J. Hartmanis, P. M. Lewis, and R. E. Stearns, Hierarchies of memory limited computations, Proc. 6th Annual IEEE Symp. on Switching Circuit Theory and Logical Design, 1965.
  13. M. Blum, A machine-independent theory of the complexity of recursive functions, Journal of ACM 14:2, 1967.
  14. W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Science 4:2, 1970
  15. L. Levin, Universal search problems,Problemy Peredachi Informatsii, 9(3), 1973
  16. R. M. KARP, Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum Press, NY, 1972
  17. Laszlo Babai, Graph Isomorphism in Quasipolynomial Time I: The "Local Certificates Algorithm", Combinatorics and Theoretical Computer Science seminar, 2015
  18. N. Robertson and P. Seymour, Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory, Series B, 92 (2), 2004
  19. M. Rabin, Degree of difficulty of computing a function and a partial ordering of recursive set, Tech. rep. no. 2, Hebrew university, 1960
  20. T. Baker, J. Gill and R. Solovay, Relativization of the P≠NP question, SIAM Journal on Computing 4:4, 1975.
  21. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge complexity of interactive proof-systems. Proceedings of 17th ACM Symposium on the Theory of Computation, Providence, Rhode Island. 1985.
  22. C. Lund , L. Fortnow , H. Karloff , and N. Nisan, Algebraic Methods for Interactive Proof Systems, proc. of the 22th Annual ACM symp. On theory of computing, 2-10, 1990.
  23. Adi Shamir, IP = PSPACE, Journal of the ACM, volume 39, issue 4, 1992
  24. L. Babai, L. Fortnow, C. Lund, Non-deterministic exponential time has two-prover interactive protocols, Proc. 31st Ann. IEEE Symp. Found. Comp. Sci., 1990.
  25. S. Aaronson and A. Wigderson, Algebrization: A new barrier in complexity theory, proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008
  26. O. Goldreich, M. Silvio, and A. Wigderson, Proofs that yield nothing but their validity, Journal of the ACM. 38 (3), 1991.
  27. A. A. Razborov and S. Rudich, Natural proofs, Journal of Computer and System Sciences. 55, 1997
  28. S Arora, and S. Safra, Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1), 1998
  29. C. Shannon, The synthesis of two-terminal switching circuits, Bell System Technical Journal. 28 (1), 1949.
  30. M. Ajtai,
  31. 1
  32. 1
  33. .
  34. formulae on finite structures, Annals of Pure and Applied Logic. 24: 1983.
  35. M. Furst, J. Saxe, and M. Sipser, Parity, circuits, and the polynomial-time hierarchy, Mathematical Systems Theory 17(1), 1984.
  36. J. Håstad, Computational limitations of small depth circuits, Ph.D. thesis, MIT press, 1987.
  37. AA. Razborov, Lower bounds on the size of bounded depth networks over a complete basis with logical addition, trans. in Math. notes of the Academy of Sciences of the USSR 41, 1987.
  38. R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proc. 19th ACM Symposium on Theory of Computing, 1987.
  39. A. Razborov, Lower bounds on the monotone complexity of some Boolean functions, Mathematics of the USSR, Doklady, 1985
  40. N. Alon, R. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica 7 (1), 1987
  41. R. Williams, Non-Uniform ACC Circuit Lower Bounds, CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011.
  42. R. Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings 7, 1974
  43. N. Immerman, Languages that Capture Complexity Classes, SIAM J. Comput., 16(4), 1987.
  44. N. Immerman, Nondeterministic space is closed under complement, SIAM Journal on Computing,1988.
  45. R. Szelepcsenyi, The method of forced enumeration for nondeterministic automata, Acts Informatica 26, 1988.
  46. S. Cook, and R. Reckhow, The Relative Efficiency of Propositional Proof Systems, J. Symbolic Logic 44, 1979.
  47. A. HAKEN, The intractability of resolution, Theoretical Computer Science 39,1985.
  48. R. Impagliazzo, and A. Wigderson, P = BPP requires exponential circuits: derandomizing the XOR lemma, STOC '97 (El Paso, TX, ACM, New York), 1999.
  49. J. Hartmanis, and J. Hopcroft, Independence results in computer science, ACM SIGACT News 8, no. 4,1976.
  50. A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic, Izvestiya Math. 59(1), 1995.
  51. R. DeMillo and R. Lipton, The consistency of P=NP and related problems within fragments ofnumber theory, in Proceedings of ACM STOC’79, 1979.
  52. V. Sazanov, A logical approach to the problem “P=NP?”, in Mathematical Foundations of ComputerScience, Springer LNCS 88, 1980.
  53. S. Aaronson, Is P vs NP formally Independent?, bulletin of the Europian Association for theoretical computer science,81 , 2003.
  54. K. D. Mulmuley and M. Sohoni, Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems, SIAM J. Comput. 31(2), 2001.
  55. P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing,26(5),1997.
  56. L. Grover, A fast quantum mechanical algorithm for database search, In Proceedings of the 28th ACM Symposium on the Theory of Computing ACM New York, 1996.
  57. Fortnow L., Review Article - The status of P vs NP problem, Communications of the ACM, 52(9), 2009.
  58. Sipser M., The history and status of P vs NP question, 24th annual ACM symp. On theory of computing, 1992.
  59. Fortnow L., and S. Homer, A Short History of Computational Complexity, Bulletin of the European Association for Theoretical Computer Science, 80, 2003.
  60. Hemaspaandra L., SIGACT News Complexity Theory Column 74, Dept. of Computer Science, University of Rochester, 2012.
Index Terms

Computer Science
Information Sciences

Keywords

P vs NP Cryptography Complexity theory P vs NP attempts and limitations Geometric complexity theory quantum computing One-way function incompleteness theorem.

Powered by PhDFocusTM