Relevant bibliographies by topics / NP-complexity

Contents

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

Academic literature on the topic 'NP-complexity'

Author: Grafiati
Published: 30 May 2022
Last updated: 31 May 2022

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-complexity.'

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-complexity"

1

Vardi, Moshe Y. "On P, NP, and computational complexity." Communications of the ACM 53, no. 11 (November 2010): 5. http://dx.doi.org/10.1145/1839676.1839677.

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

de Haan, Ronald, and Stefan Szeider. "Parameterized complexity classes beyond para-NP." Journal of Computer and System Sciences 87 (August 2017): 16–57. http://dx.doi.org/10.1016/j.jcss.2017.02.002.

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

Jiang, Yaozhi. "A Proof “P≠NP” for P vs. NP Problem by Multiple-Tape Turing-Machine." Journal of Mathematics Research 12, no. 4 (July 7, 2020): 1. http://dx.doi.org/10.5539/jmr.v12n4p1.

Full text
Abstract:
P vs. NP problem is very important research direction in computation complexity theory. In this paper author, by an engineer’s viewpoint, establishes universal multiple-tape Turing-machine and k-homogeneous multiple-tape Turing-machine, and by them we can obtain an unified mathematical model for algorithm-tree, from the unified model for algorithm-tree, we can conclude that computation complexity for serial processing NP problem if under parallel processing sometimes we can obtain P=NP  in time-complexity, but that will imply another NP, non-deterministic space-complexity NP, i.e., under serial processing P≠NP  in space-complexity, and the result is excluded the case of NP problem that there exists a faster algorithm to replace the brute-force algorithm, and hence we can proof that under parallel processing time-complexity is depended on space-complexity, and vice verse, within P vs. NP problem, this point is just the natural property of P vs. NP problem so that “P≠NP ”.
APA, Harvard, Vancouver, ISO, and other styles
4

Beame, Paul, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. "The Relative Complexity of NP Search Problems." Journal of Computer and System Sciences 57, no. 1 (August 1998): 3–19. http://dx.doi.org/10.1006/jcss.1998.1575.

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

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

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

Littman, M. L., J. Goldsmith, and M. Mundhenk. "The Computational Complexity of Probabilistic Planning." Journal of Artificial Intelligence Research 9 (August 1, 1998): 1–36. http://dx.doi.org/10.1613/jair.505.

Full text
Abstract:
We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the process of proving that certain planning problems are complete for NP^PP, we introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.
APA, Harvard, Vancouver, ISO, and other styles
7

Jukna, Stasys. "On the P versus NP intersected with co-NP question in communication complexity." Information Processing Letters 96, no. 6 (December 2005): 202–6. http://dx.doi.org/10.1016/j.ipl.2005.08.003.

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

Mulmuley, Ketan D. "On P vs. NP and geometric complexity theory." Journal of the ACM 58, no. 2 (April 2011): 1–26. http://dx.doi.org/10.1145/1944345.1944346.

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

Birget, J. C. "Inverse monoids associated with the complexity class NP." Semigroup Forum 98, no. 2 (January 3, 2019): 369–97. http://dx.doi.org/10.1007/s00233-018-9990-x.

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

Buss, Samuel R. "Towards NP–P via proof complexity and search." Annals of Pure and Applied Logic 163, no. 7 (July 2012): 906–17. http://dx.doi.org/10.1016/j.apal.2011.09.009.

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

Dissertations / Theses on the topic "NP-complexity"

1

Sempolinski, Peter. "Automatic Solutions of Logic Puzzles." Thesis, Boston College, 2009. http://hdl.handle.net/2345/690.

Full text
Abstract:
Thesis advisor: Howard Straubing
The use of computer programs to automatically solve logic puzzles is examined in this work. A typical example of this type of logic puzzle is one in which there are five people, with five different occupations and five different color houses. The task is to use various clues to determine which occupation and which color belongs to each person. The clues to this type of puzzle often are statements such as, ''John is not the barber,'' or ''Joe lives in the blue house.'' These puzzles range widely in complexity with varying numbers of objects to identify and varying numbers of characteristics that need to be identified for each object. With respect to the theoretical aspects of solving these puzzles automatically, this work proves that the problem of determining, given a logic puzzle, whether or not that logic puzzle has a solution is NP-Complete. This implies, provided that P is not equal to NP, that, for large inputs, automated solvers for these puzzles will not be efficient in all cases. Having proved this, this work proceeds to seek methods that will work for solving these puzzles efficiently in most cases. To that end, each logic puzzle can be encoded as an instance of boolean satisfiability. Two possible encodings are proposed that both translate logic puzzles into boolean formulas in Conjunctive Normal Form. Using a selection of test puzzles, a group of boolean satisfiability solvers is used to solve these puzzles in both encodings. In most cases, these simple solvers are successful in producing solutions efficiently
Thesis (BS) — Boston College, 2009
Submitted to: Boston College. College of Arts and Sciences
Discipline: College Honors Program
Discipline: Computer Science
APA, Harvard, Vancouver, ISO, and other styles
2

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

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

Ringh, Emil. "Low complexity algorithms for faster-than-Nyquistsign : Using coding to avoid an NP-hard problem." Thesis, KTH, Optimeringslära och systemteori, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-136936.

Full text
Abstract:
This thesis is an investigation of what happens when communication links are pushed towards their limits and the data-bearing-pulses are packed tighter in time than previously done. This is called faster-than-Nyquist (FTN) signaling and it will violate the Nyquist inter-symbol interference criterion, implying that the data-pulsesare no longer orthogonal and thus that the samples at the receiver will be dependent on more than one of the transmitted symbols. Inter-symbol interference (ISI) has occurred and the consequences of it are studied for the AWGN-channel model. Here it is shown that in order to do maximum likelihood estimation on these samples the receiver will face an NP-hard problem. The standard algorithm to make good estimations in the ISI case is the Viterbi algorithm, but applied on a block with N bits and interference among K bits thecomplexity is O(N *2K), hence limiting the practical applicability. Here, a precoding scheme is proposed together with a decoding that reduce the estimation complexity. By applying the proposed precoding/decoding to a data block of length N the estimation can be done in O(N2) operations preceded by a single off-line O(N3) calculation. The precoding itself is also done in O(N2)operations, with a single o ff-line operation of O(N3) complexity. The strength of the precoding is shown in simulations. In the first it was tested together with turbo codes of code rate 2/3 and block lengthof 6000 bits. When sending 25% more data (FTN) the non-precoded case needed about 2.5 dB higher signal-to-noise ratio (SNR) to have the same error rate as the precoded case. When the precoded case performed without any block errors, the non-precoded case still had a block error rate almost equal to 1. We also studied the scenario of transmission with low latency and high reliability. Here, 600 bits were transmitted with a code rate of 2/3, and hence the target was to communicate 400 bits of data. Applying FTN with doublepacking, that is transmitting 1200 bits during the same amount of time, it was possible to lower the code rate to 1/3 since only 400 bits of data was to be communicated. This technique greatly improves the robustness. When the FTN case performed error free, the classical Nyquist case still had a block error rate of 0.19. To reach error free performance the Nyquist case needed 1.25 dB higher SNR compared to the precoded FTN case with lower code rate.
Detta examensarbete handlar om vad som händer då kommunikationskanaler pressas till sin gräns och pulserna som bär data packas tätare i tiden. Detta kallas snabbare-än-Nyquist (FTN) och kommer att bryta mot Nyquists kriterium för intersymbolinterferens, vilket innebär att de databärande pulserna inte längre kommer vara ortogonala och att signalsamplen kommer vara beroende av mer än en skickad symbol. Det uppstår intersymbolinterferens (ISI) och dess konsekvenser studeras inom kanalmodellen AWGN. Vi visar att göra en maximum likelihood uppskattning baserat på dessa data är ett NP-svårt problem. Normalt används Viterbi algoritmen när man har ISI, men den har exponentiell komplexitet. På ett block med N symboler och interferens i storleken K symboler är komplexiteten O(N*2K) vilket gör att algoritmen är svår att använda i praktiska fall. Istället så föreslås en förkodning, som tillsammans med en avkodning reducerar komplexiteten. Kodningen appliceras blockvis och på ett block med N symboler är komplexiteten O(N2) för kodning/avkodning. Denna måste i båda fall föregås av en O(N3) beräkning, som dock behöver göras endast en gång.  Simuleringar visar den föreslagna kodningens fördelar. I den första simuleringen testades den ihop med turbokodning med blocklängd på 6000 bitar och en kodningsgrad på 2/3. När FTN användes för att skicka 25% mer data krävdes det cirka 2.5 dB högre signal-till-brus-förhållande (SNR) för att den icke förkodade signalen skulle ha samma felfrekvens som den förkodade. När det förkodade fallet presterade felfritt gjorde det oförkodade fel på nästan alla block.  Ett annat scenario som testades var det med korta koder, liten fördröjning och hög robusthet. I detta scenario skickades 600 bitar med en kodningsgrad på 2/3, alltså 400 bitar ren data. Genom att använda FTN med en dubbel packningsgrad, vilket innebär att 1200 bitar skickades under samma tid, var det möjligt att sänka kodningsgraden till 1/3, eftersom det bara var 400 bitar ren data som skulle överföras. Detta ökad robustheten i systemet ty då FTN fallet gjorde felfritt hade det klassiska Nyquist fallet fortfarande en felfrekvens på 0.19 för sina block. Det krävdes 1.25 dB högre SNR för Nyquist fallet att bli felfritt jämfört med FTN och lägre kodningsgrad.
APA, Harvard, Vancouver, ISO, and other styles
4

Maji, Nabanita. "An Interactive Tutorial for NP-Completeness." Thesis, Virginia Tech, 2015. http://hdl.handle.net/10919/52973.

Full text
Abstract:
A Theory of Algorithms course is essential to any Computer Science curriculum at both the undergraduate and graduate levels. It is also considered to be difficult material to teach or to learn. In particular the topics of Computational Complexity Theory, reductions, and the NP-Complete class of problems are considered difficult by students. Numerous algorithm visualizations (AVs) have been developed over the years to portray the dynamic nature of known algorithms commonly taught in undergraduate classes. However, to the best of our knowledge, the instructional material available for NP-Completeness is mostly static and textual, which does little to alleviate the complexity of the topic. Our aim is to improve the pedagogy of NP-Completeness by providing intuitive, interactive, and easy-to-understand visualizations for standard NP Complete problems, reductions, and proofs. In this thesis, we present a set of visualizations that we developed using the OpenDSA framework for certain NP-Complete problems. Our paradigm is a three step process. We first use an AV to illustrate a particular NP-Complete problem. Then we present an exercise to provide a first-hand experience with attempting to solve a problem instance. Finally, we present a visualization of a reduction as a part of the proof for NP-Completeness. Our work has been delivered as a collection of modules in OpenDSA, an interactive eTextbook system developed at Virginia Tech. The tutorial has been introduced as a teaching supplement in both a senior undergraduate and a graduate class. We present an analysis of the system use based on records of online interactions by students who used the tutorial. We also present results from a survey of the students.
Master of Science
APA, Harvard, Vancouver, ISO, and other styles
5

Huang, Xiuzhen. "Parameterized complexity and polynomial-time approximation schemes." Texas A&M University, 2004. http://hdl.handle.net/1969.1/1446.

Full text
Abstract:
According to the theory of NPcompleteness, many problems that have important realworld applications are NPhard. This excludes the possibility of solving them in polynomial time unless P=NP. A number of approaches have been proposed in dealing with NPhard problems, among them are approximation algorithms and parameterized algorithms. The study of approximation algorithms tries to find good enough solutions instead of optimal solutions in polynomial time, while parameterized algorithms try to give exact solutions when a natural parameter is small. In this thesis, we study the structural properties of parameterized computation and approximation algorithms for NP optimization problems. In particular, we investigate the relationship between parameterized complexity and polynomialtime approximation scheme (PTAS) for NP optimization problems. We give nice characterizations for two important subclasses in PTAS: Fully Polynomial Time Approximation Scheme (FPTAS) and Effcient Polynomial Time Approximation Scheme (EPTAS), using the theory of parameterized complexity. Our characterization of the class FPTAS has its advantages over the former characterizations, and our characterization of EPTAS is the first systematic investigation of this new but important approximation class. We develop new techniques to derive strong computational lower bounds for certain parameterized problems based on the theory of parameterized complexity. For example, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the clique problem could not be solved in time O(f (k)no(k)) for any function f . This lower bound matches the upper bound of the trivial algorithm that simply enumerates and checks all subsets of k vertices in the given graph of n vertices. We then extend our techniques to derive computational lower bounds for PTAS and EPTAS algorithms of NP optimization problems. We prove that certain NP optimization problems with known PTAS algorithms have no PTAS algorithms of running time O(f (1/Epsilon)no(1/Epsilon)) for any function f . Therefore, for these NP optimization problems, although theoretically they can be approximated in polynomial time to an arbitrarily small error bound Epsilon, they have no practically effective approximation algorithms for small error bound Epsilon. To our knowledge, this is the first time such lower bound results have been derived for PTAS algorithms. This seems to open a new direction for the study of computational lower bounds on the approximability of NP optimization problems.
APA, Harvard, Vancouver, ISO, and other styles
6

Beyersdorff, Olaf. "Disjoint NP-pairs and propositional proof systems." Doctoral thesis, [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=981087590.

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

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
8

Cornet, Alexis. "Algorithmes et résultats de complexité pour des problèmes de graphes avec contraintes additionnelles." Thesis, Université Clermont Auvergne‎ (2017-2020), 2018. http://www.theses.fr/2018CLFAC034/document.

Full text
Abstract:
Les problèmes de domination (dominant, dominant indépendant, ...) et de couverture (vertex-cover, arbre de Steiner, ...) sont NP-complets. Pour autant, pour la plupart de ces problèmes, il existe toujours une solution constructible en temps polynomial (potentiellement de valeur objective très mauvaise), ou au moins, il est possible de déterminer facilement (en temps polynomial) l'existence ou non d'une solution. Ces problèmes, initialement issus de situations réelles, sont des modélisations simplistes de ces situations. Nous ajoutons donc des contraintes additionnelles modélisant des contraintes pratiques plausibles : les conflits, des paires d'éléments ne pouvant faire simultanément partie d'une solution (modélisant des incompatibilités diverses), la connexité dans un second graphe (les éléments doivent pouvoir communiquer, et le graphe correspondant à ces liens de communication n'est pas forcément le même) et les obligations, des sous-ensembles d'éléments interdépendants devant être ajoutés simultanément à une solution. Notre but ici n'est pas de modéliser un problème réel précis, mais d'étudier la manière dont ces contraintes modifient la complexité des problèmes étudiés. Nous verrons que dans un grand nombre de cas, déterminer l'existence même d'une solution devient difficile, même sans se préoccuper de leur optimisation. Le problème du firefighter modélise des pompiers tentant de contenir un feu se propageant au tour par tour dans un graphe (potentiellement infini). Nous avons étudié ce problème en ajoutant des contraintes sur le déplacement des pompiers (une vitesse de déplacement limitée entre deux tours). Nous verrons que ces contraintes augmentent en général le nombre de pompiers nécessaires mais ne provoquent pas de changements aussi importants que dans les problèmes précédents
Domination problems (dominating set, independant dominating set, ...) as well as covering problems (vertex-cover, Steiner tree, ...) are NP-complete. However, for most of these problems, it is always possible to construct a (eventually bad) solution in polynomial time, or at least it is possible to determine whether a solution exists. Those problems originally came from industry, but are simplified modelizations of the real life problems. We add additional constraints modeling plausible practical constraints : conflicts which are pairs of elements that cannot apear simultaneously in a solution (to modelize various incompatibilities), connexity in a second graph (elements of the solution must be able to communicate, and the communication links are a second graph), and obligations which are subsets of interdependant vertices which must be added simultaneously in a solution.We don't aim to model a specific real-world problem, but to study how these plausible constraints affect the complexity of the studied problems. We will see that, in many cases, even determining the existence of a solution (regardless of its size) become hard. The firefighter problem models firefighters aiming to contain a fire spreading turn by turn in a (eventually infinite) graph. We studied this problem with the addition of deplacement constraints for the firefighters (a limited moving speed between turns). We will see that, most of the time, this constraint increase the number of firefighters necessary to contain the fire, but does not trigger such major change as constraints studied in the others problems
APA, Harvard, Vancouver, ISO, and other styles
9

Serédi, Silvester. "Evoluční algoritmy v úloze booleovské splnitelnosti." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2013. http://www.nusl.cz/ntk/nusl-236224.

Full text
Abstract:
The goal of this Master's Thesis is finding a SAT solving heuristic by the application of an evolutionary algorithm. This thesis surveys various approaches used in SAT solving and some variants of evolutionary algorithms that are relevant to this topic. Afterwards the implementation of a linear genetic programming system that searches for a suitable heuristic for SAT problem instances is described, together with the implementation of a custom SAT solver which expoloits the output of the genetic program. Finally, the achieved results are summarized.
APA, Harvard, Vancouver, ISO, and other styles
10

Fallgren, Mikael. "Optimization of Joint Cell, Channel and Power Allocation in Wireless Communication Networks." Doctoral thesis, KTH, Optimeringslära och systemteori, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-40274.

Full text
Abstract:
In this thesis we formulate joint cell, channel and power allocation problems within wireless communication networks. The objectives are to maximize the user with mini- mum data throughput (Shannon capacity) or to maximize the total system throughput, referred to as the max-min and max-sum problem respectively. The complexity is stud- ied together with proposed optimization- and heuristic-based approaches. In the first paper an overall joint cell, channel and power allocation max-min prob- lem is formulated. We show that the decision problem is NP-hard and that the op- timization problem is not approximable unless P is equal to NP, for instances with a sufficiently large number of channels. Further, it follows that for a feasible binary cell and channel allocation, the remaining continuous power allocation optimization problem is still not approximable unless P is equal to NP. In addition, it is shown that first-order optimality conditions give global optimum of the single channel power al- location optimization problem, although the problem is in general not convex. In the following two papers heuristics for solving the overall problem are proposed. In the second paper we consider the single channel problem with convex combinations of the max-min and the max-sum objective functions. This variable utility provides the ability of tuning the amount of fairness and total throughput. The third paper investi- gates the multiple channel setting. On a system with three cells, eight mobile users and three channels, we perform an exhaustive search over feasible cell and channel alloca- tions. The exhaustive search is then compared to the less computationally expensive heuristic approaches, presenting potential earnings to strive for. A conclusion is that several of the proposed heuristics perform very well. The final paper incorporates fixed relay stations into the overall joint cell, channel and power allocation max-min problem. The complexity is inherited from the formula- tion without relay stations. Further, we propose a heuristic channel allocation approach that shows good performance, compared to an optimization based approach, in numer- ical simulations on the relay setting.
Financial support by the Swedish Foundation for Strategic Research (SSF) QC 20110915
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "NP-complexity"

1

Gogan, J. Vincent. Slice functions and the method of approximations. Toronto, Ont: 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. Ottawa: National Library of Canada, 1990.

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

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

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

Efficient checking of polynomials and proofs and the hardness of approximation problems. Berlin: Springer₋Verlag, 1995.

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

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

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

Zakrzewski, Marek. Wprowadzenie w teorię złożoności obliczeniowej: W kręgu zagadnienia P-NP. Wrocław: Wydawn. Politechniki Wrocławskiej, 1990.

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

P Np And Npcompleteness The Basics Of Computational Complexity. Cambridge University Press, 2010.

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

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

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

Percus, Allon, Gabriel Istrate, and Cristopher Moore, eds. Computational Complexity and Statistical Physics. Oxford University Press, 2005. http://dx.doi.org/10.1093/oso/9780195177374.001.0001.

Full text
Abstract:
Computer science and physics have been closely linked since the birth of modern computing. In recent years, an interdisciplinary area has blossomed at the junction of these fields, connecting insights from statistical physics with basic computational challenges. Researchers have successfully applied techniques from the study of phase transitions to analyze NP-complete problems such as satisfiability and graph coloring. This is leading to a new understanding of the structure of these problems, and of how algorithms perform on them. Computational Complexity and Statistical Physics will serve as a standard reference and pedagogical aid to statistical physics methods in computer science, with a particular focus on phase transitions in combinatorial problems. Addressed to a broad range of readers, the book includes substantial background material along with current research by leading computer scientists, mathematicians, and physicists. It will prepare students and researchers from all of these fields to contribute to this exciting area.
APA, Harvard, Vancouver, ISO, and other styles
10

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
More sources

Book chapters on the topic "NP-complexity"

1

Arvind, Vikraman. "Complexity Theory Basics: NP and NL." In Perspectives in Computational Complexity, 1–22. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-05446-9_1.

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

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

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

Lassaigne, Richard, and Michel de Rougemont. "Time complexity: the classes P and NP." In Logic and Complexity, 191–212. London: Springer London, 2004. http://dx.doi.org/10.1007/978-0-85729-392-3_12.

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

Fleszar, Krzysztof, Christian Glaßer, Fabian Lipp, Christian Reitwießner, and Maximilian Witek. "Structural Complexity of Multiobjective NP Search Problems." In LATIN 2012: Theoretical Informatics, 338–49. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-29344-3_29.

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

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

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

de Haan, Ronald, and Stefan Szeider. "Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP." In Lecture Notes in Computer Science, 217–29. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. http://dx.doi.org/10.1007/978-3-662-46078-8_18.

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

Mulmuley, Ketan, and Milind Sohoni. "Geometric Complexity Theory, P vs. NP and Explicit Obstructions." In Advances in Algebra and Geometry, 239–61. Gurgaon: Hindustan Book Agency, 2003. http://dx.doi.org/10.1007/978-93-86279-12-5_20.

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

Jenner, Birgit, and Jacobo Torán. "The Complexity of Obtaining Solutions for Problems in NP and NL." In Complexity Theory Retrospective II, 155–78. New York, NY: Springer New York, 1997. http://dx.doi.org/10.1007/978-1-4612-1872-2_7.

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

Àlvarez, Carme, Josep Díaz, and Jacobo Torán. "Complexity classes with complete problems between P and NP-C." In Fundamentals of Computation Theory, 13–24. Berlin, Heidelberg: Springer Berlin Heidelberg, 1989. http://dx.doi.org/10.1007/3-540-51498-8_2.

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

Gruber, Hermann, and Markus Holzer. "Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP." In Developments in Language Theory, 205–16. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-73208-2_21.

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

Conference papers on the topic "NP-complexity"

1

Zhou, Xianjun, Qian Zhang, Danwen Wu, and Zhizhi Yan. "NP-complexity solved wireless spectrum auctions." In 2010 2nd IEEE International Conference on Information Management and Engineering. IEEE, 2010. http://dx.doi.org/10.1109/icime.2010.5478170.

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

Beame, Paul, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. "The relative complexity of NP search problems." In the twenty-seventh annual ACM symposium. New York, New York, USA: ACM Press, 1995. http://dx.doi.org/10.1145/225058.225147.

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

Samorodnitsky, Alex, and Luca Trevisan. "A PCP characterization of NP with optimal amortized query complexity." In the thirty-second annual ACM symposium. New York, New York, USA: ACM Press, 2000. http://dx.doi.org/10.1145/335305.335329.

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

Cozman, Fabio Gagliardi, and Denis Deratani Mauá. "The Finite Model Theory of Bayesian Networks: Descriptive Complexity." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/727.

Full text
Abstract:
We adapt the theory of descriptive complexity to Bayesian networks, to quantify the expressivity of specifications based on predicates and quantifiers. We show that Bayesian network specifications that employ first-order quantification capture the complexity class PP; by allowing quantification over predicates, the resulting Bayesian network specifications capture each class in the hierarchy PP^(NP^...^NP), a result that does not seem to have equivalent in the literature.
APA, Harvard, Vancouver, ISO, and other styles
5

Faliszewski, Piotr, Alexander Karpov, and Svetlana Obraztsova. "The Complexity of Election Problems with Group-Separable Preferences." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/29.

Full text
Abstract:
We analyze the complexity of several NP-hard election-related problems under the assumptions that the voters have group-separable preferences. We show that under this assumption our problems typically remain NP-hard, but we provide more efficient algorithms if additionally the clone decomposition tree is of moderate height.
APA, Harvard, Vancouver, ISO, and other styles
6

Souza, Uéverton, Fábio Protti, Maise Da Silva, and Dieter Rautenbach. "Multivariate Investigation of NP-Hard Problems: Boundaries Between Parameterized Tractability and Intractability." In XXVIII Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/ctd.2015.9996.

Full text
Abstract:
In this thesis we present a multivariate investigation of the complexity of some NP-hard problems, i.e., we first develop a systematic complexity analysis of these problems, defining its subproblems and mapping which one belongs to each side of an “imaginary boundary” between polynomial time solvability and intractability. After that, we analyze which sets of aspects of these problems are sources of their intractability, that is, subsets of aspects for which there exists an algorithm to solve the associated problem, whose non-polynomial time complexity is purely a function of those sets. Thus, we use classical and parameterized complexity in an alternate and complementary approach, to show which subproblems of the given problems are NP-hard and latter to diagnose for which sets of parameters the problems are fixed-parameter tractable, or in FPT. This thesis exhibits a classical and parameterized complexity analysis of different groups of NP-hard problems. The addressed problems are divided into four groups of distinct nature, in the context of data structures, combinatorial games, and graph theory: (I) and/or graph solution and its variants; (II) flooding-filling games; (III) problems on P3-convexity; (IV) problems on induced matchings.
APA, Harvard, Vancouver, ISO, and other styles
7

de Weerdt, Mathijs, Michael Albert, Vincent Conitzer, and Koos van der Linden. "Complexity of Scheduling Charging in the Smart Grid." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/658.

Full text
Abstract:
The problem of optimally scheduling the charging demand of electric vehicles within the constraints of the electricity infrastructure is called the charge scheduling problem. The models of the charging speed, horizon, and charging demand determine the computational complexity of the charge scheduling problem. We show that for about 20 variants the problem is either in P or weakly NP-hard and dynamic programs exist to compute optimal solutions. About 10 other variants of the problem are strongly NP-hard, presenting a potentially significant obstacle to their use in practical situations of scale. An experimental study establishes up to what parameter values the dynamic programs can determine optimal solutions in a couple of minutes.
APA, Harvard, Vancouver, ISO, and other styles
8

Apt, Krzysztof R., Eryk Kopczyński, and Dominik Wojtczak. "On the Computational Complexity of Gossip Protocols." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/106.

Full text
Abstract:
Gossip protocols deal with a group of communicating agents, each holding a private information, and aim at arriving at a situation in which all the agents know each other secrets. Distributed epistemic gossip protocols are particularly simple distributed programs that use formulas from an epistemic logic. Recently, the implementability of these distributed protocols was established (which means that the evaluation of these formulas is decidable), and the problems of their partial correctness and termination were shown to be decidable, but their exact computational complexity was left open. We show that for any monotonic type of calls the implementability of a distributed epistemic gossip protocol is a P^{NP}_{||}-complete problem, while the problems of its partial correctness and termination are in coNP^{NP}.
APA, Harvard, Vancouver, ISO, and other styles
9

Chen, Jiehua, Robert Ganian, and Thekla Hamm. "Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/21.

Full text
Abstract:
We investigate the following many-to-one stable matching problem with diversity constraints (SMTI-DIVERSE): Given a set of students and a set of colleges which have preferences over each other, where the students have overlapping types, and the colleges each have a total capacity as well as quotas for individual types (the diversity constraints), is there a matching satisfying all diversity constraints such that no unmatched student-college pair has an incentive to deviate? SMTI-DIVERSE is known to be NP-hard. However, as opposed to the NP-membership claims in the literature [Aziz et al., AAMAS 2019; Huang,SODA 2010], we prove that it is beyond NP: it is complete for the complexity class Σ^P_2. In addition, we provide a comprehensive analysis of the problem’s complexity from the viewpoint of natural restrictions to inputs and obtain new algorithms for the problem.
APA, Harvard, Vancouver, ISO, and other styles
10

Liu, Jin-Fan, and Karim A. Abdel-Malek. "The Problem of Scheduling Parallel Computations of Multibody Dynamic Analysis Is NP-Hard." In ASME 1996 Design Engineering Technical Conferences and Computers in Engineering Conference. American Society of Mechanical Engineers, 1996. http://dx.doi.org/10.1115/96-detc/mech-1150.

Full text
Abstract:
Abstract A formulation of a graph problem for scheduling parallel computations of multibody dynamic analysis is presented. The complexity of scheduling parallel computations for a multibody dynamic analysis is studied. The problem of finding a shortest critical branch spanning tree is described and transformed to a minimum radius spanning tree, which is solved by an algorithm of polynomial complexity. The problems of shortest critical branch minimum weight spanning tree (SCBMWST) and the minimum weight shortest critical branch spanning tree (MWSCBST) are also presented. Both problems are shown to be NP-hard by proving that the bounded critical branch bounded weight spanning tree (BCBBWST) problem is NP-complete. It is also shown that the minimum computational cost spanning tree (MCCST) is at least as hard as SCBMWST or MWSCBST problems, hence itself an NP-hard problem. A heuristic approach to solving these problems is developed and implemented, and simulation results are discussed.
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "NP-complexity"

1

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
2

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
3

Ziesler, Pamela, and Claire Spalding. Statistical abstract: 2021. National Park Service, May 2022. http://dx.doi.org/10.36967/nrds-2293345.

Full text
Abstract:
In 2021, recreation visits to National Park Service (NPS) sites rebounded from the COVID-19 pandemic-driven low visitation of 2020 and climbed to 297,115,406 recreation visits. This is an increase of 60 million recreation visits (+25.3%) from 2020 and a decrease of 30 million recreation visits (-9.3%) from 2019. Recreation visitor hours were 1,356,657,749 – a 28.6% increase from 2020 and a 5.1% decrease from 2019. Total overnight stays followed a similar pattern with 12,745,455 overnight stays – up 4.7 million (+58.5%) from 2020 and down 1.1 million (-8%) from 2019. Five parks were added to the reporting system in 2021: Alagnak Wild River in Alaska, Camp Nelson National Monument in Kentucky, Medgar and Myrlie Evers Home National Monument in Mississippi, Tule Springs Fossil Beds National Monument in Nevada, and World War I Memorial in Washington, D.C. These parks were responsible for over 629,000 recreation visits in 2021. Factors influencing visits to National Park System units in 2021 include: continuing closures and limited capacities due to COVID-19 mitigation at some parks, temporary closures for wildland fires in 2021 (eleven parks), severe regional smoke/haze from ongoing wildland fires throughout the summer and early autumn affecting parks in the western half and northern tier of states in the continental U.S., two hurricanes in 2021 – both in August – impacted visitation: Hurricane Henri caused temporary closures of some parks in the northeast and Hurricane Ida caused temporary closures of parks along the Gulf Coast and generated some heavy flooding in the northeast, hurricanes and wildland fires in previous years resulting in lingering closures, most notably Hurricanes Irma and Maria in 2017, the Carr and Woolsey Fires in 2018, Hurricane Dorian in 2019, the Caldwell, Cameron Peak, East Troublesome, and Woodward Fires in 2020, and Hurricane Sally in 2020. Forty-four parks set a record for recreation visits in 2021 and 6 parks broke a record they set in 2020. See Appendix A for a list of record parks. The number of reporting units with over 10 million recreation visits was the same as in recent years (3 parks) and 73 parks had over 1 million recreation visits. Twenty-five percent of total recreation visits occurred in the top 8 parks and fifty percent of total visitation occurred in the top 25 parks. Several parks passed annual visitation milestones including Capulin Volcano NM which passed 100,000 annual recreation visits for the first time, Big Bend NP and Devils Tower NM which each passed 500,000 annual recreation visits for the first time, and Zion NP which passed 5 million visits for the first time. Other parks passed milestones for accumulated recreation visits including Hamilton Grange NMEM (1968-2021) and Palo Alto Battlefield NHP (2003-2021) each passing 1 million total recreation visits, Voyageurs NP (1976-2021) passing 10 million total recreation visits, and Hot Springs NP (1904-2021) passing 100 million total recreation visits. Population center designations were updated in 2021 to reflect overlap of park boundaries with statistical areas from the 2020 U.S. Census. Many population center changes reflect increases in local population as indicated by parks changing from rural to outlying or from outlying to suburban. Other changes reflect increasing complexity in population density as parks changed from a single designation, such as rural or suburban, to a mixed designation. See the Definitions section for population center definitions and Table B.1 for previous and updated population center designations by park. In the pages that follow, a series of tables and figures display visitor use data for calendar year 2021. By documenting these visits across the National Park System, the NPS Statistical Abstract offers a historical record of visitor use in parks and provides NPS staff and partners with a useful tool for effective management and planning. In 2021, 394 of 423 NPS units...
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'NP-complexity' for particular source types:
Journal articles Dissertations / Theses Books
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