Добірка наукової літератури з теми "NP-complexity"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "NP-complexity".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "NP-complexity"
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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерелаДисертації з теми "NP-complexity"
Sempolinski, Peter. "Automatic Solutions of Logic Puzzles." Thesis, Boston College, 2009. http://hdl.handle.net/2345/690.
Повний текст джерела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
Simone, James Nicholas. "NP user interface modeling." Diss., Online access via UMI:, 2009.
Знайти повний текст джерела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.
Повний текст джерела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.
Maji, Nabanita. "An Interactive Tutorial for NP-Completeness." Thesis, Virginia Tech, 2015. http://hdl.handle.net/10919/52973.
Повний текст джерелаMaster of Science
Huang, Xiuzhen. "Parameterized complexity and polynomial-time approximation schemes." Texas A&M University, 2004. http://hdl.handle.net/1969.1/1446.
Повний текст джерела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.
Повний текст джерелаOno, Satoshi. "In pursuit of NP-hard combinatorial optimization problems." Diss., Online access via UMI:, 2009.
Знайти повний текст джерела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.
Повний текст джерела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
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.
Повний текст джерела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.
Повний текст джерелаFinancial support by the Swedish Foundation for Strategic Research (SSF) QC 20110915
Книги з теми "NP-complexity"
Gogan, J. Vincent. Slice functions and the method of approximations. Toronto, Ont: University of Toronto, Dept. of Computer Science, 1990.
Знайти повний текст джерелаGogan, J. Vincent. Slice functions and the method of approximations. Ottawa: National Library of Canada, 1990.
Знайти повний текст джерелаAntoine, Lobstein, and Cohen Gerard, eds. Algorithmic complexityand communication problems. London: UCL Press, 1996.
Знайти повний текст джерелаEfficient checking of polynomials and proofs and the hardness of approximation problems. Berlin: Springer₋Verlag, 1995.
Знайти повний текст джерелаBarthelemy, Jean-Pierre. Algorithmic complexity and communication problems. London: UCL Press, 1996.
Знайти повний текст джерелаZakrzewski, Marek. Wprowadzenie w teorię złożoności obliczeniowej: W kręgu zagadnienia P-NP. Wrocław: Wydawn. Politechniki Wrocławskiej, 1990.
Знайти повний текст джерелаP Np And Npcompleteness The Basics Of Computational Complexity. Cambridge University Press, 2010.
Знайти повний текст джерелаBogdanov, Andrej, and Luca Trevisan. Average-Case Complexity. Now Publishers Inc, 2006.
Знайти повний текст джерела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.
Повний текст джерелаCohen, G., J.-P. Barthelmy, and A. Lobstein. Algorithmic Complexity and Telecommunication Problems. CRC, 1997.
Знайти повний текст джерелаЧастини книг з теми "NP-complexity"
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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерелаÀ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.
Повний текст джерела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.
Повний текст джерелаТези доповідей конференцій з теми "NP-complexity"
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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерелаЗвіти організацій з теми "NP-complexity"
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.
Повний текст джерела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.
Повний текст джерелаZiesler, Pamela, and Claire Spalding. Statistical abstract: 2021. National Park Service, May 2022. http://dx.doi.org/10.36967/nrds-2293345.
Повний текст джерела