Log in

Relevant bibliographies by topics / NP-complete problems / Journal articles

To see the other types of publications on this topic, follow the link: NP-complete problems.

Journal articles on the topic 'NP-complete problems'

Author: Grafiati

Published: 4 June 2021

Last updated: 26 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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

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

11

Shaked, Natan T., Stephane Messika, Shlomi Dolev, and Joseph Rosen. "Optical solution for bounded NP-complete problems." Applied Optics 46, no. 5 (2007): 711. http://dx.doi.org/10.1364/ao.46.000711.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Rhee, Wansoo T., and Michel Talagrand. "Martingale Inequalities, Interpolation and NP-Complete Problems." Mathematics of Operations Research 14, no. 1 (1989): 91–96. http://dx.doi.org/10.1287/moor.14.1.91.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

HAYASHI, S., and M. TADA. "New NP-Complete Problems Associated with Lattices." IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E90-A, no. 5 (2007): 941–48. http://dx.doi.org/10.1093/ietfec/e90-a.5.941.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Livne, Noam. "All Natural NP-Complete Problems Have Average-Case Complete Versions." computational complexity 19, no. 4 (2010): 477–99. http://dx.doi.org/10.1007/s00037-010-0298-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Kotukh, Y., G. Khalimov, M. Korobchynskyi, et al. "Research horizons in group cryptography in the context of post-quantum cryptosystems development." Radiotekhnika, no. 216 (March 20, 2024): 62–72. http://dx.doi.org/10.30837/rt.2024.1.216.05.

Full text

Abstract:

Asymmetric cryptography relies on the principle of ease of calculation and complexity of one-sided functions’ inversion. These functions can be easily implemented, but inverting them is computationally difficult. In this context, NP-complete problems are ideal candidates for the role of such functions in asymmetric cryptography, since generating their cases is easy, but finding solutions is difficult. However, the practical application of NP-complete problems has certain limitations, in particular due to difficulties in creating problems that would be complex on average. Although an NP-complet

APA, Harvard, Vancouver, ISO, and other styles

16

da Costa, N. C. A., and F. A. Doria. "On the O’Donnell Algorithm for NP-Complete Problems." Review of Behavioral Economics 3, no. 2 (2016): 221–42. http://dx.doi.org/10.1561/105.00000048.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Nakajima, T., H. Yoshida, Y. Sakai, and A. Suyama. "Solution of NP-complete problems on DNA computer." Seibutsu Butsuri 39, supplement (1999): S205. http://dx.doi.org/10.2142/biophys.39.s205_4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Černý, Vladimír. "Quantum computers and intractable (NP-complete) computing problems." Physical Review A 48, no. 1 (1993): 116–19. http://dx.doi.org/10.1103/physreva.48.116.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Aaronson, Scott. "Guest Column: NP-complete problems and physical reality." ACM SIGACT News 36, no. 1 (2005): 30–52. http://dx.doi.org/10.1145/1052796.1052804.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Leyton-Brown, Kevin, Holger H. Hoos, Frank Hutter, and Lin Xu. "Understanding the empirical hardness of NP -complete problems." Communications of the ACM 57, no. 5 (2014): 98–107. http://dx.doi.org/10.1145/2594413.2594424.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Demaine, Erik D., Alejandro López-Ortiz, and J. Ian Munro. "On universally easy classes for NP-complete problems." Theoretical Computer Science 304, no. 1-3 (2003): 471–76. http://dx.doi.org/10.1016/s0304-3975(03)00286-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Ohya, Masanori, and Igor V. Volovich. "New quantum algorithm for studying NP-complete problems." Reports on Mathematical Physics 52, no. 1 (2003): 25–33. http://dx.doi.org/10.1016/s0034-4877(03)90002-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Martínez-Pérez, Israel Marck, and Karl-Heinz Zimmermann. "Parallel bioinspired algorithms for NP complete graph problems." Journal of Parallel and Distributed Computing 69, no. 3 (2009): 221–29. http://dx.doi.org/10.1016/j.jpdc.2008.06.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Ruiz-Vanoye, Jorge A., Joaquín Pérez-Ortega, Rodolfo A. Pazos R., et al. "Survey of polynomial transformations between NP-complete problems." Journal of Computational and Applied Mathematics 235, no. 16 (2011): 4851–65. http://dx.doi.org/10.1016/j.cam.2011.02.018.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Rao, Michaël. "Solving some NP-complete problems using split decomposition." Discrete Applied Mathematics 156, no. 14 (2008): 2768–80. http://dx.doi.org/10.1016/j.dam.2007.11.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Sinchev, B., A. B. Sinchev, Zh Akzhanova, Y. Issekeshev, and A. M. Mukhanova. "POLYNOMIAL TIME ALGORITHMS FOR SOLVING NP-COMPLETE PROBLEMS." NEWS of National Academy of Sciences of the Republic of Kazakhstan 3, no. 441 (2020): 97–101. http://dx.doi.org/10.32014/2020.2518-170x.59.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Chung, Moon Jung, W. Michael Evangelist, and Ivan Hal Sudborough. "Complete problems for space bounded subclasses of NP." Acta Informatica 22, no. 4 (1985): 379–95. http://dx.doi.org/10.1007/bf00288774.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Helman, Paul. "A family of NP-complete data aggregation problems." Acta Informatica 26, no. 5 (1989): 485–99. http://dx.doi.org/10.1007/bf00289148.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Colbourn, Charles J., W. L. Kocay, and D. R. Stinson. "Some NP-complete problems for hypergraph degree sequences." Discrete Applied Mathematics 14, no. 3 (1986): 239–54. http://dx.doi.org/10.1016/0166-218x(86)90028-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Du, Ding-Zhu, and Ronald V. Book. "On inefficient special cases of NP-complete problems." Theoretical Computer Science 63, no. 3 (1989): 239–52. http://dx.doi.org/10.1016/0304-3975(89)90015-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Bach, Eric, Anne Condon, Elton Glaser, and Celena Tanguay. "DNA Models and Algorithms for NP-Complete Problems." Journal of Computer and System Sciences 57, no. 2 (1998): 172–86. http://dx.doi.org/10.1006/jcss.1998.1586.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Borchert, Bernd, Lane A. Hemaspaandra, and Jörg Rothe. "Restrictive Acceptance Suffices for Equivalence Problems." LMS Journal of Computation and Mathematics 3 (2000): 86–95. http://dx.doi.org/10.1112/s146115700000022x.

Full text

Abstract:

AbstractOne way of suggesting that an NP problem may not be NP-complete is to show that it is in the promise class UP. We propose an analogous new method—weaker in strength of evidence but more broadly applicable—for suggesting that concrete NP problems are not NP-complete. In particular, we introduce the promise class EP, the subclass of NP consisting of those languages accepted by NP machines that, when they accept, always have a number of accepting paths that is a power of two. We show that FewP, bounded ambiguity polynomial time (which contains UP), is contained in EP. The class EP applies

APA, Harvard, Vancouver, ISO, and other styles

33

Orellana-Martín, David, Antonio Ramírez-de-Arellano, José Antonio Andreu-Guzmán, Álvaro Romero-Jiménez, and Mario J. Pérez-Jiménez. "A Protocol for Solutions to DP-Complete Problems through Tissue Membrane Systems." Mathematics 11, no. 13 (2023): 2797. http://dx.doi.org/10.3390/math11132797.

Full text

Abstract:

Considering a class R comprising recognizer membrane systems with the capability of providing polynomial-time and uniform solutions for NP-complete problems (referred to as a “presumably efficient” class), the corresponding polynomial-time complexity class PMCR encompasses both the NP and co – NP classes. Specifically, when R represents the class of recognizer presumably efficient cell-like P systems that incorporate object evolution rules, communication rules, and dissolution rules, PMCR includes both the DP and co – DP classes. Here, DP signifies the class of languages that can be expressed

APA, Harvard, Vancouver, ISO, and other styles

34

Riege, Tobias, and Jörg Rothe. "Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem." JUCS - Journal of Universal Computer Science 12, no. (6) (2006): 725–45. https://doi.org/10.3217/jucs-012-06-0725.

Full text

Abstract:

NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the domatic number problem. The deterministic time bounds are compared with the corresponding time bounds of randomized algorithms, which often run faster but only at the cost of having a certain error probability.

APA, Harvard, Vancouver, ISO, and other styles

35

LEVIN, LEONID A., and RAMARATHNAM VENKATESAN. "An Average Case NP-complete Graph Colouring Problem." Combinatorics, Probability and Computing 27, no. 5 (2018): 808–28. http://dx.doi.org/10.1017/s0963548318000123.

Full text

Abstract:

NP-complete problems should be hard on some instances but those may be extremely rare. On generic instances many such problems, especially related to random graphs, have been proved to be easy. We show the intractability of random instances of a graph colouring problem: this graph problem is hard on average unless all NP problems under all samplable (i.e. generatable in polynomial time) distributions are easy. Worst case reductions use special gadgets and typically map instances into a negligible fraction of possible outputs. Ours must output nearly random graphs and avoid any super-polynomial

APA, Harvard, Vancouver, ISO, and other styles

36

Zayko, Y. N. "Solution of Np-Complete Problems on the Landauer’s Computer." International Journal of Mathematical Research 2, no. 2 (2013): 11–16. http://dx.doi.org/10.18488/journal.24/2013.2.2/24.2.11.16.

Full text

Abstract:

In this article a new kind of classical computer – Landauer’s one is suggested. It is a computer which operates in agreement with Landauer’s Principle (LP). It is characterized by clock rate which is exponentially large in comparison with clock rate of classical computers. It leads to the possibility to use Landauer’s computer for solving of NP-complete problems in appropriate, i.e. polynomial time with the help of ordinary searching algorithms.

APA, Harvard, Vancouver, ISO, and other styles

37

Furuya, Shinji, and Satoru Miyano. "NP-complete Problems on Label Updating Calculation in ATMS." Bulletin of informatics and cybernetics 25, no. 1/2 (1991): 1–5. http://dx.doi.org/10.5109/3146.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

A. Filar, Jerzy, Michael Haythorpe, and Richard Taylor. "Linearly-growing reductions of Karp's 21 NP-complete problems." Numerical Algebra, Control & Optimization 8, no. 1 (2018): 1–16. http://dx.doi.org/10.3934/naco.2018001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Подвальный, С. Л., and Е. М. Васильев. "MATRIX REPLICATION IN NP-COMPLETE PROBLEMS OF COMBINATORIAL OPTIMIZATION." ВЕСТНИК ВОРОНЕЖСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА, no. 4(-) (August 30, 2022): 7–14. http://dx.doi.org/10.36622/vstu.2022.18.4.001.

Full text

Abstract:

Ставится задача повышения вероятности нахождения глобального экстремума в NP-полных задачах комбинаторной оптимизации большой размерности. Показано, что комбинаторный характер формирования вариантов решений приводит к изолированному расположению глобального экстремума в области определения функции цели. Указанное обстоятельство существенно снижает эффективность эволюционных алгоритмов поиска, основанных на воспроизведении свойств наследственности и изменчивости в биологической эволюции. В связи с этим предложено ввести в упомянутые алгоритмы механизм матричной репликации. В соответствии с гипо

APA, Harvard, Vancouver, ISO, and other styles

40

Fournier, Hervé. "Sparse NP-complete problems over the reals with addition." Theoretical Computer Science 255, no. 1-2 (2001): 607–10. http://dx.doi.org/10.1016/s0304-3975(00)00203-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Zimmermann, Karl-Heinz. "Efficient DNA sticker algorithms for NP-complete graph problems." Computer Physics Communications 144, no. 3 (2002): 297–309. http://dx.doi.org/10.1016/s0010-4655(02)00270-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Gasarch, W. I., M. W. Krentel, and K. J. Rappoport. "OptP as the normal behavior of NP-complete problems." Mathematical Systems Theory 28, no. 6 (1995): 487–514. http://dx.doi.org/10.1007/bf01204168.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Brun, Yuriy. "Solving NP-complete problems in the tile assembly model." Theoretical Computer Science 395, no. 1 (2008): 31–46. http://dx.doi.org/10.1016/j.tcs.2007.07.052.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Wu, Kan, Javier García de Abajo, Cesare Soci, Perry Ping Shum, and Nikolay I. Zheludev. "An optical fiber network oracle for NP-complete problems." Light: Science & Applications 3, no. 2 (2014): e147-e147. http://dx.doi.org/10.1038/lsa.2014.28.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Baker, Brenda S. "Approximation algorithms for NP-complete problems on planar graphs." Journal of the ACM 41, no. 1 (1994): 153–80. http://dx.doi.org/10.1145/174644.174650.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Murty, Katta G., and Santosh N. Kabadi. "Some NP-complete problems in quadratic and nonlinear programming." Mathematical Programming 39, no. 2 (1987): 117–29. http://dx.doi.org/10.1007/bf02592948.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Dieu, Phan Dinh, Le Cong Thanh, and Le Tuan Hoa. "Average polynomial time complexity of some NP-complete problems." Theoretical Computer Science 46 (1986): 219–37. http://dx.doi.org/10.1016/0304-3975(86)90031-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Ferreira, A. "On space-efficient algorithms for certain NP-complete problems." Theoretical Computer Science 120, no. 2 (1993): 311–15. http://dx.doi.org/10.1016/0304-3975(93)90295-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Fitzsimmons, Zack, Edith Hemaspaandra, Alexander Hoover, and David E. Narváez. "Very Hard Electoral Control Problems." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 1933–40. http://dx.doi.org/10.1609/aaai.v33i01.33011933.

Full text

Abstract:

It is important to understand how the outcome of an election can be modified by an agent with control over the structure of the election. Electoral control has been studied for many election systems, but for all these systems the winner problem is in P, and so control is in NP. There are election systems, such as Kemeny, that have many desirable properties, but whose winner problems are not in NP. Thus for such systems control is not in NP, and in fact we show that it is typically complete for ∑p2 (i.e., NPNP, the second level of the polynomial hierarchy). This is a very high level of complexi

APA, Harvard, Vancouver, ISO, and other styles

50

Yang, Jed. "Some NP-complete Edge Packing and Partitioning Problems in Planar Graphs." Communications on Number Theory and Combinatorial Theory 3, no. 1 (2022): 1–8. http://dx.doi.org/10.70013/m9rx1zq8.

Full text

Abstract:

Graph packing and partitioning problems have been studied in many contexts, including from the algorithmic complexity perspective. Consider the packing problem of determining whether a graph contains a spanning tree and a cycle that do not share edges. Bernáth and Király proved that this decision problem is NP-complete and asked if the same result holds when restricting to planar graphs. Similarly, they showed that the packing problem with a spanning tree and a path between two distinguished vertices is NP-complete. They also established the NP-completeness of the partitioning problem of deter

APA, Harvard, Vancouver, ISO, and other styles

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!