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

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

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 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 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 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 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 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 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 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 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!