Relevant bibliographies by topics / NP-complete problems

Contents

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

Academic literature on the topic 'NP-complete problems'

Author: Grafiati
Published: 4 June 2021
Last updated: 16 June 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 'NP-complete problems.'

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 "NP-complete problems"

1

Saeednia, S. "New NP-complete partition problems." IEEE Transactions on Information Theory 48, no. 7 (2002): 2092–94. http://dx.doi.org/10.1109/tit.2002.1013150.

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

Ronn, Eytan. "NP-complete stable matching problems." Journal of Algorithms 11, no. 2 (1990): 285–304. http://dx.doi.org/10.1016/0196-6774(90)90007-2.

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

Monien, Burkhard, and Ivan Hal Sudborough. "Bandwidth constrained NP-complete problems." Theoretical Computer Science 41 (1985): 141–67. http://dx.doi.org/10.1016/0304-3975(85)90068-4.

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

Stewart, Iain A. "Complete problems for monotone NP." Theoretical Computer Science 145, no. 1-2 (1995): 147–57. http://dx.doi.org/10.1016/0304-3975(94)00175-i.

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

Orus, R. "Two slightly-entangled NP-complete problems." Quantum Information and Computation 5, no. 6 (2005): 449–55. http://dx.doi.org/10.26421/qic5.6-3.

Full text
Abstract:
We perform a mathematical analysis of the classical computational complexity of two genuine quantum-mechanical problems, which are inspired in the calculation of the expected magnetizations and the entanglement between subsystems for a quantum spin system. These problems, which we respectively call SES and SESSP, are specified in terms of pure slightly-entangled quantum states of $n$ qubits, and rigorous mathematical proofs that they belong to the NP-Complete complexity class are presented. Both SES and SESSP are, therefore, computationally equivalent to the relevant $3$-SAT problem, for which an efficient algorithm is yet to be discovered.
APA, Harvard, Vancouver, ISO, and other styles
6

Budinich, Marco. "Neural networks for NP-complete problems." Nonlinear Analysis: Theory, Methods & Applications 30, no. 3 (1997): 1617–24. http://dx.doi.org/10.1016/s0362-546x(97)00308-8.

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

Rhee, Wansoo T., and Michel Talagrand. "Martingale Inequalities and NP-Complete Problems." Mathematics of Operations Research 12, no. 1 (1987): 177–81. http://dx.doi.org/10.1287/moor.12.1.177.

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

Listrovoy, S. V. "On the Theory of NP-Complete Problems." INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY 11, no. 4 (2013): 2481–83. http://dx.doi.org/10.24297/ijct.v11i4.3132.

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

Grandjean, Etienne. "Linear Time Algorithms and NP-Complete Problems." SIAM Journal on Computing 23, no. 3 (1994): 573–97. http://dx.doi.org/10.1137/s0097539791223206.

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

Zuckerman, David. "On Unapproximable Versions of $NP$-Complete Problems." SIAM Journal on Computing 25, no. 6 (1996): 1293–304. http://dx.doi.org/10.1137/s0097539794266407.

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

Dissertations / Theses on the topic "NP-complete problems"

1

Qasem, Mohamed. "Clustering solutions : a novel approach to solving NP-complete problems." Thesis, University of Southampton, 2010. https://eprints.soton.ac.uk/271282/.

Full text
Abstract:
In this thesis, we introduce a novel approach to solving MAX-SAT problems. This algorithm clusters good solutions, and restarts the search from the closest feasible configuration to the centroid of each cluster. We call this method Clustered-Landscape Guided Hopping (CLGH). In addition, where clustering does not provide an advantage due to the non-clustered landscape configuration, we use Averaged-Landscape Guided Hopping (ALGH). CLGH is shown to be highly efficient for finding good solutions of large MAX-SAT problems. Systematic studies of the landscape are presented to show that the success of clustering is due to the learning of large-scale structure of the fitness landscape. Previous studies conducted by other researchers analysed the relationship between local and global minima and provided an insight into the configuration of the landscape. It was found that local minima formed clusters around global ones. We expanded these analyses to cover the relationship between clusters, and found that local minima form many correlated yet distant clusters. In addition, we show the existence of a relationship between the size of the problem and the distance between local minima. To rule out other possibilities of this success we test several other population based algorithms, and compare their performances to clustering. In addition, we compare with solo-search algorithms. We show that this method is superior to all algorithms tested. CLGH produces results that might be produced by a solo-local search algorithm within 95% less time. However, this is not a standalone technique, and can be incorporated within other algorithms to further enhance their performance. A further application of clustering is carried out on the Traveling Salesman Problem (TSP) in the discrete domain, and Artificial Neural Networks (ANN) using backpropagation for the purpose of data classification in the continuous domain. Since TSP does not show a clustered landscape configuration we find that ALGH is an effective method for improving search results. Preliminary results are shown indicating that extensions of the proposed algorithm can give similar improvements on these hard optimisation problems.
APA, Harvard, Vancouver, ISO, and other styles
2

Петров, Сергій Олександрович, Сергей Александрович Петров, Serhii Oleksandrovych Petrov, Сергій Павлович Шаповалов, Сергей Павлович Шаповалов, and Serhii Pavlovych Shapovalov. "Application of the graph-theory to solve np-complete problems." Thesis, Видавництво СумДУ, 2007. http://essuir.sumdu.edu.ua/handle/123456789/14994.

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

Yu, Nuo 1983. "Fixed parameter tractable algorithms for optimal covering tours with turns." Thesis, McGill University, 2008. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=111595.

Full text
Abstract:
Many geometry problems can be solved by transformation to graph problems. Often, both the geometry version and graph version of the problem are NP-hard - and therefore not likely to be solved in polynomial time. One approach to solving these hard problems is to use fixed parameter tractable (FPT) algorithms. We present a framework for developing FPT algorithms for graph problems using dynamic programming, monadic second order logic of graphs, tree-width, and bidimensionality. We use this framework to obtain FPT results for covering tour problems on grid-graphs with turn costs. The results for these problems are not practical, but they demonstrate how the basic framework can be used to quickly obtain FPT results. We provide suggestions on further research to improve our FPT results and to apply our framework to obtain new FPT results.
APA, Harvard, Vancouver, ISO, and other styles
4

Maloney, John Harold. "Using constraints for user interface construction /." Thesis, Connect to this title online; UW restricted, 1991. http://hdl.handle.net/1773/6872.

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

Connelly, Abram. "Numerical evidence for phase transitions of NP-complete problems for instances drawn from Lévy-stable distributions." Thesis, University of St Andrews, 2011. http://hdl.handle.net/10023/2533.

Full text
Abstract:
Random NP-Complete problems have come under study as an important tool used in the analysis of optimization algorithms and help in our understanding of how to properly address issues of computational intractability. In this thesis, the Number Partition Problem and the Hamiltonian Cycle Problem are taken as representative NP-Complete classes. Numerical evidence is presented for a phase transition in the probability of solution when a modified Lévy-Stable distribution is used in instance creation for each. Numerical evidence is presented that show hard random instances exist near the critical threshold for the Hamiltonian Cycle problem. A choice of order parameter for the Number Partition Problem’s phase transition is also given. Finding Hamiltonian Cycles in Erdös-Rényi random graphs is well known to have almost sure polynomial time algorithms, even near the critical threshold. To the author’s knowledge, the graph ensemble presented is the first candidate, without specific graph structure built in, to generate graphs whose Hamiltonicity is intrinsically hard to determine. Random graphs are chosen via their degree sequence generated from a discretized form of Lévy-Stable distributions. Graphs chosen from this distribution still show a phase transition and appear to have a pickup in search cost for the algorithms considered. Search cost is highly dependent on the particular algorithm used and the graph ensemble is presented only as a potential graph ensemble to generate intrinsically hard graphs that are difficult to test for Hamiltonicity. Number Partition Problem instances are created by choosing each element in the list from a modified Lévy-Stable distribution. The Number Partition Problem has no known good approximation algorithms and so only numerical evidence to show the phase transition is provided without considerable focus on pickup in search cost for the solvers used. The failure of current approximation algorithms and potential candidate approximation algorithms are discussed.
APA, Harvard, Vancouver, ISO, and other styles
6

Ono, Satoshi. "In pursuit of NP-hard combinatorial optimization problems." Diss., Online access via UMI:, 2009.

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

Simone, James Nicholas. "NP user interface modeling." Diss., Online access via UMI:, 2009.

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

McDonald, Iain. "Symmetry in constraint programming." Thesis, University of St Andrews, 2004. http://hdl.handle.net/10023/14983.

Full text
Abstract:
Constraint programming is an invaluable tool for solving many of the complex NP-complete problems that we need solutions to. These problems can be easily described as Constraint Satisfaction Problems (CSPs) and then passed to constraint solvers: complex pieces of software written to solve general CSPs efficiently. Many of the problems we need solutions to are real world problems: planning (e.g. vehicle routing), scheduling (e.g. job shop schedules) and timetabling problems (e.g. staff rotas) to name but a few. In the real world, we place structure on objects to make them easier to deal with. This manifests itself as symmetry. The symmetry in these real world problems make them easier to deal with for humans. However, they lead to a great deal of redundancy when using computational methods of problem solving. Thus, this thesis examines some of the many aspects of utilising the symmetry of CSPs to reduce the amount of computation needed by constraint solvers. In this thesis we look at the ease of use of previous symmetry breaking methods. We introduce a new and novel method of describing the symmetries of CSPs. We look at previous methods of symmetry breaking and show how we can drastically reduce their computation while still breaking all symmetry. We give the first detailed investigation into the behaviour of breaking only subsets of all symmetry. We look at how this affects the performance of constraint solvers before discovering the properties of a good symmetry. We then present an original method for choosing the best symmetries to use. Finally, we look at areas of redundant computation in constraint solvers that no other research has examined. New ways of dealing with this redundancy are proposed with results of an example implementation which improves efficiency by several orders of magnitude.
APA, Harvard, Vancouver, ISO, and other styles
9

Chung, Yau-lin, and 鍾有蓮. "Optimality and approximability of the rectangle covering problem." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2004. http://hub.hku.hk/bib/B30294873.

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

Schmid, Markus L. "On the membership problem for pattern languages and related topics." Thesis, Loughborough University, 2012. https://dspace.lboro.ac.uk/2134/10304.

Full text
Abstract:
In this thesis, we investigate the complexity of the membership problem for pattern languages. A pattern is a string over the union of the alphabets A and X, where X := {x_1, x_2, x_3, ...} is a countable set of variables and A is a finite alphabet containing terminals (e.g., A := {a, b, c, d}). Every pattern, e.g., p := x_1 x_2 a b x_2 b x_1 c x_2, describes a pattern language, i.e., the set of all words that can be obtained by uniformly substituting the variables in the pattern by arbitrary strings over A. Hence, u := cacaaabaabcaccaa is a word of the pattern language of p, since substituting cac for x_1 and aa for x_2 yields u. On the other hand, there is no way to obtain the word u' := bbbababbacaaba by substituting the occurrences of x_1 and x_2 in p by words over A. The problem to decide for a given pattern q and a given word w whether or not w is in the pattern language of q is called the membership problem for pattern languages. Consequently, (p, u) is a positive instance and (p, u') is a negative instance of the membership problem for pattern languages. For the unrestricted case, i.e., for arbitrary patterns and words, the membership problem is NP-complete. In this thesis, we identify classes of patterns for which the membership problem can be solved efficiently. Our first main result in this regard is that the variable distance, i.e., the maximum number of different variables that separate two consecutive occurrences of the same variable, substantially contributes to the complexity of the membership problem for pattern languages. More precisely, for every class of patterns with a bounded variable distance the membership problem can be solved efficiently. The second main result is that the same holds for every class of patterns with a bounded scope coincidence degree, where the scope coincidence degree is the maximum number of intervals that cover a common position in the pattern, where each interval is given by the leftmost and rightmost occurrence of a variable in the pattern. The proof of our first main result is based on automata theory. More precisely, we introduce a new automata model that is used as an algorithmic framework in order to show that the membership problem for pattern languages can be solved in time that is exponential only in the variable distance of the corresponding pattern. We then take a closer look at this automata model and subject it to a sound theoretical analysis. The second main result is obtained in a completely different way. We encode patterns and words as relational structures and we then reduce the membership problem for pattern languages to the homomorphism problem of relational structures, which allows us to exploit the concept of the treewidth. This approach turns out be successful, and we show that it has potential to identify further classes of patterns with a polynomial time membership problem. Furthermore, we take a closer look at two aspects of pattern languages that are indirectly related to the membership problem. Firstly, we investigate the phenomenon that patterns can describe regular or context-free languages in an unexpected way, which implies that their membership problem can be solved efficiently. In this regard, we present several sufficient conditions and necessary conditions for the regularity and context-freeness of pattern languages. Secondly, we compare pattern languages with languages given by so-called extended regular expressions with backreferences (REGEX). The membership problem for REGEX languages is very important in practice and since REGEX are similar to pattern languages, it might be possible to improve algorithms for the membership problem for REGEX languages by investigating their relationship to patterns. In this regard, we investigate how patterns can be extended in order to describe large classes of REGEX languages.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "NP-complete problems"

1

Gogan, J. Vincent. Slice functions and the method of approximations. University of Toronto, Dept. of Computer Science, 1990.

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

Gogan, J. Vincent. Slice functions and the method of approximations. National Library of Canada, 1990.

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

Zado͡ian, K. V. Slozhnostʹ zadachi razbieni͡ia mnozhestva nuleĭ bulevoĭ funk͡tsii na nepereseka͡iushchies͡ia podmnozhestva. Akademi͡ia nauk SSSR, Vychislitelʹnyĭ ͡tsentr, 1988.

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

Scheffler, Petra. Linear-time algorithms for NP-complete problems restricted to partial k-trees. Akademie der Wissenschaften der DDR, Karl-Weierstrass-Institut für Mathematik, 1987.

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

Antoine, Lobstein, and Cohen Gerard, eds. Algorithmic complexityand communication problems. UCL Press, 1996.

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

Barthelemy, Jean-Pierre. Algorithmic complexity and communication problems. UCL Press, 1996.

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

Bogdanov, Andrej, and Luca Trevisan. Average-Case Complexity. Now Publishers Inc, 2006.

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

Cohen, G., J.-P. Barthelmy, and A. Lobstein. Algorithmic Complexity and Telecommunication Problems. CRC, 1997.

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

Fortnow, Lance. Golden Ticket: P, NP, and the Search for the Impossible. Princeton University Press, 2013.

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

Fortnow, Lance. Golden Ticket: P, Np, and the Search for the Impossible. Princeton University Press, 2013.

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

Book chapters on the topic "NP-complete problems"

1

Izadkhah, Habib. "P, NP, NP-Complete, and NP-Hard Problems." In Problems on Algorithms. Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-17043-0_15.

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

Kozen, Dexter C. "More NP-Complete Problems." In The Design and Analysis of Algorithms. Springer New York, 1992. http://dx.doi.org/10.1007/978-1-4612-4400-4_23.

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

Gawiejnowicz, Stanisław. "$$ \mathcal{NP} $$ -complete problems." In Monographs in Theoretical Computer Science. An EATCS Series. Springer Berlin Heidelberg, 2020. http://dx.doi.org/10.1007/978-3-662-59362-2_3.

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

Blum, Lenore, Felipe Cucker, Michael Shub, and Steve Smale. "The Class NP and NP-Complete Problems." In Complexity and Real Computation. Springer New York, 1998. http://dx.doi.org/10.1007/978-1-4612-0701-6_5.

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

Kozen, Dexter C. "Still More NP-Complete Problems." In The Design and Analysis of Algorithms. Springer New York, 1992. http://dx.doi.org/10.1007/978-1-4612-4400-4_24.

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

Huang, Siming. "Inverse Problems of Some NP-Complete Problems." In Algorithmic Applications in Management. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11496199_45.

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

Robson, J. M. "Parallel Algorithms for NP-Complete Problems." In Computer Science. Springer US, 1992. http://dx.doi.org/10.1007/978-1-4615-3422-8_31.

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

Myasnikov, Alexei, Vladimir Shpilrain, and Alexander Ushakov. "Generic complexity of NP-complete problems." In Non-commutative Cryptography and Complexity of Group-theoretic Problems. American Mathematical Society, 2011. http://dx.doi.org/10.1090/surv/177/12.

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

Mihara, Takashi, and Tetsuro Nishino. "Quantum computation and NP-complete problems." In Algorithms and Computation. Springer Berlin Heidelberg, 1994. http://dx.doi.org/10.1007/3-540-58325-4_203.

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

Reus, Bernhard. "How to Solve NP-Complete Problems." In Undergraduate Topics in Computer Science. Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-27889-6_21.

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

Conference papers on the topic "NP-complete problems"

1

Rossi, Bernardo, and Erhard Aichinger. "On NP-Complete Search Problems on Finite Algebras." In 2024 IEEE 54th International Symposium on Multiple-Valued Logic (ISMVL). IEEE, 2024. http://dx.doi.org/10.1109/ismvl60454.2024.00034.

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

Gungor, Seda Nur, and Mehmet Karakose. "A Quantum Computing Based Solution Approach for NP-Complete Problems." In 2025 29th International Conference on Information Technology (IT). IEEE, 2025. https://doi.org/10.1109/it64745.2025.10930248.

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

Popescu, Andrei, and Johannes P. Wallner. "Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach." 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/55.

Full text
Abstract:
Reasoning with defeasible and conflicting knowledge in an argumentative form is a key research field in computational argumentation. Reasoning under various forms of uncertainty is both a key feature and a challenging barrier for automated argumentative reasoning. It was shown that argumentative reasoning using probabilities faces in general high computational complexity, in particular for the so-called constellation approach. In this paper, we develop an algorithmic approach to overcome this obstacle. We refine existing complexity results and show that two main reasoning tasks, that of computing the probability of a given set being an extension and an argument being acceptable, diverge in their complexity: the former is #P-complete and the latter is #-dot-NP-complete when considering their underlying counting problems. We present an algorithm for the complex task of computing the probability of a set of arguments being a complete extension by using dynamic programming operating on tree-decompositions. An experimental evaluation shows promise of our approach.
APA, Harvard, Vancouver, ISO, and other styles
4

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 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, and other styles
5

Gurevich, Yuri. "Complete and incomplete randomized NP problems." In 28th Annual Symposium on Foundations of Computer Science. IEEE, 1987. http://dx.doi.org/10.1109/sfcs.1987.14.

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

Nishino, Tetsuro. "Quantum Computation and NP-Complete Problems." In Proceedings of the Second International Conference. WORLD SCIENTIFIC, 2000. http://dx.doi.org/10.1142/9789812792761_0009.

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

Ohya, Masanori, and Igor V. Volovich. "NP-complete Problems with Chaotic Dynamics." In Proceedings of the Second International Conference. WORLD SCIENTIFIC, 2000. http://dx.doi.org/10.1142/9789812792761_0012.

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

Sampath, G. "A graph for NP-complete problems." In the 35th Annual Southeast Regional Conference. ACM Press, 1997. http://dx.doi.org/10.1145/2817460.2817501.

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

Arabi, Bander Hassan. "Solving NP-complete Problems Using Genetic Algorithms." In 2016 UKSim-AMSS 18th International Conference on Computer Modelling and Simulation (UKSim). IEEE, 2016. http://dx.doi.org/10.1109/uksim.2016.65.

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

Harsha, A. Sri, P. Vijaya Kumar, Arumalla Nagaraju, K. Prakash Babu, N. R. Medikondu, and B. V. Dharmendra. "Mining knowledge for NP-complete scheduling problems." In CONTEMPORARY INNOVATIONS IN ENGINEERING AND MANAGEMENT. AIP Publishing, 2023. http://dx.doi.org/10.1063/5.0158474.

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

Reports on the topic "NP-complete problems"

1

Franco, John. Probabilistic Analysis of Algorithms for NP-Complete Problems. Defense Technical Information Center, 1986. http://dx.doi.org/10.21236/ada179537.

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

Franco, John. Probabilistic Analysis of Algorithms for NP-Complete Problems. Defense Technical Information Center, 1985. http://dx.doi.org/10.21236/ada168617.

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

Rappoport, Kevin J. Relative Approximation Bounds for NP-Complete Optimization Problems. Defense Technical Information Center, 1990. http://dx.doi.org/10.21236/ada236570.

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

Sertkaya, Barış. Some Computational Problems Related to Pseudo-intents. Technische Universität Dresden, 2008. http://dx.doi.org/10.25368/2022.169.

Full text
Abstract:
We investigate the computational complexity of several decision, enumeration and counting problems related to pseudo-intents. We show that given a formal context and a set of its pseudo-intents, checking whether this context has an additional pseudo-intent is in conp and it is at least as hard as checking whether a given simple hypergraph is saturated. We also show that recognizing the set of pseudo-intents is also in conp and it is at least as hard as checking whether a given hypergraph is the transversal hypergraph of another given hypergraph. Moreover, we show that if any of these two problems turns out to be conp-hard, then unless p = np, pseudo-intents cannot be enumerated in output polynomial time. We also investigate the complexity of finding subsets of a given Duquenne-Guigues Base from which a given implication follows. We show that checking the existence of such a subset within a specified cardinality bound is np-complete, and counting all such minimal subsets is #p-complete.
APA, Harvard, Vancouver, ISO, and other styles
5

Baader, Franz, and Barbara Morawska. SAT Encoding of Unification in EL. Technische Universität Dresden, 2010. http://dx.doi.org/10.25368/2022.177.

Full text
Abstract:
The Description Logic EL is an inexpressive knowledge representation language, which nevertheless has recently drawn considerable attention in the knowledge representation and the ontology community since, on the one hand, important inference problems such as the subsumption problem are polynomial. On the other hand, EL is used to define large biomedical ontologies. Unification in Description Logics has been proposed as a novel inference service that can, for example, be used to detect redundancies in ontologies. In a recent paper, we have shown that unification in EL is NP-complete, and thus of a complexity that is considerably lower than in other Description Logics of comparably restricted expressive power. In this paper, we introduce a new NP-algorithm for solving unification problem in EL, which is based on a reduction to satisfiability in propositional logic (SAT). The advantage of this new algorithm is, on the one hand, that it allows us to employ highly optimized state of the art SAT solverswhen implementing an EL-unification algorithm. On the other hand, this reduction provides us with a proof of the fact that EL-unification is in NP that is much simpler than the one given in our previous paper on EL-unification.
APA, Harvard, Vancouver, ISO, and other styles
6

Baader, Franz, and Ralf Küsters. Matching Concept Descriptions with Existential Restrictions Revisited. Aachen University of Technology, 1999. http://dx.doi.org/10.25368/2022.98.

Full text
Abstract:
An abridged version of this technical report has been submitted to KR 2000. Matching of concepts against patterns is a new inference task in Description Logics, which was originally motivated by applications of the CLASSIC system. Consequently, the work on this problem was until now mostly concerned with sublanguages of the Classic language, which does not allow for existential restrictions. Motivated by an application in chemical process engineering, which requires a description language with existential restrictions, this paper investigates the matching problem in Description Logics with existential restrictions. It turns out that existential restrictions make matching more complex in two respects. First, whereas matching in sublanguages of CLASSIC is polynomial, deciding the existence of matchers is an NP-complete problem in the presence of existential restrictions. Second, whereas in sublanguages of Classic solvable matching problems have a unique least matcher, this is not the case for languages with existential restrictions. Thus, it is not a priori clear which of the (possibly infinitely many) matchers should be returned by a matching algorithm. After determining the complexity of the decision problem, the present paper first investigates the question of what are 'interesting' sets of matchers, and then describes algorithms for computing these sets for the languages EL (which allows for conjunction and existential restrictions) and ALE (which additionally allows for value restrictions, primitive negation, and the bottom concept).
APA, Harvard, Vancouver, ISO, and other styles
7

Baader, Franz, and Ralf Küsters. Matching Concept Descriptions with Existential Restrictions Revisited. Aachen University of Technology, 1999. http://dx.doi.org/10.25368/2022.98.

Full text
Abstract:
An abridged version of this technical report has been submitted to KR 2000. Matching of concepts against patterns is a new inference task in Description Logics, which was originally motivated by applications of the CLASSIC system. Consequently, the work on this problem was until now mostly concerned with sublanguages of the Classic language, which does not allow for existential restrictions. Motivated by an application in chemical process engineering, which requires a description language with existential restrictions, this paper investigates the matching problem in Description Logics with existential restrictions. It turns out that existential restrictions make matching more complex in two respects. First, whereas matching in sublanguages of CLASSIC is polynomial, deciding the existence of matchers is an NP-complete problem in the presence of existential restrictions. Second, whereas in sublanguages of Classic solvable matching problems have a unique least matcher, this is not the case for languages with existential restrictions. Thus, it is not a priori clear which of the (possibly infinitely many) matchers should be returned by a matching algorithm. After determining the complexity of the decision problem, the present paper first investigates the question of what are 'interesting' sets of matchers, and then describes algorithms for computing these sets for the languages EL (which allows for conjunction and existential restrictions) and ALE (which additionally allows for value restrictions, primitive negation, and the bottom concept).
APA, Harvard, Vancouver, ISO, and other styles
8

Perk, Shimon, Maricarmen Garcia, Alexander Panshin, et al. Avian Influenza Virus H9N2: Characterization and Control Strategies. United States Department of Agriculture, 2007. http://dx.doi.org/10.32747/2007.7709882.bard.

Full text
Abstract:
Control of Avian Influenza (AI) infection is a highly topical subject of major economicimportance for the worldwide poultry industry at the national level and for international trade.H9N2 viruses are endemic in poultry throughout Asia and the Middle East, causing major losses inproduction. Moreover, these viruses pose wider threats since they have been isolated from bothswine and humans. At the same time, study of the AI viruses affords an opportunity to explore anumber of problems of intriguing scientific interest. The overall goal of this project was to developa sound control strategy for avian influenza subtype H9N2 viruses (AI H9N2) in commercialpoultry in Israel. The one-year feasibility study focused on two main goals, namely: to study themolecular characteristics of AI H9N2 circulating during the last seven years in Israel and todevelop tools enabling differentiation between the immune response to vaccination and infectionwith H9N2.Genetic and phylogenetic characterization of 29 selected AI H9N2 isolates (2000-2006)was performed by complete sequencing of hemagglutinin (HA), neuraminidase (NA), and all sixinternal genes [nucleoprotein (NP), polymerase basic 1 (PB1), polymerase basic 2 (PB2),polymerase acid (PA), matrix (M), and nonstructural (NS) genes]; comparative phylogenetic andgenetic analyses of these sequences; and comparative genetic analyses of deduced amino acidsequences of the HA, NA, NS1, and NS2 proteins. The major conclusions of the molecularanalyses were: (1) Israeli isolates, together with other H9N2 viruses isolated in Middle Eastcountries, comprise a single regional sublineage related to the G1-lineage. In addition, Israeliisolates subdivided into three different subgroups. Genetic analysis of these viruses suggests thatthey underwent divergent evolution paths.
APA, Harvard, Vancouver, ISO, and other styles
9

Baader, Franz, and Ralf Molitor. Rewriting Concepts Using Terminologies. Aachen University of Technology, 1999. http://dx.doi.org/10.25368/2022.92.

Full text
Abstract:
In this work we consider the inference problem of computing (minimal) rewritings of concept descriptions using defined concepts from a terminology. We introduce a general framework for this problem. For the small description logic FL₀, which provides us with conjunction and value restrictions, we show that the decision problem induced by the minimal rewriting problem is NP-complete.
APA, Harvard, Vancouver, ISO, and other styles
10

Baader, Franz, and Barbara Morawska. Matching with respect to general concept inclusions in the Description Logic EL. Technische Universität Dresden, 2014. http://dx.doi.org/10.25368/2022.205.

Full text
Abstract:
Matching concept descriptions against concept patterns was introduced as a new inference task in Description Logics (DLs) almost 20 years ago, motivated by applications in the Classic system. For the DL EL, it was shown in 2000 that the matching problem is NP-complete. It then took almost 10 years before this NP-completeness result could be extended from matching to unification in EL. The next big challenge was then to further extend these results from matching and unification without a TBox to matching and unification w.r.t. a general TBox, i.e., a finite set of general concept inclusions. For unification, we could show some partial results for general TBoxes that satisfy a certain restriction on cyclic dependencies between concepts, but the general case is still open. For matching, we solve the general case in this paper: we show that matching in EL w.r.t. general TBoxes is NP-complete by introducing a goal-oriented matching algorithm that uses non-deterministic rules to transform a given matching problem into a solved form by a polynomial number of rule applications. We also investigate some tractable variants of the matching problem.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'NP-complete problems' for particular source types:
Journal articles Dissertations / Theses
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