Готові списки джерел за темами / P versus NP problem

Зміст

Статті в журналах
Дисертації
Книги
Частини книг
Тези доповідей конференцій
Звіти організацій

Добірка наукової літератури з теми "P versus NP problem"

Автор: Grafiati

Опубліковано: 3 червня 2025

Оновлено: 6 липня 2025

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "P versus NP problem".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Статті в журналах з теми "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.

Повний текст джерела

Анотація:

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 unprovable in Peano Arithmetic) are the most complex mathematical statements (theorems, conjectures and problems) studied in this framework [9, 5, 6, 2, 20].

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 time. We use different problems to display the question of P versus NP from Formal Languages Theory View.

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 functioning of living cells, as well as from the organization of cells in tissues, organs, and other higher order structures. The devices of this paradigm, called P systems or membrane systems, constitute models for distributed, parallel and non-deterministic computing. In this paper, a computational complexity theory within the framework of Membrane Computing is introduced. Polynomial complexity classes associated with different models of cell-like and tissue-like membrane systems are defined and the most relevant results obtained so far are presented. Different borderlines between efficiency and non-efficiency are shown, and many attractive characterizations of the P ≠ NP conjecture within the framework of this bio-inspired and non-conventional computing model are studied.

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 P versus NP. In the framework of Membrane Computing, the key of this approach is to detect the syntactic or semantic ingredients that are needed to pass from a nonefficient class of membrane systems to a presumably efficient one. This paper deals with tissue P systems with communication rules of type symport/antiport allowing the evolution of the objects triggering the rules. In previous works, frontiers of efficiency were found in these kinds of membrane systems both with division rules and with separation rules. However, since they were not optimal, it is interesting to refine these frontiers. In this work, optimal frontiers of the efficiency are obtained in terms of the total number of objects involved in the communication rules used for that kind of membrane systems. These optimizations could be easier to translate, if possible, to efficient solutions in a nonefficient model.

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 non-regular iff P [Formula: see text] NP . The group of units of [Formula: see text] is the famous Richard Thompson group [Formula: see text].

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 that P A ≠ NP A for every oracle A that is p-betting-game random. Ideally, we would extend (1) to p-random oracles. We show that answering this either way would imply an unrelativized complexity class separation: (2) If P A ≠ NP A relative to every p-random oracle A , then BPP ≠ EXP. (3) If P A ≠ NP A relative to some p-random oracle A , then P ≠ PSPACE. Rossman, Servedio, and Tan [2015] showed that the polynomial-time hierarchy is infinite relative to a random oracle, solving a longstanding open problem. We consider whether we can extend (1) to show that PH A is infinite relative to oracles A that are p-betting-game random. Showing that PH A separates at even its first level would also imply an unrelativized complexity class separation: (4) If NP A ≠ coNP A for a p-betting-game measure 1 class of oracles A , then NP ≠ EXP. (5) If PH A is infinite relative to every p-random oracle A , then PH ≠ EXP. We also consider random oracles for time versus space, for example: (6) L A ≠ P A relative to every oracle A that is p-betting-game random.

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Більше джерел

Дисертації з теми "P versus NP problem"

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

Повний текст джерела

Анотація:

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'algorithme naïf que nous présentons également. Nous proposons enfin une généralisation de cet algorithme à toute classe de motifs de degré supérieur ou égal à deux. Nous nous inspirons du cas de la classe des motifs de degré un pour proposer un algorithme efficace de résolution des équations aux mots à une variable

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

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

Повний текст джерела

Анотація:

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 finished by a new separation result for p = 2 and q = 3.

Стилі APA, Harvard, Vancouver, ISO та ін.

Книги з теми "P versus NP problem"

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

Знайти повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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

Знайти повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Частини книг з теми "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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Тези доповідей конференцій з теми "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.

Повний текст джерела

Анотація:

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 boundedness problem for this UCRPQs fragment is Pi-p-2-complete, and that an equivalent bounded query can be produced in polynomial time whenever possible. When the query turns out to be unbounded, we also study the task of finding an equivalent maximally bounded query, which we show to be feasible in Pi-p-2 . As a side result of independent interest stemming from our developments, we study a notion of succinct finite automata and prove that its membership problem is NP-complete.

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 CCRV for First-Last can be determined in random polynomial time. So on the one hand, if CCRV for First-Last is NP-complete then RP = NP, which is extremely unlikely. On the other hand, showing that CCRV for First-Last is in P would also show that Exact Perfect Bipartite Matching is in P, which would solve a well-studied 40-year-old open problem. Considering RP as an option for classifying problems can also help classify problems that until now had escaped classification. For example, the sole open problem in the comprehensive table from Erdélyi et al. [2021, https://doi.org/10.1007/s10458-021-09523-9] is CCRV for 2-Approval. We show that this problem is in RP, and thus easy since it is widely assumed that P = RP.

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 competitive comparing to the state-of-the-art methods in spite of its simplicity. As a well-known NP-hard problem which has already been studied for over half a century, it is a challenging task to break the records on these classic datasets. Yet VWTS improves the best known results for 14 out of 54 large instances, and matches the optimal results for all remaining 84 ones. In addition, the computational time taken by VWTS is much shorter than other algorithms in the literature.

Стилі APA, Harvard, Vancouver, ISO та ін.

Звіти організацій з теми "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.

Повний текст джерела

Анотація:

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 us to distinguish queries that were indistinguishable before. We show that the dichotomy between P and PP in (Open)PDBs can be lifted to the case of first-order rewritable positive programs (without negative constraints); and that the problem can become NP^PP-complete, once negative constraints are allowed. We also propose an approximating semantics that circumvents the increase in complexity caused by negative constraints.

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!