Storming of the Bastille and List of NP-complete problems: Difference between pages

From Wikipedia, the free encyclopedia
(Difference between pages)
Content deleted Content added
VisualWikitext
m Reverted 1 edit by 76.15.48.13 identified as vandalism to last revision by IRP. (TW)
 
m wikilink fixed, this time for real
 
Line 1: Line 1:
Here are some of the more commonly known problems that are [[NP-complete]] when expressed as [[decision problem]]s. This list is in no way comprehensive (there are more than 3000 known NP-complete problems). Most of the problems in this list are taken from Garey and Johnson's seminal book ''Computers and Intractability: A Guide to the Theory of NP-Completeness'', and are here presented in the same order and organization.
{{Infobox Military Conflict
| conflict = The Storming of the Bastille
| partof = [[French Revolution]]
| image = [[Image:Prise de la Bastille.jpg|200px]]
| caption = ''Prise de la Bastille'', by Jean-Pierre-Louis-Laurent Houel
| date = [[14 July]] [[1789]]
| place = [[Paris]], [[France]]
| casus =
| territory =
| result = [[Bastille]] captured, rebellion begins
| combatant1 = {{flagicon|France|royal}} [[Early Modern France|French government]]
| combatant2 = {{flagicon|France}} [[Paris]]ian [[militia]] (predecessor of France's [[National Guard (France)|National Guard]])
| commander1 = {{flagicon|France|royal}} [[Bernard-René de Launay]]{{KIA}}<BR>{{flagicon|France|royal}} Prince de Lambesc
| commander2 = {{flagicon|France}} [[Camille Desmoulins]]
| strength1 = 114 soldiers, 30 artillery pieces
| strength2 = 600 - 1,000 insurgents
| casualties1 = 1 (6 or possibly 8 killed after surrender. See discussion page)
| casualties2 = 98
| notes =
}}


{{Expand list|date=August 2008}}
'''The Storming of the Bastille''' in [[Paris]] occurred on [[14 July]] [[1789]]. While the medieval [[fortress]] and [[prison]] in Paris known as the [[Bastille]] contained only seven prisoners, its fall was the flashpoint of the [[French Revolution]], and it subsequently became an icon of the [[French Republic]]. In France, ''Le quatorze juillet'' ([[14 July]]) is a public holiday, formally known as the [[Fête de la Fédération]] (''Federation Holiday''). It is usually called [[Bastille Day]] in English.


== [[Computational geometry]]==
During the reign of [[Louis XVI of France|Louis XVI]], France faced a major financial crisis, triggered by the cost of intervening in the [[American Revolutionary War|American War of Independence]], and exacerbated by an unequal system of taxation. On [[5 May]] [[1789]], the [[Estates-General of 1789]] convened to deal with this issue, but was held back by archaic protocols and the conservatism of the [[Estates of the realm#In France|Second Estate]], consisting of the nobility and comprising 2% of France's population at the time. On [[17 June]] [[1789]], the [[Estates of the realm#In France|Third Estate]], with its representatives drawn from the middle class, or ''[[bourgeoisie]]'', reconstituted themselves as the [[National Assembly (French Revolution)|National Assembly]], a body whose purpose was the creation of a French [[constitution]]. The king initially opposed this development, but was forced to acknowledge the authority of the assembly, which subsequently renamed itself the [[National Constituent Assembly]] on [[9 July]].
*[[Minimum weight triangulation]] for a set of points in the plane <ref>[http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cs/0601002 Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)]</ref>
*Testing whether a [[tree (graph theory)|tree]] may be represented as [[Euclidean minimum spanning tree]]
*[[Unit disk graph]] recognition (Unit disk graphs are intersection graphs of circles of unit radius in the plane)<ref>H. Breu and [[David G. Kirkpatrick]]. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998</ref>
*Many [[motion planning]] among polygonal obstacles in the plane are NP-hard.
**[[Planar partitioning into connected subassemblies]]: Given a set A of non-overlapping (but possibly touching) polygons in the plane, decide if there is a proper subset S of A that can be separated from A\S by a collision-free rigid motion of S, and such that both S and A\S are connected. <ref>"Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165. </ref>


== Graph theory ==
The storming of the Bastille and the subsequent [[Declaration of the Rights of Man and of the Citizen]] was the third event of this opening stage of the revolution. The first had been the revolt of the nobility, refusing to aid King Louis XVI through the payment of taxes.<ref>Gross, David (ed.) ''We Won’t Pay!: A Tax Resistance Reader'' ISBN 1434898253 pp. 139-153</ref> The second had been the formation of the National Assembly and the [[Tennis Court Oath]].
=== Covering and partitioning ===
*[[Vertex cover problem|Vertex cover]]
*[[Dominating set problem|Dominating set]]
*[[Domatic number problem|Domatic number]]
*[[Graph coloring|Graph k-colorability]]
*[[Achromatic number]]
*[[Grundy number]]
*[[Monochromatic triangle]]
*[[Feedback vertex set]]
*[[Feedback arc set]]
*[[Partial feedback edge set]]
*[[Minimum maximal matching]]
*[[Partition into triangles]]
*[[Partition into isomorphic subgraphs]]
*[[Partition into Hamiltonian subgraphs]]
*[[Partition into forests]]
*[[Partition into cliques]]
*[[Partition into perfect matchings]]
*[[Two-stage maximum weight stochastic matching]]
*[[Covering by cliques]]
*[[Berth Allocation Problem (BAP)]]
*[[Bipartite dimension|Covering by complete bipartite subgraphs]]


=== Subgraphs and supergraphs ===
The middle class had formed the National Guard, sporting ''tricolor'' rosettes of blue, white and red; soon to become the symbol of the revolution.
*[[Clique problem|Clique]]
*[[Independent set problem|Independent set]]
*[[Induced subgraph with property Pi]]
*[[Induced connected subgraph with property Pi]]
*[[Induced path]]
*[[Balanced complete bipartite subgraph]]
*[[Bipartite subgraph]]
*[[Degree-bounded connected subgraph]]
*[[Planar subgraph]]
*[[Edge-subgraph]]
*[[Transitive subgraph]]
*[[Uniconnected subgraph]]
*[[Minimum k-connected subgraph]]
*[[Cubic subgraph]]
*[[Minimum equivalent digraph]]
*[[Hamiltonian completion]]
*[[Interval graph completion]]
*[[Path graph completion]]


=== Vertex ordering ===
[[Paris]], close to insurrection, and, in [[François Mignet]]'s words, "intoxicated with liberty and enthusiasm,"<ref> Mignet, ''History…'', Chapter I.</ref> showed wide support for the Assembly. The press published the Assembly's debates; political debate spread beyond the Assembly itself into the public squares and halls of the capital. The [[Palais-Royal]] and its grounds became the site of an endless meeting. The crowd, on the authority of the meeting at the Palais-Royal, broke open the prisons of the [[Abbaye]] to release some grenadiers of the French guards, reportedly imprisoned for refusing to fire on the people. The Assembly recommended the imprisoned guardsmen to the clemency of the king; they returned to prison, and received pardon. The rank and file of the regiment, previously considered reliable, now leaned toward the popular cause.
*[[Hamiltonian path problem|Hamiltonian circuit]]
*[[Directed Hamiltonian circuit problem|Directed Hamiltonian circuit]]
*[[Hamiltonian path problem|Hamiltonian path]]
*[[Bandwidth problem|Bandwidth]]
*[[Directed bandwidth]]
*[[Optimal linear arrangement]]
*[[Directed optimal linear arrangement]]
*[[Minimum cut linear arrangement]]
*[[Rooted tree arrangement]]
*[[Directed elimination ordering]]
*[[Elimination degree sequence]]


=== Iso- and other morphisms ===
{{French Revolution}}
*[[Subgraph isomorphism problem|Subgraph isomorphism]]
==Necker's dismissal==
*[[Largest common subgraph]]
[[Image:Bastillestatue.jpg|thumb|250pz|A statue by [[Jean Boucher]] commemorating the storming of the Bastille, depicting Camille Desmoulins supported by [[sans-culottes]]]]
*[[Maximum subgraph matching]]
*[[Graph contractability]]
*[[Graph homomorphism]]
*[[Digraph D-morphism]]


=== Miscellaneous ===
On [[11 July]] [[1789]], with troops at [[Versailles]], [[Sèvres]], the [[Champ de Mars]], and [[Saint-Denis, Seine-Saint-Denis|Saint-Denis]], Louis XVI, acting under the influence of the conservative nobles of his [[privy council]], dismissed and banished his finance minister, [[Jacques Necker]], who had been sympathetic to the Third Estate, and completely reconstructed the ministry. The marshal [[Victor-François, 2nd duc de Broglie|Victor-François, duc de Broglie]], [[la Galissonnière]], the [[Paul François de Quelen, duc de la Vauguyon|duc de la Vauguyon]], the Baron [[Baron de Breteuil|Louis de Breteuil]], and the intendant [[Foulon]], took over the posts of [[Puységur]], [[Armand Marc, comte de Montmorin]], [[César Guillaume de La Luzerne|La Luzerne]], [[Saint-Priest]], and Necker.
*[[Path with forbidden pairs]]
*[[Multiple choice matching]]
*[[Graph Grundy numbering]]
*[[Kernel problem|Kernel]]
*[[K-closure]]
*[[Intersection graph basis]]
*[[Path distinguishers]]
*[[Metric dimension (graph theory)|Metric dimension]]
*[[Nesetril-Rödl dimension]]
*[[Threshold number]]
*[[Oriented diameter]]
*[[Weighted diameter]]


== Network design ==
News of Necker's dismissal reached Paris in the afternoon of Sunday, [[12 July]]. The Parisians generally presumed that the dismissal marked the start of a coup by conservative elements. Liberal Parisians were further enraged by the fear that a concentration of Royal troops brought to Versailles from frontier garrisons would attempt to shut down the [[National Constituent Assembly]], which was meeting in Versailles. Crowds gathered throughout Paris, including more than ten thousand at the Palais-Royal. [[Camille Desmoulins]], a known [[freemasonry|freemason]] from the [[Neuf Soeurs|lodge of the Nine Sisters]], according to Mignet, successfully rallied the crowd by "mounting a table, pistol in hand, exclaiming: 'Citizens, there is no time to lose; the dismissal of Necker is the knell of a [[St. Bartholomew's Day Massacre|Saint Bartholomew]] for patriots! This very night all the Swiss and German battalions will leave the Champ de Mars to massacre us all; one resource is left; to take arms!'" <ref>Mignet, ''History…'', Chapter I.</ref>
=== Spanning trees ===
*[[Degree-constrained spanning tree]]
*[[Minimum degree spanning tree]]
*[[Maximum leaf spanning tree]]
*[[Shortest total path length spanning tree]]
*[[Bounded diameter spanning tree]]
*[[Capacitated spanning tree]]
*[[Geometric capacitated spanning tree]]
*[[Optimum communication spanning tree]]
*[[Isomorphic spanning tree]]
*[[Kth best spanning tree]]
*[[Bounded component spanning forest]]
*[[Multiple choice branching]]
*[[Steiner tree]]
*[[Geometric Steiner tree]]
*[[Cable Trench Problem]]
*[[Minimum Touching Tree/Minimum Length Corridor]]


=== Cuts and connectivity ===
The Swiss and German regiments referred to were among the foreign [[mercenary]] troops who made up a significant portion of the pre-revolutionary [[Military history of France#Ancien Régime|Royal Army]], and were seen as being less likely to be sympathetic to the popular cause than ordinary French soldiers. By early July, approximately half of the 25,000 regular troops concentrated around Paris and Versailles were drawn from these foreign regiments.
*[[Graph partitioning]]
*[[Acyclic partition]]
*[[Max weight cut]]
*[[Minimum cut into bounded sets]]
*[[Biconnectivity augmentation]]
*[[Strong connectivity augmentation]]
*[[Network reliability]]
*[[Network survivability]]
*[[Multiway Cut]]
*[[Minimum k-cut]]


=== Routing problems ===
==Armed conflict==
*[[Bottleneck traveling salesman]]
A growing crowd, brandishing busts of Necker and of the [[Louis-Philippe of france|duc d'Orléans]], passed through the streets to the [[Place Vendôme]], where they put a detachment of the Royal-Allemand Cavalerie (a heavy cavalry regiment recruited from German-speaking Alsace) to flight by a shower of stones. At the [[Place de la Concorde|Place Louis XV]], the Royal-Allemand, led by the Prince de Lambesc, shot the bearer of one of the busts; a soldier was also killed. Lambesc and his troopers rode into the crowd and a single civilian, reportedly an elderly man, was killed.
*[[Chinese postman for mixed graphs]]
*[[Euclidean traveling salesman]]
*[[K most vital arcs]]
*[[Kth shortest path]]
*[[Metric traveling salesman]]
*[[Longest circuit]]
*[[Longest path]]
*[[Prize Collecting Traveling Salesman]]
*[[Rural Postman]]
*[[Shortest path in general networks]]
*[[Shortest weight-constrained path]]
*[[Stacker-crane]]
*[[Time constrained traveling salesman feasibility]]
*[[Traveling salesman problem]]
*[[Vehicle routing problem]]


=== Flow problems ===
The regiment of [[Gardes Françaises''']] (French Guards) formed the permanent garrison of Paris and with many local ties was favourably disposed towards the popular cause. This regiment had remained confined to its barracks during the initial stages of the mid-July disturbances. With Paris becoming the scene of a general riot, Lambesc, not trusting the regiment to obey his order, posted sixty dragoons to station themselves before its dépôt in the [[Rue de la Chaussée-d'Antin|Chaussée d'Antin]]. Once again, a measure intended to restrain only served to provoke. The French Guards regiment routed the cavalry, killing two, wounding three, and putting the rest to flight. The officers of the French Guards made ineffectual attempts to rally their men. The rebellious citizenry had now acquired a trained military contingent; as word of this spread, the commanders of the royal forces encamped on the Champ de Mars became doubtful of the dependability of even the foreign regiments. The future "Citizen King", [[Louis-Philippe of France|Louis-Phillipe, duc d'Orléans]], witnessed these events as a young officer and was of the opinion that the soldiers would have obeyed orders if put to the test. He also commented in retrospect that the officers of the French Guards had neglected their responsibilities in the period before the rising, leaving the regiment too much to the control of its [[non-commissioned officer]]s. However the uncertain leadership of M. de Besenval led to a virtual abdication of royal authority in central Paris.
*[[Minimum edge-cost flow]]
*[[Integral flow with multipliers]]
*[[Path constrained network flow]]
*[[Integral flow with homologous arcs]]
*[[Integral flow with bundles]]
*[[Undirected flow with lower bounds]]
*[[Directed two-commodity integral flow]]
*[[Undirected two-commodity integral flow]]
*[[Disjoint connecting paths]]
*[[Maximum length-bounded disjoint paths]]
*[[Maximum fixed-length disjoint paths]]
*[[Unsplittable multicommodity flow]]


=== Miscellaneous ===
The demonstrators gathered in and around the [[Hôtel de Ville, Paris|Hôtel de Ville]] and sounded the [[tocsin]]. Distrust between the leading citizens gathered within the building and the masses outside was exacerbated by the failure or inability of the former to provide the latter with arms. Between political insurrection and opportunistic looting, Paris slid into chaos. In Versailles, the Assembly went into continuous session so that it could not, once again, be deprived of its meeting space.<ref>[http://www.fsmitha.com/h3/h33-fr.html The French Revolution] 2002</ref>
*[[Quadratic assignment problem]]
*[[Minimizing dummy activities in PERT networks]]
*[[Constrained triangulation]]
*[[Intersection graph for segments on a grid]]
*[[Edge embedding on a grid]]
*[[Geometric connected dominating set]]
*[[Minimum broadcast time]]
*[[Min-max multicenter]]
*[[Min-sum multicenter]]
*[[Uncapacitated Facility Location]]
*[[Metric k-center]]


== Sets and partitions ==
==Storming the Bastille==
=== Covering, hitting, and splitting ===
The demonstrators had earlier stormed the [[Les Invalides|Hôtel des Invalides]] to gather arms (29,000 to 32,000 muskets, but without powder or shot), and were mainly seeking to acquire the large quantities of arms and ammunition stored at the Bastille - on the 14th there were over 13,600 kg (30,000 lb) of [[gunpowder]] stored there.
*[[3-dimensional matching]]
*[[Exact cover]]
*[[Set packing]]
*[[Set splitting]]
*[[Set cover problem|Set cover]]
*[[Minimum test set]]
*[[Set basis]]
*[[Hitting set]]
*[[Intersection pattern]]
*[[Comparative containment]]
*[[3-matroid intersection]]


=== Weighted set problems ===
At this point, the Bastille was nearly empty of prisoners, housing only seven inmates: four [[forgery|forgers]], two "lunatics" and one "deviant" aristocrat, the conte de Solages (the [[Marquis de Sade]] had been transferred out ten days earlier). The cost of maintaining a medieval fortress and garrison for so limited a purpose had led to a decision being taken to close it, shortly before the disturbances began. It was, however, a symbol of royal tyranny.
*[[Partition problem|Partition]]
*[[Subset sum problem|Subset sum]]
*[[Subset product]]
*[[3-partition]]
*[[Numerical 3-dimensional matching]]
*[[Numerical matching with target sums]]
*[[Expected component sum]]
*[[Minimum sum of squares]]
*[[Kth largest subset]]
*[[Kth largest m-tuple]]


=== Set partitions ===
The regular garrison consisted of 82 ''invalides'' (veteran soldiers no longer suitable for service in the field). It had however been reinforced on [[7 July]] by 32 grenadiers of the Swiss Salis-Samade Regiment from the troops on the Champ de Mars. The walls mounted eighteen eight-pound guns and twelve smaller pieces. The governor was [[Bernard-René de Launay]], son of the previous governor and actually born within the Bastille.
*[[Median partition]]


== Storage and retrieval ==
The list of ''vainqueurs de la Bastille'' has around 600 names, and the total of the crowd was probably less than one thousand. The crowd gathered outside around mid-morning, calling for the surrender of the prison, the removal of the guns and the release of the arms and gunpowder. Two representatives of the crowd outside were invited into the fortress and negotiations began, and another was admitted around noon with definite demands. The negotiations dragged on while the crowd grew and became impatient.
=== Data storage ===
*[[Bin packing problem|Bin packing]]
*[[Dynamic storage allocation]]
*[[Pruned trie space minimization]]
*[[Expected retrieval cost]]
*[[Rooted tree storage assignment]]
*[[Multiple copy file allocation]]
*[[Capacity assignment]]


=== Compression and representation ===
Around 13:30 the crowd surged into the undefended outer courtyard, and the chains on the [[drawbridge]] to the inner courtyard were cut - crushing one unfortunate ''vainqueur''. About this time gunfire began, though which side actually fired first will never be conclusively decided. The crowd seemed to have felt it had been drawn into a trap and the fighting became more violent and intense, while attempts by deputies to organize a cease-fire were ignored by the attackers.
*[[Shortest common supersequence]]
*[[Shortest common superstring]]
*[[Longest common subsequence problem]] for the case of arbitrary (i.e., not ''a priori'' fixed) number of input sequences even in the case of the binary alphabet
*[[Bounded post correspondence problem]]
*[[Hitting string]]
*[[Sparse matrix compression]]
*[[Consecutive ones submatrix]]
*[[Consecutive ones matrix partition]]
*[[Consecutive ones matrix augmentation]]
*[[Consecutive block minimization]]
*[[Consecutive sets]]
*[[2-dimensional consecutive sets]]
*[[String-to-string correction]]
*[[Grouping by swapping]]
*[[External macro data compression]]
*[[Internal macro data compression]]
*[[Regular expression substitution]]
*[[Rectilinear picture compression]]
*[[Optimal vector quantization codebook]]
*[[Minimal grammar-based compression]]
*[[Adaptive Block-size Compression]]


=== Database problems ===
The firing continued, and at 15:00 the attackers were reinforced by mutinous ''gardes françaises'' and other deserters from among the regular troops, along with two cannons. A substantial force of Royal Army troops encamped on the nearby Champs de Mars did not intervene. With the possibility of a mutual massacre suddenly apparent Governor de Launay ordered a cease fire at 17:00. A letter offering his terms was handed out to the besiegers through a gap in the inner gate. His demands were refused, but de Launay nonetheless capitulated, as he realized that his troops could not hold out much longer; he opened the gates to the inner courtyard, and the ''vainqueurs'' swept in to liberate the fortress at 17:30.
*[[Minimum cardinality key]]
*[[Additional key]]
*[[Prime attribute name]]
*[[Boyce-Codd normal form violation]]
*[[Conjunctive query foldability]]
*[[Boolean conjunctive query]]
*[[Tableau equivalence]]
*[[Serializability]] [[of database histories]]
*[[Safety of database transaction systems]]
*[[Consistency of database frequency tables]]
*[[Safety of file protection systems]]


== Sequencing and scheduling ==
Ninety-eight attackers and one defender had died in the actual fighting. De Launay was seized and dragged towards the [[Hôtel de Ville]] in a storm of abuse. Outside the Hôtel a discussion as to his fate began. The badly beaten de Launay shouted "Enough! Let me die!" and kicked a pastry cook named Desnot in the groin. De Launay was then stabbed repeatedly and fell, and his head was sawed off and fixed on a [[Pike (weapon)|pike]] to be carried through the streets. The three officers of the permanent Bastille garrison were also killed by the crowd; surviving police reports detail their wounds and clothing. Two of the ''invalides'' of the garrison were lynched, but all but two of the Swiss regulars of the Salis-Samade Regiment were protected by the French Guards and eventually released to return to their regiment. Their officer, Lieutenant Louis de Flue, wrote a detailed report on the defense of the Bastille which was incorporated in the logbook of the Salis-Samade and has survived. It is (perhaps unfairly) critical of the dead Marquis de Launay, whom de Flue accuses of weak and indecisive leadership. The blame for the fall of the Bastille would rather appear to lie with the inertia of the commanders of the substantial force of Royal Army troops encamped on the Champs de Mars, who made no effort to intervene when the nearby Hôtel des Invalides or the Bastille were attacked.
=== Sequencing on one processor ===
*[[Sequencing with release times and deadlines]]
*[[Sequencing to minimize Tardy tasks]]
*[[Sequencing to minimize Tardy weight]]
*[[Sequencing to minimize weighted completion time]]
*[[Sequencing to minimize weighted tardiness]]
*[[Sequencing with deadlines and set-up times]]
*[[Sequencing to minimize maximum cumulative cost]]


=== Multiprocessor scheduling ===
Returning to the Hôtel de Ville, the mob accused the ''prévôt ès marchands'' (roughly, mayor) [[Jacques de Flesselles]] of treachery, and he was assassinated en route to an ostensible trial at the [[Palais-Royal]].
*[[Multiprocessor scheduling]]
*[[Precedence constrained scheduling]]
*[[Resource constrained scheduling]]
*[[Scheduling with individual deadlines]]
*[[Preemptive scheduling]]
*[[Scheduling to minimize weighted completion time]]


=== Shop scheduling ===
[[Image:Sansculottes.jpg|left|thumb|175px|The ''[[sans culottes]]'', wearing iconic [[Phrygian cap]]s and ''tricolor'' rosettes]]
*[[Open-shop scheduling]]
*[[Flow-shop scheduling]]
*[[No-wait flow-shop scheduling]]
*[[Two-processor flow-shop with bounded buffer]]
*[[Job-shop scheduling]]


=== Miscellaneous ===
==Aftermath==
*[[Timetable design]]
The citizenry of Paris, expecting a counterattack, entrenched the streets, built barricades of paving stones, and armed themselves as well as they could, especially with improvised pikes. Meanwhile, at Versailles, the Assembly remained ignorant of most of the Paris events, but eminently aware that Marshal de Broglie stood on the brink of unleashing a pro-Royalist coup to force the Assembly to adopt the order of [[23 June]]<ref>[http://sourcebook.fsc.edu/history/seance.html The Séance royale of 23 June, 1789<!-- Bot generated title -->]</ref> and then to dissolve. The [[Louis-Marie, vicomte de Noailles|viscomte de Noailles]] apparently first brought reasonably accurate news of the Paris events to Versailles. M. Ganilh and Bancal-des-Issarts, dispatched to the Hôtel de Ville, confirmed his report.
*[[Staff scheduling]]
*[[Production planning]]
*[[Deadlock avoidance]]


== Mathematical programming ==
By the morning of [[15 July]] the outcome appeared clear to the king as well, and he and his military commanders backed down. The Royal troops concentrated around Paris were dispersed to their frontier garrisons. The [[Marquis de la Fayette]] took up command of the National Guard at Paris; [[Jean-Sylvain Bailly]] — leader of the Third Estate and instigator of the [[Tennis Court Oath]] — became the city's mayor under a new governmental structure known as the ''[[Paris Commune (French Revolution)|Commune de Paris]]''. The king announced that he would recall Necker and return from Versailles to Paris; on [[27 July]], in Paris, he accepted a [[Flag of France|tricolor]] [[cockade]] from Bailly and entered the Hôtel de Ville, as cries of "Long live the King" were changed to "Long live the Nation".
[[Integer programming]]
*[[Linear programming|0-1 Integer programming]]
*[[Quadratic programming]] (NP-hard in some cases, P when convex)
*[[Cost-parametric linear programming]]
*[[Feasible basis extension]]
*[[Minimum weight solution to linear equations]]
*[[Open hemisphere]]
*[[K-relevancy]]
*[[Traveling salesman polytope non-adjacency]]
*[[Knapsack problem|Knapsack]]
*[[Integer knapsack]]
*[[Continuous multiple choice knapsack]]
*[[Partially ordered knapsack]]
*[[Generalized assignment problem]]
*[[Comparative vector inequalities]]
*[[Sparse approximation]]


== Algebra and number theory ==
Nonetheless, after this violence, nobles — little assured by the apparent and, as it was to prove, temporary reconciliation of king and people — started to flee the country as ''[[émigré]]s''. Early émigrés included the comte d'Artois (the future [[Charles X of France]]) and his two sons, the [[Louis Joseph, Prince of Condé|prince de Condé]], the [[Louis François II, Prince of Conti|prince de Conti]], the [[Polignac]] family, and (slightly later) [[Charles Alexandre de Calonne]], the former finance minister. They settled at [[Turin]], where Calonne, as agent for the count d'Artois and the prince de Condé, began plotting civil war within the kingdom and agitating for a European coalition against France.
=== Divisibility problems ===
*[[Quadratic congruences]]
*[[Simultaneous incongruences]]
*[[Simultaneous divisibility of linear polynomials]]
*[[Comparative divisibility]]
*[[Exponential expression divisibility]]
*[[Non-divisibility of a product polynomial]]
*[[Non-trivial greatest common divisor]]


=== Solvability of equations ===
Necker returned from [[Basel]] to Paris in triumph (which proved short-lived). He discovered upon his arrival that the mob had cruelly murdered Foulon and Foulon's nephew, Berthier, and that the [[Pierre Victor Besenval de Bronstatt|baron de Besenval]] (commander under Broglie) was held prisoner. Wishing to avoid further bloodshed, he overplayed his hand by demanding and obtaining a general amnesty, voted by the assembly of electors of Paris. In demanding amnesty rather than merely a just tribunal, Necker misjudged the weight of the political forces. He overestimated the power of the ''ad hoc'' assembly, which almost immediately revoked the amnesty to save their own role, and perhaps their own skins, instituting a trial court at the [[Châtelet]]. Mignet counts this as the moment when the Revolution left Necker behind.
*[[Quadratic diophantine equations]]
*[[Algebraic equations over GF2|Algebraic equations over GF[2] ]]
*[[Root of modulus 1]]
*[[Number of roots for a product polynomial]]
*[[Periodic solution recurrence relation]]


=== Miscellaneous ===
The successful insurrection at Paris spread throughout France. In accord with principles of [[popular sovereignty]] and with complete disregard for claims of royal authority, the people created a parallel structure of municipalities for civic government and militia for civic protection. In rural areas, many went beyond this: some burned title-deeds and no small number of châteaux, as the "[[Great Fear]]" spread across the countryside during the weeks July 20 to August 5, with attacks on wealthy landlords impelled by the belief that the aristocracy was trying to put down the revolution.
*[[Permanent evaluation]]
*[[Cosine product integration]]
*[[Equilibrium point problem|Equilibrium point]]
*[[Unification with commutative operators]]
*[[Unification for finitely presented algebras]]
*[[Integer expression membership]]
*[[Minimal addition chain]]


== Games and puzzles ==
==Fiction==
[[Alternating hitting set]]
Historical fiction accounts of the storming of the Bastille can be found in the novels ''[[A Tale of Two Cities]]'', by [[Charles Dickens]], and ''Ange Pitou'', by [[Alexandre Dumas]]. The event also comprises an important part in the [[Rose of Versailles]] franchise of [[Riyoko Ikeda]].
*[[Alternating maximum weighted matching]]
*[[Annihilation problem|Annihilation]]
*[[Battleship (puzzle)|Battleship]]
*[[Clickomania|Clickomania (SameGame)]]
*[[Cross Sums]]
*[[Crossword]] puzzle construction
*[[FreeCell]]
*[[Instant Insanity]]
*[[Light Up]]
*[[LITS]]
*[[Mastermind (board game)|Mastermind]]
*[[Masyu]]
*[[Minesweeper Consistency Problem]]
*[[Nurikabe]]
*[[Nonogram|Paint by numbers (Nonogram)]]
*[[Rabin game]]s
*[[Sift (game)|Sift]]
*[[Slither Link]]
*[[Square-tiling]]
*[[Sudoku]]
*[[Tetris]]
*[[Variable partition truth assignment]]
*[[Verbal arithmetic]]


==References==
== Logic ==
=== Propositional logic ===
{{Reflist}}
*[[Satisfiability]]
*[[Satisfiability#3-satisfiability|3-Satisfiability]]
*[[Not-all-equal 3SAT]]
*[[One-in-three 3SAT]]
*[[Maximum 3-Satisfiability]]
*[[Generalized satisfiability]]
*[[Non-tautology]]
*[[Minimum disjunctive normal form]]
*Truth-functionally complete connectives
*[[Planar-3SAT]]
*[[Monotone-3SAT]]


=== Miscellaneous ===
* {{1911}}
*[[Modal logic]] S5-Satisfiability
* {{Mignet}}
*[[Negation-free logic]]
*Conjunctive satisfiability with functions and inequalities
*[[Minimum axiom set]]
*[[First order subsumption]]
*[[Second order instantiation]]


== Automata and language theory ==
==Further reading==
=== Automata theory ===
* ''Relatation de la prise de la Bastille le 14 juillet par un de ses défenseurs''
*Two-way [[finite state automaton]] non-emptiness
* ''1789 L'annee cruciale'', E. Braesch (Paris, 1948)
*[[Quasi-realtime automaton]] acceptance
* ''A Tale of Two Cities'', Charles Dickens.
*Reduction of incompletely specified automata
*[[Minimum inferred finite state automaton]]


=== Formal languages ===
==External links==
*[[Regular expression]] inequivalence
* [http://www.footnote.com/spotlight/174/thomas-jeffersons-accoun Thomas Jefferson's letter to John Jay recounting the storming of the Bastille]
*[[Minimum inferred regular expression]]
*[[Reynolds covering]] for [[context-free grammars]]
*[[Covering for linear grammars]]
*Structural inequivalence for [[linear grammars]]
*[[Regular grammar]] inequivalence
*Non-[[LR(K)]] context-free grammar
*[[Etol grammar]] non-emptiness
*[[Context-free programmed language]] membership
*[[Quasi-real-time language]] membership
*[[Etol language]] membership
*[[Tree transducer language]] membership


== Program optimization ==
[[Category:1789 in France]]
=== Code generation ===
[[Category:French Revolution]]
*[[Register sufficiency]]
[[Category:History of Paris]]
*[[Feasible register assignment]]
*[[Register sufficiency for loops]]
*[[Code generation on a one-register machine]]
*[[Code generation with unlimited registers]]
*[[Code generation for parallel assignments]]
*[[Code generation with address expressions]]
*[[Code generation with unfixed variable locations]]
*[[Ensemble computation]]
*[[Microcode bit optimization]]

=== Programs and schemes ===
*[[Inequivalence of programs with arrays]]
*[[Inequivalence of programs with assignments]]
*[[Inequivalence of finite memory programs]]
*[[Inequivalence of loop programs without nesting]]
*[[Inequivalence of simple functions]]
*[[Strong inequivalence of Ianov schemes]]
*[[Strong inequivalence for monadic recursion]]
*[[Non-containment for free B-schemes]]
*[[Non-freedom for loop-free program schemes]]
*[[Programs with formally recursive procedures]]

== Miscellaneous ==
*[[Cyclic ordering]]
*[[Non-liveness of free choice Petri nets]]
*[[Reachability for 1-conservative Petri nets]]
*[[Finite function generation]]
*[[Permutation generation]]
*[[Decoding of linear codes]]
*[[Shapley-Shubik voting power]]
*[[Clustering problem|Clustering]]
*[[Randomization test for matched pairs]]
*[[Maximum likelihood ranking]]
*[[Matrix domination]]
*[[Matrix cover]]
*[[Simply deviated disjunction]]
*[[Decision tree problem|Decision tree]]
*[[Minimum weight and/or graph solution]]
*[[Fault detection in logic circuits]]
*[[Fault detection in directed graphs]]
*[[Fault detection with test points]]

== See also ==

* [[Karp's 21 NP-complete problems]]
* [[List of PSPACE-complete problems]]

== References ==
<references/>
* {{cite book
| last = Garey
| first = M.R.
| authorlink = Michael Garey
| coauthors = [[David S. Johnson|Johnson, D.S.]]
| title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
| year = 1979
| publisher = W.H. Freeman
| location = New York
| isbn = 0-7167-1045-5
}} This book is a classic, developing the theory, then cataloguing ''many'' NP-Complete problems.
* {{cite conference
| last = Cook
| first = S.A.
| authorlink = Stephen A. Cook
| title = The complexity of theorem proving procedures
| booktitle = Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York
| year = 1971
| pages = 151–158
| url = http://dx.doi.org/10.1145/800157.805047
| doi = 10.1145/800157.805047
}}
* {{cite web
| last = Dunne
| first = P.E
| title = An annotated list of selected NP-complete problems
| publisher = COMP202, Dept. of Computer Science, [[University of Liverpool]]
| url = http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html
| accessdate = 2008-06-21
}}
* {{cite web
| last = Crescenzi
| first = P.
| coauthors = Kann, V.; Halldórsson, M.; [[Marek Karpinski|Karpinski, M.]]; Woeginger, G
| title = A compendium of NP optimization problems
| publisher = KTH NADA, Stockholm
| url = http://www.nada.kth.se/~viggo/problemlist/compendium.html
| accessdate = 2008-06-21
}}
* {{cite web
| last = Dahlke
| first = K
| title = NP-complete problems
| work = Math Reference Project
| url = http://www.mathreference.com/lan-cx-np,intro.html
| accessdate = 2008-06-21
}}
* {{cite web
| first = E
| last = Friedman
| title = Pearl puzzles are NP-complete
| year = 2002
| publisher = Stetson University, DeLand, Florida
| url = http://www.stetson.edu/~efriedma/papers/pearl/pearl.html
| accessdate = 2008-06-21
}}


[[Category:Mathematics-related lists|NP-complete problems]]
{{Link FA|es}}
[[Category:NP-complete problems|*]]


[[fr:Liste de problèmes NP-complets]]
[[bg:Бастилия]]
[[pl:Lista problemów NP-zupełnych]]
[[da:Bastillen]]
[[de:Sturm auf die Bastille]]
[[es:Toma de la Bastilla]]
[[eu:Bastillaren Hartzea]]
[[fr:Prise de la Bastille]]
[[it:Presa della Bastiglia]]
[[he:נפילת הבסטיליה]]
[[ka:ბასტილიის აღება]]
[[lb:Bastille#1789: De Stuerm op d'Bastille]]
[[nl:Bestorming van de Bastille]]
[[ja:バスティーユ襲撃]]
[[no:Bastillen]]
[[pl:Bastylia]]
[[pt:Bastilha]]
[[ru:Взятие Бастилии]]
[[sv:Bastiljen]]
[[th:การโจมตีคุกบาสตีย์]]
[[tr:Bastille hapishanesi baskını]]
[[zh:攻占巴士底狱]]

Revision as of 21:08, 10 October 2008

Here are some of the more commonly known problems that are NP-complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP-complete problems). Most of the problems in this list are taken from Garey and Johnson's seminal book Computers and Intractability: A Guide to the Theory of NP-Completeness, and are here presented in the same order and organization.

Computational geometry

Graph theory

Covering and partitioning

Subgraphs and supergraphs

Vertex ordering

Iso- and other morphisms

Miscellaneous

Network design

Spanning trees

Cuts and connectivity

Routing problems

Flow problems

Miscellaneous

Sets and partitions

Covering, hitting, and splitting

Weighted set problems

Set partitions

Storage and retrieval

Data storage

Compression and representation

Database problems

Sequencing and scheduling

Sequencing on one processor

Multiprocessor scheduling

Shop scheduling

Miscellaneous

Mathematical programming

Integer programming

Algebra and number theory

Divisibility problems

Solvability of equations

Miscellaneous

Games and puzzles

Alternating hitting set

Logic

Propositional logic

Miscellaneous

Automata and language theory

Automata theory

Formal languages

Program optimization

Code generation

Programs and schemes

Miscellaneous

See also

References

  1. ^ Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)
  2. ^ H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998
  3. ^ "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.
  • Garey, M.R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help) This book is a classic, developing the theory, then cataloguing many NP-Complete problems.
  • Cook, S.A. (1971). "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151–158. doi:10.1145/800157.805047. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
  • Dunne, P.E. "An annotated list of selected NP-complete problems". COMP202, Dept. of Computer Science, University of Liverpool. Retrieved 2008-06-21.
  • Crescenzi, P. "A compendium of NP optimization problems". KTH NADA, Stockholm. Retrieved 2008-06-21. {{cite web}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  • Dahlke, K. "NP-complete problems". Math Reference Project. Retrieved 2008-06-21.
  • Friedman, E (2002). "Pearl puzzles are NP-complete". Stetson University, DeLand, Florida. Retrieved 2008-06-21.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Storming_of_the_Bastille&oldid=244446458"