Thematische Bibliographien / P versus NP problem

Inhaltsverzeichnis

Zeitschriftenartikel
Dissertationen
Bücher
Buchteile
Konferenzberichte
Berichte der Organisationen

Auswahl der wissenschaftlichen Literatur zum Thema „P versus NP problem“

Autor: Grafiati

Veröffentlicht am 3. Juni 2025

Zuletzt aktualisiert am 31. Juli 2025

Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an

Wählen Sie eine Art der Quelle aus:

Machen Sie sich mit den Listen der aktuellen Artikel, Bücher, Dissertationen, Berichten und anderer wissenschaftlichen Quellen zum Thema "P versus NP problem" bekannt.

Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.

Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.

Zeitschriftenartikel zum Thema "P versus NP problem"

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Mehr Quellen

Dissertationen zum Thema "P versus NP problem"

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

Bücher zum Thema "P versus NP problem"

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

Den vollen Inhalt der Quelle finden

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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

Den vollen Inhalt der Quelle finden

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Buchteile zum Thema "P versus NP problem"

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Konferenzberichte zum Thema "P versus NP problem"

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

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.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

Berichte der Organisationen zum Thema "P versus NP problem"

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.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

Wir bieten Rabatte auf alle Premium-Pläne für Autoren, deren Werke in thematische Literatursammlungen aufgenommen wurden. Kontaktieren Sie uns, um einen einzigartigen Promo-Code zu erhalten!