Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
List of NP-complete problems
open-in-new
<h2 id="graphs-and-hypergraphs">Graphs and hypergraphs</h2> <p><a href="/facts/Graph_theory/VVPCd4TX">Graphs</a> occur frequently in everyday applications. Examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (e.g. <a href="/facts/Facebook/0IhXFR6u">Facebook</a> or <a href="/facts/LinkedIn/Iq2IcNMt">LinkedIn</a>). </p> <ul><li><a href="/facts/1-planar_graph/HxeXsKo9">1-planarity</a><a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a></li> <li><a href="/facts/3-dimensional_matching/WFr6DxFj">3-dimensional matching</a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>: SP1 </li> <li><a href="/facts/Bandwidth_problem/ugGo2j8l">Bandwidth problem</a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>: GT40 </li> <li><a href="/facts/Bipartite_dimension/j9gHHJBN">Bipartite dimension</a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>: GT18 </li> <li><a href="/facts/Capacitated_minimum_spanning_tree/Sj1q3XKK">Capacitated minimum spanning tree</a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>: ND5 </li> <li><a href="/facts/Route_inspection_problem/zh0EhCsU">Route inspection problem</a> (also called Chinese postman problem) for <a href="/facts/Mixed_graph/6W2VCsLJ">mixed graphs</a> (having both directed and undirected edges). The program is solvable in polynomial time if the graph has all undirected or all directed edges. Variants include the rural postman problem.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>: ND25, ND27 </li> <li><a href="/facts/Clique_cover_problem/tXT9GSVq">Clique cover problem</a><a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a><a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a>: GT17 </li> <li><a href="/facts/Clique_problem/cVVBNP08">Clique problem</a><a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a><a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a>: GT19 </li> <li><a href="/facts/Complete_coloring/7BU2RkpN">Complete coloring</a>, a.k.a. achromatic number<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a>: GT5 </li> <li><a href="/facts/Cycle_rank/KKGbLcKo">Cycle rank</a></li> <li><a href="/facts/Degree-constrained_spanning_tree/XCYJLXdb">Degree-constrained spanning tree</a><a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a>: ND1 </li> <li><a href="/facts/Domatic_number/CWtHhmlW">Domatic number</a><a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a>: GT3 </li> <li><a href="/facts/Dominating_set_problem/3xX4kSnP">Dominating set</a>, a.k.a. domination number<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a>: GT2 </li></ul> NP-complete special cases include the <a href="/facts/Edge_dominating_set/hpgn1FBV">edge dominating set</a> problem, i.e., the dominating set problem in line graphs. NP-complete variants include the <a href="/facts/Connected_dominating_set/uCJqduKD">connected dominating set</a> problem and the <a href="/facts/Maximum_leaf_spanning_tree/uCJqduKD">maximum leaf spanning tree</a> problem.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a>: ND2 <ul><li><a href="/facts/Feedback_vertex_set/Kzr6n97M">Feedback vertex set</a><a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a><a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a>: GT7 </li> <li><a href="/facts/Feedback_arc_set/p69AScPL">Feedback arc set</a><a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a><a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a>: GT8 </li> <li><a href="/facts/Graph_coloring/J6HoBfP0">Graph coloring</a><a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a><a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a>: GT4 </li> <li><a href="/facts/Graph_homomorphism/XSljQ25z">Graph homomorphism</a> problem<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a>: GT52 </li> <li><a href="/facts/Graph_partition/MSQF0WyD">Graph partition</a> into <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraphs</a> of specific types (triangles, <a href="/facts/Graph_isomorphism/SBjVIhwW">isomorphic</a> <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraphs</a>, <a href="/facts/Hamiltonian_graph/MHjY2xoY">Hamiltonian</a> subgraphs, <a href="/facts/Forest_(graph_theory)/TCWk4Joy">forests</a>, <a href="/facts/Perfect_matching/LmtRYLgK">perfect matchings</a>) are known NP-complete. Partition into <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">cliques</a> is the same problem as <a href="/facts/Graph_coloring/J6HoBfP0">coloring</a> the <a href="/facts/Complement_(graph_theory)/IdHUPFr3">complement</a> of the given graph. A related problem is to find a partition that is optimal terms of the number of edges between parts.<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a>: GT11, GT12, GT13, GT14, GT15, GT16, ND14 </li> <li><a href="/facts/Grundy_number/fFXvgJyd">Grundy number</a> of a directed graph.<a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a>: GT56 </li> <li><a href="/facts/Hamiltonian_completion/E63XC6ex">Hamiltonian completion</a><a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a>: GT34 </li> <li><a href="/facts/Hamiltonian_path_problem/heMgdfpa">Hamiltonian path problem</a>, directed and undirected.<a class="footnote-ref" id="fnref:27" href="#fn:27"><sup>27</sup></a><a class="footnote-ref" id="fnref:28" href="#fn:28"><sup>28</sup></a>: GT37, GT38, GT39 </li> <li><a href="/facts/Induced_subgraph_isomorphism_problem/XBKgfULs">Induced subgraph isomorphism problem</a></li> <li><a href="/facts/Intersection_number_(graph_theory)/jxGe98Mw">Graph intersection number</a><a class="footnote-ref" id="fnref:29" href="#fn:29"><sup>29</sup></a>: GT59 </li> <li><a href="/facts/Longest_path_problem/W17hlDKs">Longest path problem</a><a class="footnote-ref" id="fnref:30" href="#fn:30"><sup>30</sup></a>: ND29 </li> <li>Maximum bipartite subgraph or (especially with weighted edges) <a href="/facts/Maximum_cut/9rulcdeW">maximum cut</a>.<a class="footnote-ref" id="fnref:31" href="#fn:31"><sup>31</sup></a><a class="footnote-ref" id="fnref:32" href="#fn:32"><sup>32</sup></a>: GT25, ND16 </li> <li><a href="/facts/Maximum_common_subgraph_isomorphism_problem/AEPrt2lF">Maximum common subgraph isomorphism problem</a><a class="footnote-ref" id="fnref:33" href="#fn:33"><sup>33</sup></a>: GT49 </li> <li><a href="/facts/Maximum_independent_set/ksu46kdz">Maximum independent set</a><a class="footnote-ref" id="fnref:34" href="#fn:34"><sup>34</sup></a>: GT20 </li> <li>Maximum <a href="/facts/Induced_path/zfcIx9Sw">Induced path</a><a class="footnote-ref" id="fnref:35" href="#fn:35"><sup>35</sup></a>: GT23 </li> <li><a href="/facts/Minimum_maximal_independent_set/eB4NQsny">Minimum maximal independent set</a> a.k.a. minimum independent dominating set<a class="footnote-ref" id="fnref:36" href="#fn:36"><sup>36</sup></a></li></ul> NP-complete special cases include the <a href="/facts/Minimum_maximal_matching/s0pUJ7hd">minimum maximal matching</a> problem,<a class="footnote-ref" id="fnref:37" href="#fn:37"><sup>37</sup></a>: GT10 which is essentially equal to the <a href="/facts/Edge_dominating_set/hpgn1FBV">edge dominating set</a> problem (see above). <ul><li><a href="/facts/Metric_dimension_(graph_theory)/Lkl3auvJ">Metric dimension</a> of a graph<a class="footnote-ref" id="fnref:38" href="#fn:38"><sup>38</sup></a>: GT61 </li> <li><a href="/facts/Metric_k-center/Uvt3a9Xw">Metric k-center</a></li> <li><a href="/facts/Minimum_degree_spanning_tree/IuFm3kbo">Minimum degree spanning tree</a></li> <li><a href="/facts/Minimum_k-cut/M5z8b8BR">Minimum k-cut</a></li> <li><a href="/facts/Minimum_k-spanning_tree/p0TJfgxu">Minimum k-spanning tree</a></li> <li><a href="/facts/Minor_(graph_theory)/qn5eI22T">Minor</a> testing (checking whether an input graph G {\displaystyle G} contains an input graph H {\displaystyle H} as a minor); the same holds with topological minors</li> <li><a href="/facts/Steiner_tree_problem/5mhCq8cN">Steiner tree</a>, or <a href="/facts/Minimum_spanning_tree/kgkGmY9s">Minimum spanning tree</a> for a subset of the vertices of a graph.<a class="footnote-ref" id="fnref:39" href="#fn:39"><sup>39</sup></a> (The minimum spanning tree for an entire graph is solvable in polynomial time.)</li> <li><a href="/facts/Modularity_(networks)/Q3hmfMwa">Modularity maximization</a><a class="footnote-ref" id="fnref:40" href="#fn:40"><sup>40</sup></a></li> <li><a href="/facts/Monochromatic_triangle/P2xp4eDn">Monochromatic triangle</a><a class="footnote-ref" id="fnref:41" href="#fn:41"><sup>41</sup></a>: GT6 </li> <li><a href="/facts/Pathwidth/Gf5S2byH">Pathwidth</a>,<a class="footnote-ref" id="fnref:42" href="#fn:42"><sup>42</sup></a> or, equivalently, <a href="/facts/Path_decomposition/Gf5S2byH">interval thickness</a>, and <a href="/facts/Path_decomposition/Gf5S2byH">vertex separation number</a><a class="footnote-ref" id="fnref:43" href="#fn:43"><sup>43</sup></a></li> <li>Rank coloring</li> <li><a href="/facts/Route_inspection_problem/zh0EhCsU">k-Chinese postman</a></li> <li><a href="/facts/Shortest_total_path_length_spanning_tree/gG3dmMpL">Shortest total path length spanning tree</a><a class="footnote-ref" id="fnref:44" href="#fn:44"><sup>44</sup></a>: ND3 </li> <li><a href="/facts/Slope_number/WSj4QUEg">Slope number</a> two testing<a class="footnote-ref" id="fnref:45" href="#fn:45"><sup>45</sup></a></li> <li>Recognizing <a href="/facts/String_graph/EQI2vzeh">string graphs</a><a class="footnote-ref" id="fnref:46" href="#fn:46"><sup>46</sup></a></li> <li><a href="/facts/Subgraph_isomorphism_problem/86LLWRg4">Subgraph isomorphism problem</a><a class="footnote-ref" id="fnref:47" href="#fn:47"><sup>47</sup></a>: GT48 </li> <li><a href="/facts/Treewidth/uoITxzRJ">Treewidth</a><a class="footnote-ref" id="fnref:48" href="#fn:48"><sup>48</sup></a></li> <li>Testing whether a <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> may be represented as <a href="/facts/Euclidean_minimum_spanning_tree/yu6atHA6">Euclidean minimum spanning tree</a></li> <li><a href="/facts/Vertex_cover/WK86bJvf">Vertex cover</a><a class="footnote-ref" id="fnref:49" href="#fn:49"><sup>49</sup></a><a class="footnote-ref" id="fnref:50" href="#fn:50"><sup>50</sup></a>: GT1 </li></ul> <h2 id="mathematical-programming">Mathematical programming</h2> <ul><li><a href="/facts/3-partition_problem/X4uW5f57">3-partition problem</a><a class="footnote-ref" id="fnref:51" href="#fn:51"><sup>51</sup></a>: SP15 </li> <li><a href="/facts/Bin_packing_problem/T67Qe934">Bin packing problem</a><a class="footnote-ref" id="fnref:52" href="#fn:52"><sup>52</sup></a>: SR1 </li> <li><a href="/facts/Bottleneck_traveling_salesman/4TJrYK5T">Bottleneck traveling salesman</a><a class="footnote-ref" id="fnref:53" href="#fn:53"><sup>53</sup></a>: ND24 </li> <li><a href="/facts/Optimal_facility_location/ssbU6ww2">Uncapacitated facility location problem</a></li> <li><a href="/facts/Flow_Shop_Scheduling_Problem/9XLuvp5b">Flow Shop Scheduling Problem</a></li> <li><a href="/facts/Generalized_assignment_problem/XLPNoqvp">Generalized assignment problem</a></li> <li><a href="/facts/Integer_programming/MDaaadoA">Integer programming</a>. The variant where variables are required to be 0 or 1, called zero-one linear programming, and several other variants are also NP-complete<a class="footnote-ref" id="fnref:54" href="#fn:54"><sup>54</sup></a><a class="footnote-ref" id="fnref:55" href="#fn:55"><sup>55</sup></a>: MP1 </li> <li>Some problems related to <a href="/facts/Job-shop_scheduling/1JjAvD3m">Job-shop scheduling</a></li> <li><a href="/facts/Knapsack_problem/HMIdVJH5">Knapsack problem</a>, <a href="/facts/Quadratic_knapsack_problem/dtbmYG1T">quadratic knapsack problem</a>, and several variants<a class="footnote-ref" id="fnref:56" href="#fn:56"><sup>56</sup></a><a class="footnote-ref" id="fnref:57" href="#fn:57"><sup>57</sup></a>: MP9 </li> <li>Some problems related to <a href="/facts/Multiprocessor_scheduling/LFDtRUfD">Multiprocessor scheduling</a></li> <li><a href="/facts/Numerical_3-dimensional_matching/bIySVJjg">Numerical 3-dimensional matching</a><a class="footnote-ref" id="fnref:58" href="#fn:58"><sup>58</sup></a>: SP16 </li> <li><a href="/facts/Open-shop_scheduling/Y3cImTY8">Open-shop scheduling</a></li> <li><a href="/facts/Partition_problem/LcSBAcmu">Partition problem</a><a class="footnote-ref" id="fnref:59" href="#fn:59"><sup>59</sup></a><a class="footnote-ref" id="fnref:60" href="#fn:60"><sup>60</sup></a>: SP12 </li> <li><a href="/facts/Quadratic_assignment_problem/kQ5KJSb2">Quadratic assignment problem</a><a class="footnote-ref" id="fnref:61" href="#fn:61"><sup>61</sup></a>: ND43 </li> <li><a href="/facts/Quadratic_programming/ct4RIUgs">Quadratic programming</a> (NP-hard in some cases, P if convex)</li> <li><a href="/facts/Subset_sum_problem/Guvrwy0L">Subset sum problem</a><a class="footnote-ref" id="fnref:62" href="#fn:62"><sup>62</sup></a>: SP13 </li> <li>Variations on the <a href="/facts/Traveling_salesman_problem/2WEKVLnV">traveling salesman problem</a>. The problem for graphs is NP-complete if the edge lengths are assumed integers. The problem for points on the plane is NP-complete with the discretized Euclidean metric and rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.<a class="footnote-ref" id="fnref:63" href="#fn:63"><sup>63</sup></a>: ND22, ND23 </li></ul> <h2 id="formal-languages-and-string-processing">Formal languages and string processing</h2> <ul><li><a href="/facts/Closest_string/8kaLYNzL">Closest string</a><a class="footnote-ref" id="fnref:64" href="#fn:64"><sup>64</sup></a></li> <li><a href="/facts/Longest_common_subsequence_problem/2HKIa0yd">Longest common subsequence problem</a> over multiple sequences<a class="footnote-ref" id="fnref:65" href="#fn:65"><sup>65</sup></a>: SR10 </li> <li>The bounded variant of the <a href="/facts/Post_correspondence_problem/YjHh66CM">Post correspondence problem</a><a class="footnote-ref" id="fnref:66" href="#fn:66"><sup>66</sup></a>: SR11 </li> <li><a href="/facts/Shortest_common_supersequence/oR3PSgxW">Shortest common supersequence</a> over multiple sequences<a class="footnote-ref" id="fnref:67" href="#fn:67"><sup>67</sup></a>: SR8 </li> <li>Extension of the <a href="/facts/String-to-string_correction_problem/A6EVoqKR">string-to-string correction problem</a><a class="footnote-ref" id="fnref:68" href="#fn:68"><sup>68</sup></a><a class="footnote-ref" id="fnref:69" href="#fn:69"><sup>69</sup></a>: SR8 </li></ul> <h2 id="games-and-puzzles">Games and puzzles</h2> <ul><li><a href="/facts/Bag_(puzzle)/l5FoEjQA">Bag (Corral)</a><a class="footnote-ref" id="fnref:70" href="#fn:70"><sup>70</sup></a></li> <li><a href="/facts/Battleship_(puzzle)/38oxAeFT">Battleship</a></li> <li><a href="/facts/Bulls_and_Cows/NK3voAQL">Bulls and Cows</a>, marketed as <a href="/facts/Mastermind_(board_game)/venBhaHW">Master Mind</a>: certain optimisation problems but not the game itself.</li> <li><a href="/facts/Edge-matching_puzzle/RYY7DHhJ">Edge-matching puzzles</a></li> <li><a href="/facts/Fillomino/nEXDvWay">Fillomino</a><a class="footnote-ref" id="fnref:71" href="#fn:71"><sup>71</sup></a></li> <li>(<a href="/facts/Generalized_game/dY2tP9pn">Generalized</a>) <a href="/facts/FreeCell/g35NFXhn">FreeCell</a><a class="footnote-ref" id="fnref:72" href="#fn:72"><sup>72</sup></a></li> <li><a href="/facts/Goishi_Hiroi/RTM4MQXb">Goishi Hiroi</a></li> <li><a href="/facts/Hashiwokakero/qWk7ckq3">Hashiwokakero</a><a class="footnote-ref" id="fnref:73" href="#fn:73"><sup>73</sup></a></li> <li><a href="/facts/Heyawake/5pDYBa4D">Heyawake</a><a class="footnote-ref" id="fnref:74" href="#fn:74"><sup>74</sup></a></li> <li>(<a href="/facts/Generalized_game/dY2tP9pn">Generalized</a>) <a href="/facts/Instant_Insanity/lacpVjQM">Instant Insanity</a><a class="footnote-ref" id="fnref:75" href="#fn:75"><sup>75</sup></a>: GP15 </li> <li><a href="/facts/Kakuro/jNkWlllU">Kakuro (Cross Sums)</a><a class="footnote-ref" id="fnref:76" href="#fn:76"><sup>76</sup></a></li> <li><a href="/facts/Kingdomino/tGJXw3RA">Kingdomino</a><a class="footnote-ref" id="fnref:77" href="#fn:77"><sup>77</sup></a></li> <li><a href="/facts/Kuromasu/6IBor9q6">Kuromasu</a> (also known as Kurodoko)<a class="footnote-ref" id="fnref:78" href="#fn:78"><sup>78</sup></a></li> <li><a href="/facts/LaserTank/gIo7HaY3">LaserTank</a><a class="footnote-ref" id="fnref:79" href="#fn:79"><sup>79</sup></a></li> <li><a href="/facts/Lemmings_(game)/9T2Q9x64">Lemmings</a> (with a polynomial time limit)<a class="footnote-ref" id="fnref:80" href="#fn:80"><sup>80</sup></a></li> <li><a href="/facts/Light_Up_(puzzle)/ajzwVbaJ">Light Up</a><a class="footnote-ref" id="fnref:81" href="#fn:81"><sup>81</sup></a></li> <li><a href="/facts/Mahjong_solitaire/bTpXzjF4">Mahjong solitaire</a> (with looking below tiles)</li> <li><a href="/facts/Masyu/FQI6DK3D">Masyu</a><a class="footnote-ref" id="fnref:82" href="#fn:82"><sup>82</sup></a></li> <li><a href="/facts/Minesweeper_Consistency_Problem/yn8sb9b5">Minesweeper Consistency Problem</a><a class="footnote-ref" id="fnref:83" href="#fn:83"><sup>83</sup></a> (but see Scott, Stege, & van Rooij<a class="footnote-ref" id="fnref:84" href="#fn:84"><sup>84</sup></a>)</li> <li><a href="/facts/Nonogram/t7h59YcR">Nonograms</a></li> <li><a href="/facts/Numberlink/PgDRrzs3">Numberlink</a></li> <li><a href="/facts/Nurikabe_(puzzle)/k07hLrA0">Nurikabe</a><a class="footnote-ref" id="fnref:85" href="#fn:85"><sup>85</sup></a></li> <li>(<a href="/facts/Generalized_game/dY2tP9pn">Generalized</a>) <a href="/facts/Pandemic_(board_game)/Xt9dNdRW">Pandemic</a><a class="footnote-ref" id="fnref:86" href="#fn:86"><sup>86</sup></a></li> <li><a href="/facts/Peg_solitaire/Bux8rR4H">Peg solitaire</a></li> <li><a href="/facts/Eight_queens_puzzle/XDx2HwlB">n-Queens completion</a></li> <li>Optimal solution for the <i>N</i>×<i>N</i>×<i>N</i> <a href="/facts/Rubik%2527s_Cube/Nlq35AbS">Rubik's Cube</a><a class="footnote-ref" id="fnref:87" href="#fn:87"><sup>87</sup></a></li> <li><a href="/facts/SameGame/s7PVy4YB">SameGame</a></li> <li><a href="/facts/Shakashaka/S8yR1WGj">Shakashaka</a></li> <li><a href="/facts/Slither_Link/tcXg9jG8">Slither Link</a> on a variety of grids<a class="footnote-ref" id="fnref:88" href="#fn:88"><sup>88</sup></a><a class="footnote-ref" id="fnref:89" href="#fn:89"><sup>89</sup></a><a class="footnote-ref" id="fnref:90" href="#fn:90"><sup>90</sup></a></li> <li>(<a href="/facts/Generalized_game/dY2tP9pn">Generalized</a>) <a href="/facts/Sudoku/I5Savmhf">Sudoku</a><a class="footnote-ref" id="fnref:91" href="#fn:91"><sup>91</sup></a><a class="footnote-ref" id="fnref:92" href="#fn:92"><sup>92</sup></a></li> <li><a href="/facts/Tatamibari/nQfeXXuC">Tatamibari</a></li> <li><a href="/facts/Tentai_Show/TTlWUtKg">Tentai Show</a></li> <li>Problems related to <a href="/facts/Tetris/djLfTK0n">Tetris</a><a class="footnote-ref" id="fnref:93" href="#fn:93"><sup>93</sup></a></li> <li><a href="/facts/Verbal_arithmetic/x97CcbnT">Verbal arithmetic</a></li></ul> <h2 id="other">Other</h2> <ul><li><a href="/facts/Berth_allocation_problem/A21btenJ">Berth allocation problem</a><a class="footnote-ref" id="fnref:94" href="#fn:94"><sup>94</sup></a></li> <li><a href="/facts/Betweenness_problem/tms0GlrG">Betweenness</a></li> <li>Assembling an optimal <a href="/facts/Bitcoin/UJvqfray">Bitcoin</a> block.<a class="footnote-ref" id="fnref:95" href="#fn:95"><sup>95</sup></a></li> <li><a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problem</a> (SAT).<a class="footnote-ref" id="fnref:96" href="#fn:96"><sup>96</sup></a><a class="footnote-ref" id="fnref:97" href="#fn:97"><sup>97</sup></a>: LO1 There are many variations that are also NP-complete. An important variant is where each clause has exactly three literals (3SAT), since it is used in the proof of many other NP-completeness results.<a class="footnote-ref" id="fnref:98" href="#fn:98"><sup>98</sup></a>: p. 48 </li> <li><a href="/facts/Circuit_satisfiability_problem/LDkc2Yc0">Circuit satisfiability problem</a></li> <li><a href="/facts/Conjunctive_Boolean_query/M7T1HCJU">Conjunctive Boolean query</a><a class="footnote-ref" id="fnref:99" href="#fn:99"><sup>99</sup></a>: SR31 </li> <li><a href="/facts/Cyclic_ordering/j5DaU26j">Cyclic ordering</a><a class="footnote-ref" id="fnref:100" href="#fn:100"><sup>100</sup></a></li> <li><a href="/facts/Exact_cover/C7QcbDcN">Exact cover</a> problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">matching</a>).<a class="footnote-ref" id="fnref:101" href="#fn:101"><sup>101</sup></a><a class="footnote-ref" id="fnref:102" href="#fn:102"><sup>102</sup></a>: SP2 </li> <li>Finding the global minimum solution of a <a href="/facts/Hartree-Fock/U9mlRWVR">Hartree-Fock</a> problem<a class="footnote-ref" id="fnref:103" href="#fn:103"><sup>103</sup></a></li> <li><a href="/facts/Hasse_diagram/EqeJbUH0">Upward planarity</a> testing<a class="footnote-ref" id="fnref:104" href="#fn:104"><sup>104</sup></a></li> <li><a href="/facts/National_Resident_Matching_Program/LlpBtGe1">Hospitals-and-residents problem with couples</a></li> <li><a href="/facts/Knot_genus/LqkqdPl8">Knot genus</a><a class="footnote-ref" id="fnref:105" href="#fn:105"><sup>105</sup></a></li> <li><a href="/facts/Latin_square/1e60MInk">Latin square</a> completion (the problem of determining if a partially filled square can be completed)</li> <li><a href="/facts/Maximum_2-satisfiability/cUMH5x2y">Maximum 2-satisfiability</a><a class="footnote-ref" id="fnref:106" href="#fn:106"><sup>106</sup></a>: LO5 </li> <li>Maximum volume <a href="/facts/Submatrix/qa8FI4ko">submatrix</a> – Problem of selecting the best conditioned subset of a larger m × n {\displaystyle m\times n} matrix. This class of problem is associated with Rank revealing <a href="/facts/QR_factorization/NswfKLGY">QR factorizations</a> and D optimal experimental design.<a class="footnote-ref" id="fnref:107" href="#fn:107"><sup>107</sup></a></li> <li>Minimal <a href="/facts/Addition_chain/WlqPzv4v">addition chains</a> for sequences.<a class="footnote-ref" id="fnref:108" href="#fn:108"><sup>108</sup></a> The complexity of minimal addition chains for individual numbers is unknown.<a class="footnote-ref" id="fnref:109" href="#fn:109"><sup>109</sup></a></li> <li><a href="/facts/Modal_logic/I7uXvYYT">Modal logic</a> <a href="/facts/S5_(modal_logic)/0CpkyrlH">S5</a>-Satisfiability</li> <li><a href="/facts/Pancake_sorting/tejLXXL6">Pancake sorting</a> distance problem for strings<a class="footnote-ref" id="fnref:110" href="#fn:110"><sup>110</sup></a></li> <li>Solubility of two-variable quadratic polynomials over the integers.<a class="footnote-ref" id="fnref:111" href="#fn:111"><sup>111</sup></a> Given positive integers A , B , C {\displaystyle \textstyle A,B,C} , decide existence of positive integers x , y {\displaystyle x,y} such that A x 2 + B y − C = 0 {\displaystyle Ax^{2}+By-C=0} </li> <li>By the same article<a class="footnote-ref" id="fnref:112" href="#fn:112"><sup>112</sup></a> existence of bounded <a href="/facts/Tonelli%25E2%2580%2593Shanks_algorithm/tdxF6hfd">modular square roots</a> with arbitrarily composite modulus. Given positive integers A , B , C ≥ 0 {\displaystyle \textstyle A,B,C\geq 0} , decide existence of an integer x ∈ [ 0 , C ] {\displaystyle x\in [0,C]} such that x 2 ≡ A mod B {\displaystyle x^{2}\equiv A{\bmod {B}}} . The problem remains NP-complete even if a <a href="/facts/Prime_number/L20FLkgn">prime factorization</a> of B {\displaystyle B} is provided.</li> <li><a href="/facts/Serializability/j6LY0fqE">Serializability</a> of database histories<a class="footnote-ref" id="fnref:113" href="#fn:113"><sup>113</sup></a>: SR33 </li> <li><a href="/facts/Set_cover_problem/MVzyBYs1">Set cover</a> (also called "minimum cover" problem). This is equivalent, by transposing the incidence matrix, to the hitting set problem.<a class="footnote-ref" id="fnref:114" href="#fn:114"><sup>114</sup></a><a class="footnote-ref" id="fnref:115" href="#fn:115"><sup>115</sup></a>: SP5, SP8 </li> <li><a href="/facts/Set_packing/6SYrhrDN">Set packing</a><a class="footnote-ref" id="fnref:116" href="#fn:116"><sup>116</sup></a><a class="footnote-ref" id="fnref:117" href="#fn:117"><sup>117</sup></a>: SP3 </li> <li><a href="/facts/Set_splitting/V9sBhlho">Set splitting</a> problem<a class="footnote-ref" id="fnref:118" href="#fn:118"><sup>118</sup></a>: SP4 </li> <li>Scheduling to minimize weighted completion time</li> <li>Block Sorting<a class="footnote-ref" id="fnref:119" href="#fn:119"><sup>119</sup></a> (Sorting by Block Moves)</li> <li><a href="/facts/Sparse_approximation/IkUA6yDf">Sparse approximation</a></li> <li>Variations of the <a href="/facts/Steiner_tree_problem/5mhCq8cN">Steiner tree problem</a>. Specifically, with the discretized Euclidean metric, rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.<a class="footnote-ref" id="fnref:120" href="#fn:120"><sup>120</sup></a>: ND13 </li> <li>Three-dimensional <a href="/facts/Ising_model/lvBpj2h1">Ising model</a><a class="footnote-ref" id="fnref:121" href="#fn:121"><sup>121</sup></a></li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Existential_theory_of_the_reals/LgJzEklm">Existential theory of the reals § Complete problems</a></li> <li><a href="/facts/Karp%2527s_21_NP-complete_problems/dqu5bBh0">Karp's 21 NP-complete problems</a></li> <li><a href="/facts/List_of_PSPACE-complete_problems/09NILpMD">List of PSPACE-complete problems</a></li> <li><a href="/facts/Reduction_(complexity)/IVWF7a1c">Reduction (complexity)</a></li></ul> <h2 id="notes">Notes</h2> <p>General </p> <ul><li><a href="/facts/Michael_Garey/xuSLYs90">Garey, Michael R.</a>; <a href="/facts/David_S._Johnson/kGSBxucb">Johnson, David S.</a> (1979). <i><a href="/facts/Computers_and_Intractability/04FE56Ss">Computers and Intractability: A Guide to the Theory of NP-Completeness</a></i>. Series of Books in the Mathematical Sciences (1st ed.). New York: <a href="/facts/W._H._Freeman_and_Company/sJ3zg32G">W. H. Freeman and Company</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780716710455. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066">0519066</a>. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/247570676">247570676</a>.. This book is a classic, developing the theory, then cataloguing <i>many</i> NP-Complete problems.</li> <li><a href="/facts/Stephen_A._Cook/GdE35Sm1">Cook, S.A.</a> (1971). "The complexity of theorem proving procedures". <i>Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York</i>. pp. 151–158. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F800157.805047">10.1145/800157.805047</a>.</li> <li><a href="/facts/Richard_Karp/XtYCL0nA">Karp, Richard M.</a> (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). <i>Complexity of Computer Computations</i>. Plenum. pp. 85–103.</li> <li>Dunne, P.E. <a href="http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html">"An annotated list of selected NP-complete problems"</a>. COMP202, Dept. of Computer Science, <a href="/facts/University_of_Liverpool/c9yBULDJ">University of Liverpool</a>. Retrieved 21 June 2008.</li> <li>Crescenzi, P.; Kann, V.; Halldórsson, M.; <a href="/facts/Marek_Karpinski/XPxNRbPA">Karpinski, M.</a>; <a href="/facts/Gerhard_J._Woeginger/beUa9kJr">Woeginger, G</a>. <a href="https://www.csc.kth.se/~viggo/problemlist/compendium.html">"A compendium of NP optimization problems"</a>. KTH NADA, Stockholm. Retrieved 21 June 2008.</li> <li>Dahlke, K. <a href="http://www.mathreference.com/lan-cx-np,intro.html">"NP-complete problems"</a>. <i>Math Reference Project</i>. Retrieved 21 June 2008.</li></ul> <p>Specific problems </p> <ul><li>Friedman, E (2002). <a href="https://web.archive.org/web/20060904225147/http://www.stetson.edu/~efriedma/papers/pearl/pearl.html">"Pearl puzzles are NP-complete"</a>. Stetson University, DeLand, Florida. Archived from <a href="https://www.stetson.edu/~efriedma/papers/pearl/pearl.html">the original</a> on 4 September 2006. Retrieved 21 June 2008.</li> <li>Grigoriev, A; <a href="/facts/Hans_L._Bodlaender/D7g6rsQ1">Bodlaender, H L</a> (2007). "Algorithms for graphs embeddable with few crossings per edge". <i>Algorithmica</i>. 49 (1): 1–11. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.3576">10.1.1.61.3576</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00453-007-0010-x">10.1007/s00453-007-0010-x</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2344391">2344391</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:8174422">8174422</a>.</li> <li>Hartung, S; Nichterlein, A (2012). "NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs". <i>How the World Computes</i>. Lecture Notes in Computer Science. Vol. 7318. Springer, Berlin, Heidelberg. pp. 283–292. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.377.2077">10.1.1.377.2077</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-30870-3_29">10.1007/978-3-642-30870-3_29</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-30869-7. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6112925">6112925</a>.</li> <li>Holzer, Markus; Ruepp, Oliver (2007). <a href="https://mediatum.ub.tum.de/doc/1289953/document.pdf">"The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake"</a> (PDF). <i>Proceedings, 4th International Conference on Fun with Algorithms, <a href="/facts/LNCS/1UeA77BC">LNCS</a> 4475</i>. Springer, Berlin/Heidelberg. pp. 198–212. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-72914-3_18">10.1007/978-3-540-72914-3_18</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-72913-6.</li> <li>Kaye, Richard (2000). "Minesweeper is NP-complete". <i>Mathematical Intelligencer</i>. 22 (2): 9–15. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF03025367">10.1007/BF03025367</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:122435790">122435790</a>. Further information available online at <a href="http://web.mat.bham.ac.uk/R.W.Kaye/minesw/">Richard Kaye's Minesweeper pages</a>.</li> <li>Kashiwabara, T.; Fujisawa, T. (1979). "NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph". <i>Proceedings</i>. <a href="/facts/International_Symposium_on_Circuits_and_Systems/WKqCAhzC">International Symposium on Circuits and Systems</a>. pp. 657–660.</li> <li>Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). "One-dimensional logic gate assignment and interval graphs". <i>IEEE Transactions on Circuits and Systems</i>. 26 (9): 675–684. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FTCS.1979.1084695">10.1109/TCS.1979.1084695</a>.</li> <li>Lengauer, Thomas (1981). "Black-white pebbles and graph separation". <i><a href="/facts/Acta_Informatica/xUwmqIIq">Acta Informatica</a></i>. 16 (4): 465–475. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF00264496">10.1007/BF00264496</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:19415148">19415148</a>.</li> <li>Arnborg, Stefan; <a href="/facts/Derek_Corneil/IlyG5ET3">Corneil, Derek G.</a>; Proskurowski, Andrzej (1987). "Complexity of finding embeddings in a <i>k</i>-tree". <i>SIAM Journal on Algebraic and Discrete Methods</i>. 8 (2): 277–284. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0608024">10.1137/0608024</a>.</li> <li>Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs". <i>Proceedings of Third International Conference on Fun with Algorithms (FUN 2004)</i>. pp. 65–76.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://www.csc.kth.se/~viggo/problemlist/">A compendium of NP optimization problems</a></li> <li><a href="https://adriann.github.io/npc/npc.html">Graph of NP-complete Problems</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Grigoriev & Bodlaender (2007). - Grigoriev, A; Bodlaender, H L (2007). "Algorithms for graphs embeddable with few crossings per edge". Algorithmica. 49 (1): 1–11. CiteSeerX 10.1.1.61.3576. doi:10.1007/s00453-007-0010-x. MR 2344391. S2CID 8174422. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.3576" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.3576</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> <li id="fn:25"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li> <li id="fn:26"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li> <li id="fn:27"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:27" class="footnote-back-ref">↩</a></p></li> <li id="fn:28"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></p></li> <li id="fn:29"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></p></li> <li id="fn:30"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></p></li> <li id="fn:31"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:31" class="footnote-back-ref">↩</a></p></li> <li id="fn:32"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></p></li> <li id="fn:33"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></p></li> <li id="fn:34"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></p></li> <li id="fn:35"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></p></li> <li id="fn:36"><p>Minimum Independent Dominating Set <a href="http://www.csc.kth.se/~viggo/wwwcompendium/node14.html" target="_blank">http://www.csc.kth.se/~viggo/wwwcompendium/node14.html</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></p></li> <li id="fn:37"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></p></li> <li id="fn:38"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></p></li> <li id="fn:39"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:39" class="footnote-back-ref">↩</a></p></li> <li id="fn:40"><p>Brandes, Ulrik; Delling, Daniel; Gaertler, Marco; Görke, Robert; Hoefer, Martin; Nikoloski, Zoran; Wagner, Dorothea (2006), Maximizing Modularity is hard, arXiv:physics/0608255, Bibcode:2006physics...8255B <a href="/wiki/Ulrik_Brandes" target="_blank">/wiki/Ulrik_Brandes</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></p></li> <li id="fn:41"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></p></li> <li id="fn:42"><p>Arnborg, Corneil & Proskurowski (1987) - Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej (1987). "Complexity of finding embeddings in a k-tree". SIAM Journal on Algebraic and Discrete Methods. 8 (2): 277–284. doi:10.1137/0608024. <a href="https://doi.org/10.1137%2F0608024" target="_blank">https://doi.org/10.1137%2F0608024</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></p></li> <li id="fn:43"><p>Kashiwabara & Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981). - Kashiwabara, T.; Fujisawa, T. (1979). "NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph". Proceedings. International Symposium on Circuits and Systems. pp. 657–660. <a href="#fnref:43" class="footnote-back-ref">↩</a></p></li> <li id="fn:44"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></p></li> <li id="fn:45"><p>Garg, Ashim; Tamassia, Roberto (1995). "On the computational complexity of upward and rectilinear planarity testing". Lecture Notes in Computer Science. Vol. 894/1995. pp. 286–297. doi:10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1. <a href="978-3-540-58950-1" target="_blank">978-3-540-58950-1</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></p></li> <li id="fn:46"><p>Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (September 2003). "Recognizing string graphs in NP". Journal of Computer and System Sciences. 67 (2): 365–380. doi:10.1016/S0022-0000(03)00045-X. <a href="https://doi.org/10.1016%2FS0022-0000%2803%2900045-X" target="_blank">https://doi.org/10.1016%2FS0022-0000%2803%2900045-X</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></p></li> <li id="fn:47"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></p></li> <li id="fn:48"><p>Arnborg, Corneil & Proskurowski (1987) - Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej (1987). "Complexity of finding embeddings in a k-tree". SIAM Journal on Algebraic and Discrete Methods. 8 (2): 277–284. doi:10.1137/0608024. <a href="https://doi.org/10.1137%2F0608024" target="_blank">https://doi.org/10.1137%2F0608024</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></p></li> <li id="fn:49"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:49" class="footnote-back-ref">↩</a></p></li> <li id="fn:50"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></p></li> <li id="fn:51"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:51" class="footnote-back-ref">↩</a></p></li> <li id="fn:52"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:52" class="footnote-back-ref">↩</a></p></li> <li id="fn:53"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:53" class="footnote-back-ref">↩</a></p></li> <li id="fn:54"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:54" class="footnote-back-ref">↩</a></p></li> <li id="fn:55"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:55" class="footnote-back-ref">↩</a></p></li> <li id="fn:56"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:56" class="footnote-back-ref">↩</a></p></li> <li id="fn:57"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:57" class="footnote-back-ref">↩</a></p></li> <li id="fn:58"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:58" class="footnote-back-ref">↩</a></p></li> <li id="fn:59"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:59" class="footnote-back-ref">↩</a></p></li> <li id="fn:60"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:60" class="footnote-back-ref">↩</a></p></li> <li id="fn:61"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:61" class="footnote-back-ref">↩</a></p></li> <li id="fn:62"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:62" class="footnote-back-ref">↩</a></p></li> <li id="fn:63"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:63" class="footnote-back-ref">↩</a></p></li> <li id="fn:64"><p>Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), "Distinguishing string selection problems", Information and Computation, 185 (1): 41–55, doi:10.1016/S0890-5401(03)00057-9, MR 1994748 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:64" class="footnote-back-ref">↩</a></p></li> <li id="fn:65"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:65" class="footnote-back-ref">↩</a></p></li> <li id="fn:66"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:66" class="footnote-back-ref">↩</a></p></li> <li id="fn:67"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:67" class="footnote-back-ref">↩</a></p></li> <li id="fn:68"><p>Wagner, Robert A. (May 1975). "On the complexity of the Extended String-to-String Correction Problem". Proceedings of seventh annual ACM symposium on Theory of computing - STOC '75. pp. 218–223. doi:10.1145/800116.803771. ISBN 9781450374194. S2CID 18705107. <a href="9781450374194" target="_blank">9781450374194</a> <a href="#fnref:68" class="footnote-back-ref">↩</a></p></li> <li id="fn:69"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:69" class="footnote-back-ref">↩</a></p></li> <li id="fn:70"><p>Friedman, Erich. "Corral Puzzles are NP-complete" (PDF). Retrieved 17 August 2021. <a href="https://erich-friedman.github.io/papers/corral.pdf" target="_blank">https://erich-friedman.github.io/papers/corral.pdf</a> <a href="#fnref:70" class="footnote-back-ref">↩</a></p></li> <li id="fn:71"><p>Yato, Takauki (2003). Complexity and Completeness of Finding Another Solution and its Application to Puzzles. CiteSeerX 10.1.1.103.8380. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:71" class="footnote-back-ref">↩</a></p></li> <li id="fn:72"><p>Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence 143(2):219-262, 2003. <a href="#fnref:72" class="footnote-back-ref">↩</a></p></li> <li id="fn:73"><p>"HASHIWOKAKERO Is NP-Complete". <a href="http://www.cs.au.dk/~koda/hashiwokakero" target="_blank">http://www.cs.au.dk/~koda/hashiwokakero</a> <a href="#fnref:73" class="footnote-back-ref">↩</a></p></li> <li id="fn:74"><p>Holzer & Ruepp (2007) - Holzer, Markus; Ruepp, Oliver (2007). "The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake" (PDF). Proceedings, 4th International Conference on Fun with Algorithms, LNCS 4475. Springer, Berlin/Heidelberg. pp. 198–212. doi:10.1007/978-3-540-72914-3_18. ISBN 978-3-540-72913-6. <a href="https://mediatum.ub.tum.de/doc/1289953/document.pdf" target="_blank">https://mediatum.ub.tum.de/doc/1289953/document.pdf</a> <a href="#fnref:74" class="footnote-back-ref">↩</a></p></li> <li id="fn:75"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:75" class="footnote-back-ref">↩</a></p></li> <li id="fn:76"><p>Takahiro, Seta (5 February 2002). "The complexities of puzzles, cross sum and their another solution problems (ASP)" (PDF). Retrieved 18 November 2018. <a href="http://www-imai.is.s.u-tokyo.ac.jp/~seta/paper/senior_thesis/seniorthesis.pdf" target="_blank">http://www-imai.is.s.u-tokyo.ac.jp/~seta/paper/senior_thesis/seniorthesis.pdf</a> <a href="#fnref:76" class="footnote-back-ref">↩</a></p></li> <li id="fn:77"><p>Nguyen, Viet-Ha; Perrot, Kévin; Vallet, Mathieu (24 June 2020). "NP-completeness of the game KingdominoTM". Theoretical Computer Science. 822: 23–35. doi:10.1016/j.tcs.2020.04.007. ISSN 0304-3975. S2CID 218552723. <a href="https://doi.org/10.1016%2Fj.tcs.2020.04.007" target="_blank">https://doi.org/10.1016%2Fj.tcs.2020.04.007</a> <a href="#fnref:77" class="footnote-back-ref">↩</a></p></li> <li id="fn:78"><p>Kölker, Jonas (2012). "Kurodoko is NP-complete" (PDF). Journal of Information Processing. 20 (3): 694–706. doi:10.2197/ipsjjip.20.694. S2CID 46486962. Archived from the original (PDF) on 12 February 2020. <a href="https://web.archive.org/web/20200212021124/https://pdfs.semanticscholar.org/4971/aa310e07aaa07c1ba7299f519b39ba5c5195.pdf" target="_blank">https://web.archive.org/web/20200212021124/https://pdfs.semanticscholar.org/4971/aa310e07aaa07c1ba7299f519b39ba5c5195.pdf</a> <a href="#fnref:78" class="footnote-back-ref">↩</a></p></li> <li id="fn:79"><p>Alexandersson, Per; Restadh, Petter (2020). "LaserTank is NP-Complete". Mathematical Aspects of Computer and Information Sciences. Lecture Notes in Computer Science. Vol. 11989. Springer International Publishing. pp. 333–338. arXiv:1908.05966. doi:10.1007/978-3-030-43120-4_26. ISBN 978-3-030-43119-8. S2CID 201058355. <a href="978-3-030-43119-8" target="_blank">978-3-030-43119-8</a> <a href="#fnref:79" class="footnote-back-ref">↩</a></p></li> <li id="fn:80"><p>Cormode, Graham (2004). The hardness of the lemmings game, or Oh no, more NP-completeness proofs (PDF). <a href="http://dimacs.rutgers.edu/~graham/pubs/papers/cormodelemmings.pdf" target="_blank">http://dimacs.rutgers.edu/~graham/pubs/papers/cormodelemmings.pdf</a> <a href="#fnref:80" class="footnote-back-ref">↩</a></p></li> <li id="fn:81"><p>Light Up is NP-Complete <a href="https://web.archive.org/web/20080308132136/http://www.cs.umass.edu/~mcphailb/papers/2005lightup.pdf" target="_blank">https://web.archive.org/web/20080308132136/http://www.cs.umass.edu/~mcphailb/papers/2005lightup.pdf</a> <a href="#fnref:81" class="footnote-back-ref">↩</a></p></li> <li id="fn:82"><p>Friedman, Erich (27 March 2012). "Pearl Puzzles are NP-complete". Archived from the original on 4 February 2012. <a href="https://web.archive.org/web/20120204150006/http://www2.stetson.edu/~efriedma/papers/pearl/pearl.html" target="_blank">https://web.archive.org/web/20120204150006/http://www2.stetson.edu/~efriedma/papers/pearl/pearl.html</a> <a href="#fnref:82" class="footnote-back-ref">↩</a></p></li> <li id="fn:83"><p>Kaye (2000) - Kaye, Richard (2000). "Minesweeper is NP-complete". Mathematical Intelligencer. 22 (2): 9–15. doi:10.1007/BF03025367. S2CID 122435790. <a href="https://doi.org/10.1007%2FBF03025367" target="_blank">https://doi.org/10.1007%2FBF03025367</a> <a href="#fnref:83" class="footnote-back-ref">↩</a></p></li> <li id="fn:84"><p>Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper may not be NP-complete but is hard nonetheless, The Mathematical Intelligencer 33:4 (2011), pp. 5–17. <a href="#fnref:84" class="footnote-back-ref">↩</a></p></li> <li id="fn:85"><p>Holzer, Markus; Klein, Andreas; Kutrib, Martin; Ruepp, Oliver (2011). "Computational Complexity of NURIKABE". Fundamenta Informaticae. 110 (1–4): 159–174. doi:10.3233/FI-2011-534. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:85" class="footnote-back-ref">↩</a></p></li> <li id="fn:86"><p>Nakai, Kenichiro; Takenaga, Yasuhiko (2012). "NP-Completeness of Pandemic". Journal of Information Processing. 20 (3): 723–726. doi:10.2197/ipsjjip.20.723. ISSN 1882-6652. <a href="https://doi.org/10.2197%2Fipsjjip.20.723" target="_blank">https://doi.org/10.2197%2Fipsjjip.20.723</a> <a href="#fnref:86" class="footnote-back-ref">↩</a></p></li> <li id="fn:87"><p>Demaine, Erik; Eisenstat, Sarah; Rudoy, Mikhail (2018). Solving the Rubik's Cube Optimally is NP-complete. 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). doi:10.4230/LIPIcs.STACS.2018.24. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:87" class="footnote-back-ref">↩</a></p></li> <li id="fn:88"><p>Sato, Takayuki; Seta, Takahiro (1987). Complexity and Completeness of Finding Another Solution and Its Application to Puzzles (PDF). International Symposium on Algorithms (SIGAL 1987). <a href="http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf" target="_blank">http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf</a> <a href="#fnref:88" class="footnote-back-ref">↩</a></p></li> <li id="fn:89"><p>Nukui; Uejima (March 2007). "ASP-Completeness of the Slither Link Puzzle on Several Grids". Ipsj Sig Notes. 2007 (23): 129–136. <a href="http://ci.nii.ac.jp/naid/110006249219/en/" target="_blank">http://ci.nii.ac.jp/naid/110006249219/en/</a> <a href="#fnref:89" class="footnote-back-ref">↩</a></p></li> <li id="fn:90"><p>Kölker, Jonas (2012). "Selected Slither Link Variants are NP-complete". Journal of Information Processing. 20 (3): 709–712. doi:10.2197/ipsjjip.20.709. <a href="https://doi.org/10.2197%2Fipsjjip.20.709" target="_blank">https://doi.org/10.2197%2Fipsjjip.20.709</a> <a href="#fnref:90" class="footnote-back-ref">↩</a></p></li> <li id="fn:91"><p>Sato, Takayuki; Seta, Takahiro (1987). Complexity and Completeness of Finding Another Solution and Its Application to Puzzles (PDF). International Symposium on Algorithms (SIGAL 1987). <a href="http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf" target="_blank">http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf</a> <a href="#fnref:91" class="footnote-back-ref">↩</a></p></li> <li id="fn:92"><p>A SURVEY OF NP-COMPLETE PUZZLES, Section 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; March 2008. (icga2008.pdf) <a href="https://www.cs.wmich.edu/elise/courses/cs431/icga2008.pdf" target="_blank">https://www.cs.wmich.edu/elise/courses/cs431/icga2008.pdf</a> <a href="#fnref:92" class="footnote-back-ref">↩</a></p></li> <li id="fn:93"><p>Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (25–28 July 2003). Tetris is Hard, Even to Approximate (PDF). Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003). Big Sky, Montana. <a href="http://erikdemaine.org/papers/Tetris_COCOON2003/paper.pdf" target="_blank">http://erikdemaine.org/papers/Tetris_COCOON2003/paper.pdf</a> <a href="#fnref:93" class="footnote-back-ref">↩</a></p></li> <li id="fn:94"><p>Lim, Andrew (1998), "The berth planning problem", Operations Research Letters, 22 (2–3): 105–110, doi:10.1016/S0167-6377(98)00010-8, MR 1653377 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:94" class="footnote-back-ref">↩</a></p></li> <li id="fn:95"><p>J. Bonneau, "Bitcoin mining is NP-hard" <a href="https://freedom-to-tinker.com/blog/jbonneau/bitcoin-mining-is-np-hard/" target="_blank">https://freedom-to-tinker.com/blog/jbonneau/bitcoin-mining-is-np-hard/</a> <a href="#fnref:95" class="footnote-back-ref">↩</a></p></li> <li id="fn:96"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:96" class="footnote-back-ref">↩</a></p></li> <li id="fn:97"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:97" class="footnote-back-ref">↩</a></p></li> <li id="fn:98"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:98" class="footnote-back-ref">↩</a></p></li> <li id="fn:99"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:99" class="footnote-back-ref">↩</a></p></li> <li id="fn:100"><p>Galil, Zvi; Megiddo, Nimrod (October 1977). "Cyclic ordering is NP-complete". Theoretical Computer Science. 5 (2): 179–182. doi:10.1016/0304-3975(77)90005-6. <a href="https://doi.org/10.1016%2F0304-3975%2877%2990005-6" target="_blank">https://doi.org/10.1016%2F0304-3975%2877%2990005-6</a> <a href="#fnref:100" class="footnote-back-ref">↩</a></p></li> <li id="fn:101"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:101" class="footnote-back-ref">↩</a></p></li> <li id="fn:102"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:102" class="footnote-back-ref">↩</a></p></li> <li id="fn:103"><p>Whitfield, James Daniel; Love, Peter John; Aspuru-Guzik, Alán (2013). "Computational complexity in electronic structure". Phys. Chem. Chem. Phys. 15 (2): 397–411. arXiv:1208.3334. Bibcode:2013PCCP...15..397W. doi:10.1039/C2CP42695A. PMID 23172634. S2CID 12351374. <a href="https://doi.org/10.1039/C2CP42695A" target="_blank">https://doi.org/10.1039/C2CP42695A</a> <a href="#fnref:103" class="footnote-back-ref">↩</a></p></li> <li id="fn:104"><p>Garg, Ashim; Tamassia, Roberto (1995). "On the computational complexity of upward and rectilinear planarity testing". Lecture Notes in Computer Science. Vol. 894/1995. pp. 286–297. doi:10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1. <a href="978-3-540-58950-1" target="_blank">978-3-540-58950-1</a> <a href="#fnref:104" class="footnote-back-ref">↩</a></p></li> <li id="fn:105"><p>Agol, Ian; Hass, Joel; Thurston, William (19 May 2002). "3-manifold knot genus is NP-complete". Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. STOC '02. New York, NY, USA: Association for Computing Machinery. pp. 761–766. arXiv:math/0205057. doi:10.1145/509907.510016. ISBN 978-1-58113-495-7. S2CID 10401375. <a href="978-1-58113-495-7" target="_blank">978-1-58113-495-7</a> <a href="#fnref:105" class="footnote-back-ref">↩</a></p></li> <li id="fn:106"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:106" class="footnote-back-ref">↩</a></p></li> <li id="fn:107"><p>Çivril, Ali; Magdon-Ismail, Malik (2009), "On selecting a maximum volume sub-matrix of a matrix and related problems" (PDF), Theoretical Computer Science, 410 (47–49): 4801–4811, doi:10.1016/j.tcs.2009.06.018, MR 2583677, archived from the original (PDF) on 3 February 2015 <a href="https://web.archive.org/web/20150203193923/http://www.meliksah.edu.tr/acivril/max-vol-original.pdf" target="_blank">https://web.archive.org/web/20150203193923/http://www.meliksah.edu.tr/acivril/max-vol-original.pdf</a> <a href="#fnref:107" class="footnote-back-ref">↩</a></p></li> <li id="fn:108"><p>Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981 <a href="#fnref:108" class="footnote-back-ref">↩</a></p></li> <li id="fn:109"><p>D. J. Bernstein, "Pippinger's exponentiation algorithm" (draft) <a href="http://cr.yp.to/papers/pippenger.pdf" target="_blank">http://cr.yp.to/papers/pippenger.pdf</a> <a href="#fnref:109" class="footnote-back-ref">↩</a></p></li> <li id="fn:110"><p>Hurkens, C.; Iersel, L. V.; Keijsper, J.; Kelk, S.; Stougie, L.; Tromp, J. (2007). "Prefix reversals on binary and ternary strings". SIAM J. Discrete Math. 21 (3): 592–611. arXiv:math/0602456. doi:10.1137/060664252. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:110" class="footnote-back-ref">↩</a></p></li> <li id="fn:111"><p>Manders, Kenneth; Adleman, Leonard (1976). "NP-complete decision problems for quadratic polynomials". Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76. pp. 23–29. doi:10.1145/800113.803627. ISBN 9781450374149. S2CID 18885088. <a href="9781450374149" target="_blank">9781450374149</a> <a href="#fnref:111" class="footnote-back-ref">↩</a></p></li> <li id="fn:112"><p>Manders, Kenneth; Adleman, Leonard (1976). "NP-complete decision problems for quadratic polynomials". Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76. pp. 23–29. doi:10.1145/800113.803627. ISBN 9781450374149. S2CID 18885088. <a href="9781450374149" target="_blank">9781450374149</a> <a href="#fnref:112" class="footnote-back-ref">↩</a></p></li> <li id="fn:113"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:113" class="footnote-back-ref">↩</a></p></li> <li id="fn:114"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:114" class="footnote-back-ref">↩</a></p></li> <li id="fn:115"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:115" class="footnote-back-ref">↩</a></p></li> <li id="fn:116"><p>Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. <a href="#fnref:116" class="footnote-back-ref">↩</a></p></li> <li id="fn:117"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:117" class="footnote-back-ref">↩</a></p></li> <li id="fn:118"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:118" class="footnote-back-ref">↩</a></p></li> <li id="fn:119"><p>Bein, W. W.; Larmore, L. L.; Latifi, S.; Sudborough, I. H. (1 January 2002). "Block sorting is hard". Proceedings International Symposium on Parallel Architectures, Algorithms and Networks. I-SPAN'02. pp. 307–312. doi:10.1109/ISPAN.2002.1004305. ISBN 978-0-7695-1579-3. S2CID 32222403. <a href="978-0-7695-1579-3" target="_blank">978-0-7695-1579-3</a> <a href="#fnref:119" class="footnote-back-ref">↩</a></p></li> <li id="fn:120"><p>Garey & Johnson (1979) - Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0519066</a> <a href="#fnref:120" class="footnote-back-ref">↩</a></p></li> <li id="fn:121"><p>Barry Arthur Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6. <a href="/wiki/Barry_Arthur_Cipra" target="_blank">/wiki/Barry_Arthur_Cipra</a> <a href="#fnref:121" class="footnote-back-ref">↩</a></p></li> </ol>