Relevant bibliographies by topics / P versus NP problem

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'P versus NP problem'

Author: Grafiati
Published: 3 June 2025
Last updated: 19 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'P versus NP problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "P versus NP problem"

1

CALUDE, CRISTIAN S., ELENA CALUDE, and MELISSA S. QUEEN. "INDUCTIVE COMPLEXITY OF THE P VERSUS NP PROBLEM." Parallel Processing Letters 23, no. 01 (2013): 1350007. http://dx.doi.org/10.1142/s0129626413500072.

Full text
Abstract:
This paper does not propose a solution, not even a new possible attack, to the P versus NP problem. We are asking the simpler question: How “complex” is the P versus NP problem? Using the inductive complexity measure—a measure based on computations run by inductive register machines of various orders—developed in [2], we determine an upper bound on the inductive complexity of second order of the P versus NP problem. From this point of view, the P versus NP problem is significantly more complex than the Riemann hypothesis. To date, the P versus NP problem and the Goostein theorem (which is unpr
APA, Harvard, Vancouver, ISO, and other styles
2

Ruiz-Vanoye, Jorge A., Ocotlán Díaz-Parra, Francisco Rafael Trejo-Macotela, and Julio Cesar Ramos-Fernández. "Editorial: P versus NP problem from Formal Languages Theory View." International Journal of Combinatorial Optimization Problems and Informatics 12, no. 1 (2020): 1–8. https://doi.org/10.61467/2007.1558.2021.v12i1.207.

Full text
Abstract:
P versus NP is an unsolved problem in mathematics and computational complexity. In this paper, we use the formal language theory to the computational complexity to analyze P versus NP problem from a new point of view. P versus NP problem is to determine whether some deterministic algorithm also accepts every language accepted by some nondeterministic algorithm in polynomial time in polynomial time. Then, we use the theory of formal languages to determine whether some deterministic algorithm also accepts every language accepted by some nondeterministic algorithm in polynomial time in polynomial
APA, Harvard, Vancouver, ISO, and other styles
3

Fortnow, Lance. "The status of the P versus NP problem." Communications of the ACM 52, no. 9 (2009): 78–86. http://dx.doi.org/10.1145/1562164.1562186.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Meester, R. W. J., and K. Slooten. "DNA database matches: A p versus np problem." Forensic Science International: Genetics 46 (May 2020): 102229. http://dx.doi.org/10.1016/j.fsigen.2019.102229.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Pérez-Jiménez, Mario J. "The P versus NP Problem from the Membrane Computing View." European Review 22, no. 1 (2014): 18–33. http://dx.doi.org/10.1017/s1062798713000598.

Full text
Abstract:
In the last few decades several computing models using powerful tools from Nature have been developed (because of this, they are known as bio-inspired models). Commonly, the space-time trade-off method is used to develop efficient solutions to computationally hard problems. According to this, implementation of such models (in biological, electronic, or any other substrate) would provide a significant advance in the practical resolution of hard problems. Membrane Computing is a young branch of Natural Computing initiated by Gh. Păun at the end of 1998. It is inspired by the structure and functi
APA, Harvard, Vancouver, ISO, and other styles
6

Kumar, Neelam Jeevan. "Algorithm for P versus NP Problem on Sets by JEEVAN – KUSHALAIAH Method." International Journal of Computer Applications Technology and Research 2, no. 5 (2013): 526–29. http://dx.doi.org/10.7753/ijcatr0205.1005.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Orellana-Martín, David, Luis Valencia-Cabrera, Bosheng Song, Linqiang Pan, and Mario J. Pérez-Jiménez. "Tuning Frontiers of Efficiency in Tissue P Systems with Evolutional Communication Rules." Complexity 2021 (April 28, 2021): 1–14. http://dx.doi.org/10.1155/2021/7120840.

Full text
Abstract:
Over the last few years, a new methodology to address the P versus NP problem has been developed, based on searching for borderlines between the nonefficiency of computing models (only problems in class P can be solved in polynomial time) and the presumed efficiency (ability to solve NP-complete problems in polynomial time). These borderlines can be seen as frontiers of efficiency, which are crucial in this methodology. “Translating,” in some sense, an efficient solution in a presumably efficient model to an efficient solution in a nonefficient model would give an affirmative answer to problem
APA, Harvard, Vancouver, ISO, and other styles
8

Birget, J. C. "Polynomial-time right-ideal morphisms and congruences." International Journal of Algebra and Computation 28, no. 05 (2018): 791–835. http://dx.doi.org/10.1142/s0218196718500364.

Full text
Abstract:
We continue with the functional approach to the P -versus- NP problem, begun in [J. C. Birget, Semigroups and one-way functions, Int. J. Algebra Comput. 25(1–2) (2015) 3–36; J. C. Birget, Infinitely generated semigroups and polynomial complexity, Int. J. Algebra Comput. 26(04) (2016) 727–750.] We previously constructed a monoid [Formula: see text] that is non-regular iff NP [Formula: see text] P . We now construct homomorphic images of [Formula: see text] with interesting properties. In particular, the homomorphic image [Formula: see text] of [Formula: see text] is finitely generated, and is n
APA, Harvard, Vancouver, ISO, and other styles
9

Hitchcock, John M., Adewale Sekoni, and Hadi Shafei. "Polynomial-Time Random Oracles and Separating Complexity Classes." ACM Transactions on Computation Theory 13, no. 1 (2021): 11–16. http://dx.doi.org/10.1145/3434389.

Full text
Abstract:
Bennett and Gill [1981] showed that P A ≠ NP A ≠ coNP A for a random oracle A , with probability 1. We investigate whether this result extends to individual polynomial-time random oracles. We consider two notions of random oracles: p-random oracles in the sense of martingales and resource-bounded measure [Lutz 1992; Ambos-Spies et al. 1997], and p-betting-game random oracles using the betting games generalization of resource-bounded measure [Buhrman et al. 2000]. Every p-betting-game random oracle is also p-random; whether the two notions are equivalent is an open problem. (1) We first show th
APA, Harvard, Vancouver, ISO, and other styles
10

de Figueiredo, Celina M. H. "The P versus NP–complete dichotomy of some challenging problems in graph theory." Discrete Applied Mathematics 160, no. 18 (2012): 2681–93. http://dx.doi.org/10.1016/j.dam.2010.12.014.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "P versus NP problem"

1

Eyono, Obono Séraphin Désiré. "Recherche efficace d'images morphiques de mots." Rouen, 1995. http://www.theses.fr/1995ROUE5014.

Full text
Abstract:
Nous étudions dans cette thèse la recherche d'un motif homomorphe dans un texte et montrons que ce problème est NP-complet. Nous établissons une première classification des motifs: les motifs simples (ou motifs élémentaires) et les motifs non simples. Nous donnons une caractérisation de la rationalité des motifs simples. Nous proposons ensuite une classification des motifs simples selon leurs degrés, ainsi qu'un algorithme efficace de recherche dans un texte des images de tout motif de degré un ou deux, qui fait gagner, ou presque gagner, un ou deux degrés de complexité par rapport à l'algorit
APA, Harvard, Vancouver, ISO, and other styles
2

Kopřiva, Jan. "Srovnání algoritmů při řešení problému obchodního cestujícího." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2009. http://www.nusl.cz/ntk/nusl-222126.

Full text
Abstract:
The Master Thesis deals with logistic module innovation of information system ERP. The principle of innovation is based on implementation of heuristic algorithms which solve Travel Salesman Problems (TSP). The software MATLAB is used for analysis and tests of these algorithms. The goal of Master Thesis is the comparison of selections algorithm, which are suitable for economic purposes (accuracy of solution, speed of calculation and memory demands).
APA, Harvard, Vancouver, ISO, and other styles
3

Ševčíková, Renáta. "NP vyhledávací problémy a redukce mezi nimi." Master's thesis, 2012. http://www.nusl.cz/ntk/nusl-305877.

Full text
Abstract:
NP search problems and reductions among them Renáta Ševčíková In the thesis we study the class of Total NP search problems. More attention is devoted to study the subclasses of Total NP search problems and reductions among them. We combine some known methods: the search trees and their relation to re- ductions, the Nullstellensatz refutation and the degree lower bound based on design to show that two classes of relativized NP search problems based on Mod-p counting principle and Mod-q counting principle, where p and q are different primes, are not reducible to each other. This thesis is finish
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "P versus NP problem"

1

Mohandoss, Ramaswami. What Is the P vs NP Problem? Orange Window Publishing, 2022.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Mohandoss, Ramaswami. What is the P vs NP problem? Orange Window Publishing, 2022.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "P versus NP problem"

1

Calude, Cristian S., Elena Calude, and Melissa S. Queen. "Inductive Complexity of P versus NP Problem." In Unconventional Computation and Natural Computation. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32894-7_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Fortnow, Lance. "A Personal View of the P versus NP Problem." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-39053-1_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Pérez-Jiménez, Mario J., Alvaro Romero-Jiménez, and Fernando Sancho-Caparrini. "The P Versus NP Problem Through Cellular Computing with Membranes." In Aspects of Molecular Computing. Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-24635-0_26.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Krantz, Steven G., and Harold R. Parks. "The P/NP Problem." In A Mathematical Odyssey. Springer US, 2014. http://dx.doi.org/10.1007/978-1-4614-8939-9_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Bürgisser, Peter, Michael Clausen, and Mohammad Amin Shokrollahi. "P Versus NP: A Nonuniform Algebraic Analogue." In Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/978-3-662-03338-8_21.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Blum, Lenore, Felipe Cucker, Michael Shub, and Steve Smale. "Algebraic Settings for the Problem “P ≠ NP?”." In Complexity and Real Computation. Springer New York, 1998. http://dx.doi.org/10.1007/978-1-4612-0701-6_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Grötschel, Martin. "Das Problem mit der Komplexität: P = NP?" In Diskrete Mathematik erleben. Springer Fachmedien Wiesbaden, 2015. http://dx.doi.org/10.1007/978-3-658-06993-3_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Fan, Xueshuang, Yunjuan Li, and Zongqi Sun. "Theoretical Basis of P and NP Problem." In Lecture Notes in Electrical Engineering. Springer Singapore, 2021. http://dx.doi.org/10.1007/978-981-16-0115-6_248.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Jukna, S., A. Razborov, P. Savický, and I. Wegener. "On P versus NP∩co-NP for decision trees and read-once branching programs." In Mathematical Foundations of Computer Science 1997. Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/bfb0029975.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Bürgisser, Peter. "On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity." In Mathematical Foundations of Computer Science 2001. Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-44683-4_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "P versus NP problem"

1

Figueira, Diego, S. Krishna, Om Swostik Mishra, and Anantha Padmanabha. "Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions." In 21st International Conference on Principles of Knowledge Representation and Reasoning {KR-2023}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/kr.2024/34.

Full text
Abstract:
The problem of whether a recursive query can be rewritten as query without recursion is a fundamental reasoning task, known as the boundedness problem. Here we study the boundedness problem for Unions of Conjunctive Regular Path Queries (UCRPQs), a navigational query language extensively used in ontology and graph database querying. The boundedness problem for UCRPQs is known to be decidable, ExpSpace-complete. Here we focus our analysis on UCRPQs using simple regular expressions, which are of high practical relevance and enjoy a lower reasoning complexity. We show that the complexity for the
APA, Harvard, Vancouver, ISO, and other styles
2

Fakotakis, Nikos Dimitris. "P versus NP." In Emerging Tech Conference Edge Intelligence 2022. Hellenic Emerging Technology Industry Association, 2025. https://doi.org/10.63438/ccyx6126.

Full text
Abstract:
The generalized Sudoku problem, with S as the set of the symbols, is known to be NP-complete and it is equivalent to any other NP-complete problem. In this paper, we present a method that solves the Sudoku Problem in polynomial time and proves that P = NP.
APA, Harvard, Vancouver, ISO, and other styles
3

Srinivasan, N. "Tutorial: Current state of P vs NP problem." In 2011 International Conference on Recent Trends in Information Technology (ICRTIT). IEEE, 2011. http://dx.doi.org/10.1109/icrtit.2011.5972506.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Sipser, Michael. "The history and status of the P versus NP question." In the twenty-fourth annual ACM symposium. ACM Press, 1992. http://dx.doi.org/10.1145/129712.129771.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Rubin, Stuart H., Thouraya Bouabana-Tebibel, Yasmin Hoadjli, and Zahira Ghalem. "Reusing the NP-Hard Traveling-Salesman Problem to Demonstrate That P~NP (Invited Paper)." In 2016 IEEE 17th International Conference on Information Reuse and Integration (IRI). IEEE, 2016. http://dx.doi.org/10.1109/iri.2016.84.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Rybalov, Alexander N. "On the P vs NP problem over reals with integer oracle." In 2016 Dynamics of Systems, Mechanisms and Machines (Dynamics). IEEE, 2016. http://dx.doi.org/10.1109/dynamics.2016.7819075.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Ambos-Spies, Klaus. "Honest Polynomial Reducibilities, Recursively Enumerable Sets, and the P=?NP Problem." In Proceeding Structure in Complexity Theory. IEEE, 1987. http://dx.doi.org/10.1109/psct.1987.10319255.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Fitzsimmons, Zack, and Edith Hemaspaandra. "Insight into Voting Problem Complexity Using Randomized Classes." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/42.

Full text
Abstract:
The first step in classifying the complexity of an NP problem is typically showing the problem in P or NP-complete. This has been a successful first step for many problems, including voting problems. However, in this paper we show that this may not always be the best first step. We consider the problem of constructive control by replacing voters (CCRV) introduced by Loreggia et al. [2015, https://dl.acm.org/doi/10.5555/2772879.2773411] for the scoring rule First-Last, which is defined by (1, 0, ..., 0, -1). We show that this problem is equivalent to Exact Perfect Bipartite Matching, and so CCR
APA, Harvard, Vancouver, ISO, and other styles
9

Elorza, Anne, Leticia Hernando, and Jose A. Lozano. "Transitions from P to NP-hardness: the case of the Linear Ordering Problem." In 2022 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2022. http://dx.doi.org/10.1109/cec55065.2022.9870392.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Zhang, Qingyun, Zhipeng Lü, Zhouxing Su, Chumin Li, Yuan Fang, and Fuda Ma. "Vertex Weighting-Based Tabu Search for p-Center Problem." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/206.

Full text
Abstract:
The p-center problem consists of choosing p centers from a set of candidates to minimize the maximum cost between any client and its assigned facility. In this paper, we transform the p-center problem into a series of set covering subproblems, and propose a vertex weighting-based tabu search (VWTS) algorithm to solve them. The proposed VWTS algorithm integrates distinguishing features such as a vertex weighting technique and a tabu search strategy to help the search to jump out of the local optima. Computational experiments on 138 most commonly used benchmark instances show that VWTS is highly
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "P versus NP problem"

1

Borgwardt, Stefan, Ismail Ilkan Ceylan, and Thomas Lukasiewicz. Ontology-Mediated Queries for Probabilistic Databases. Technische Universität Dresden, 2017. http://dx.doi.org/10.25368/2023.218.

Full text
Abstract:
Probabilistic databases (PDBs) are usually incomplete, e.g., contain only the facts that have been extracted from the Web with high confidence. However, missing facts are often treated as being false, which leads to unintuitive results when querying PDBs. Recently, open-world probabilistic databases (OpenPDBs) were proposed to address this issue by allowing probabilities of unknown facts to take any value from a fixed probability interval. In this paper, we extend OpenPDBs by Datalog± ontologies, under which both upper and lower probabilities of queries become even more informative, enabling u
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'P versus NP problem' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography