Werner Sombart and List of NP-complete problems: Difference between pages

From Wikipedia, the free encyclopedia
(Difference between pages)
Content deleted Content added
VisualWikitext
m Reverted edits by Kipperfield (talk) to last version by 38.100.43.50
 
m →‎Formal languages: no, regular expression inequivalence is PSPACE-complete!
 
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_Scientist
| name = Werner Sombart
| image = werner_sombart.jpg|300px
| image_width = 300px
| caption =
| birth_date = {{birth date|1863|1|19|mf=y}}
| birth_place = [[Ermsleben]]
| death_date = {{death date and age|1941|5|18|1863|1|19|mf=y}}
| death_place = [[Berlin]]
| nationality = [[Image:Flag of Germany.svg|20px|]] [[Germany|German]]
| field = [[economics]], [[sociology]], [[history]]
| work_institution = [[University of Wrocław|University of Breslau]]<br />[[Humboldt University of Berlin|Handelshochschule Berlin]]<br />
[[Humboldt University of Berlin|Friedrich-Wilhelms-Universität]]
| doctoral_advisor = [[Gustav von Schmoller]]<br />[[Adolph Wagner]]
| doctoral_students = [[Wassily Leontief]] <br\> [[Richard Löwenthal]]
| known_for =
| prizes =
| religion =
}}
'''Werner Sombart''' ([[19 January]] [[1863]] &ndash; [[18 May]] [[1941]]) was a [[Germany|German]] [[economics|economist]] and [[sociology|sociologist]], the head of the “Youngest [[Historical School]]” and one of the leading Continental European social scientists during the first quarter of the 20th century.


{{Expand list|date=August 2008}}
== Life and work==
=== Early career, socialism and economics ===


== [[Computational geometry]]==
He was born in [[Ermsleben]], Harz, as the son of a wealthy liberal politician, industrialist, and estate-owner, Anton Ludwig Sombart, and studied at the universities of [[Pisa]], [[Berlin]], and [[Rome]], both [[law]] and [[economics]]. In 1888, he received his [[Doctor of Philosophy|Ph.D.]] from Berlin under the direction of [[Gustav von Schmoller]] and [[Adolph Wagner]], then the most eminent German economists.
*[[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 ==
As an economist and especially social activist, Sombart was then seen as radically left-wing, and so only received — after some practical work as head lawyer of the [[Bremen (city)|Bremen]] [[Chamber of Commerce]] — a junior professorship at the out-of-the-way University of [[Breslau]]. Although faculties at such eminent universities as [[Heidelberg]] and [[Freiburg]] called him on chairs, the respective governments always vetoed this. Sombart, at that time, was an important [[Marxian]], someone who used and interpreted [[Karl Marx]] — to the point that [[Friedrich Engels]] called him the only German professor who understood ''[[Das Kapital]]''. Sombart called himself a "convinced [[Marxist]]".<ref>Abram L. Harris, 'Sombart and German (National) Socialism', ''The Journal of Political Economy'', Vol. 50, No. 6. (Dec., 1942), p. 807.</ref>
=== 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 ===
Sombart was the first sociologist to devote a whole book to the concept of [[social movement]] in his 1896 published ''Sozialismus und soziale Bewegung''. His understanding of social movements is inspired by [[Lorenz von Stein]] and Marx. For him, the raising worker’s movement was a result of the inherent contradictions of capitalism. The proletarian situation created a “love for the mass”, which together with the tendency “to a communistic way of life” in social production were the prime features of the social movement.
*[[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 ===
In 1902, his ''magnum opus'', ''Der moderne Kapitalismus'', appeared in six volumes. It is a systematic history of economics and economic development through the centuries and very much a work of the [[Historical School]]. Although later much disparaged by [[Neoclassical economics|neo-classical]] economists, and much criticized in specific points, it is still today a standard work with important ramifications for, e.g., the ''[[Annales school]]'' ([[Fernand Braudel]]).
*[[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 ===
In 1906, Sombart accepted a call to a full professorship at the Berlin School of Commerce, an inferior institution to Breslau but closer to political “action” than Breslau. Here, i.a., companion volumes to ''Modern Capitalism'' dealing with luxury, fashion, and war as economic paradigms appeared; especially the former two are the key works on the subject until today. In 1906 his ''Why is there no Socialism in the United States?'' also appeared, which, while naturally having been questioned since then, is a classical work on American [[exceptionalism]] in this respect.
*[[Subgraph isomorphism problem|Subgraph isomorphism]]
*[[Largest common subgraph]]
*[[Maximum subgraph matching]]
*[[Graph contractability]]
*[[Graph homomorphism]]
*[[Digraph D-morphism]]


=== Middle career and sociology ===
=== Miscellaneous ===
*[[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 ==
Finally, in 1917, Sombart became professor at the [[Humboldt University|Friedrich-Wilhelms-Universität]], then the pre-eminent university in Europe if not in the world, succeeding his mentor [[Adolph Wagner]]. He remained on the chair until 1931 but continued teaching until 1940. During that period, he was also one of the leading sociologists around, much more prominent than his friend [[Max Weber]], who later of course eclipsed him to the point that Sombart is virtually forgotten in that field by now. Sombart's insistence on Sociology as a part of the [[Humanities]] (''Geisteswissenschaften''), necessarily so because it dealt with human beings and therefore required inside, empathic "''Verstehen''" rather than the outside, objectivizing "''Begreifen''" (both German words translate as "understanding" into English), became extremely unpopular already during his lifetime, because it was the opposite of the "scientification" of the social sciences (jocularly referred to as "physics envy"), in the tradition of [[Auguste Comte]], [[Émile Durkheim]] and [[Max Weber|Weber]] (although this is a misunderstanding; Weber largely shared Sombart's views in these matters), which became fashionable during this time and has more or less remained so until today. However, because Sombart's approach has much in common with [[Hans-Georg Gadamer]]'s [[Hermeneutics]], which likewise is a ''Verstehen''-based approach to understanding the world, he is coming back in some sociological and even philosophical circles that are sympathetic to that approach and critical towards the scientification of the world. Sombart's key sociological essays are collected in his posthumous 1956 work, ''Noo-Soziologie''.
=== 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]]


=== Late career and National Socialism ===
=== Cuts and connectivity ===
*[[Graph partitioning]]
During the [[Weimar Republic]], Sombart moved to the political right; his relation to [[Nazism]] is heavily debated until today. His 1938 [[anthropology]] book, ''Vom Menschen'', is clearly anti-Nazi, and was indeed hindered in publication and distribution by the Nazis. His earlier book, ''Die Juden und das Wirtschaftsleben'' (1911), is a pendant to [[Max Weber]]'s study on the connection between [[Protestantism]] (especially [[Calvinism]]) and [[Capitalism]], only that Sombart puts the Jews at the core of the development. This book was seen as [[philo-semitism|philosemitic]] when it appeared, but several contemporary Jewish scholars describe it as [[anti-semitism|antisemitic]], at least in effect. In his attitude towards the Nazis, he is often likened to [[Martin Heidegger]] and his younger friend, colleague and adorer of his wife [[Carl Schmitt]], but it is clear that, while the latter two tried to be the vanguard thinkers for the [[Third Reich]] in their field and only became critical when they were too individualistic and elbowed out from their power positions, Sombart was always much more ambivalent. Sombart had many, indeed more than proportional, Jewish students, most of which felt after the war moderately positive about him, although he clearly was no hero nor resistance fighter.
*[[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 ===
In 1934 he published ''Deutscher Sozialismus'' where he claimed a "new spirit" was beginning to "rule mankind". The age of capitalism and proletarian socialism was over and with "German socialism" ([[Nazism|National-Socialism]]) taking over. This German socialism puts the "welfare of the whole above the welfare of the individual".<ref>Harris, pp. 808-9.</ref> German socialism must effect a "total ordering of life" with a "planned economy in accordance with state regulations".<ref>Harris, pp. 810-11.</ref> The new legal system will confer on individuals "no rights but only duties" and that "the state should never evaluate individual persons as such, but only the group which represents these persons".<ref>Harris, p. 811.</ref> German socialism is accompanied by the ''Volksgeist'' (national spirit) which is not racial in the biological sense but metaphysical: "the German spirit in a Negro is quite as much within the realm of possibility as the Negro spirit in a German".<ref>Harris, pp. 812-13.</ref> The antithesis of the German spirit is the Jewish spirit, which is not a matter of being born Jewish or believing in Judaism but is a capitalistic spirit.<ref>Harris, p. 813.</ref> The English people possess the Jewish spirit and the "chief task" of the German people and National Socialism is to destroy the Jewish spirit.<ref>Harris, p. 813.</ref>
*[[Bottleneck traveling salesman]]
*[[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]]


=== Sombart today ===
=== Flow problems ===
*[[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 ===
Sombart's legacy today is difficult to ascertain, because the alleged Nazi affiliations have made an objective reevaluation difficult (while his earlier Socialist ones harmed him with the more bourgeois circles), especially in Germany. As has been stated, in [[economic history]], his "Modern Capitalism" is regarded as a milestone and inspiration, although many details have been questioned. Key insights from his economic work concern the - recently again validated - discovery of the emergence of double-entry [[accounting]] as a key precondition for [[Capitalism]] and the interdisciplinary study of the [[City]] in the sense of [[urban studies]]. He also coined the term and concept of [[creative destruction]] which is a key ingredient of [[Joseph Schumpeter]]'s theory of [[innovation]] (Schumpeter actually borrowed much from Sombart, not always with proper reference). In Sociology, mainstream proponents still regard Sombart as a 'minor figure' and his sociological theory an oddity; today it is more philosophical sociologists and culturologists who, together with heterodox economists, use his work. Sombart has always been very popular in [[Japan]]. One of the reasons of a lack of reception in the United States is that most of his works were for a long time not translated into English - in spite of, and excluding as far as the reception is concerned, the classic study on ''Why there is no Socialism in America''.
*[[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]]


== Bibliography ==
== Sets and partitions ==
=== Works by Sombart ===
=== Covering, hitting, and splitting ===
*[[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 ===
*Sombart, Werner (1905) [1896]: Sozialismus und soziale Bewegung. Jena: Verlag von Gustav Fischer.
*[[Partition problem|Partition]]
*Sombart, Werner (1906): ''Das Proletariat. Bilder und Studien.'' Die Gesellschaft, vol. 1. Berlin: Rütten & Loening.
*[[Subset sum problem|Subset sum]]
*Sombart, Werner (1906): ''Warum gibt es in den Vereinigten Staaten keinen Sozialismus?'' Tübingen: Mohr. Several English translations, incl. (1976): ''Why is there No Socialism in the United States.'' New York: Sharpe.
*[[Subset product]]
*Sombart, Werner (1911): ''Die Juden und das Wirtschaftsleben.'' Leipzig: Duncker"
*[[3-partition]]
''The Jews and Modern Capitalism.'' http://mailstar.net/sombart-jews-capitalism.pdf
*[[Numerical 3-dimensional matching]]
*Sombart, Werner: ''Der moderne Kapitalismus. Historisch-systematische Darstellung des gesamteuropäischen Wirtschaftslebens von seinen Anfängen bis zur Gegenwart.'' Final edn. 1916, repr. 1969, paperback edn. (3 vols. in 6): 1987 Munich: dtv. (Also in Spanish; no English translation yet.)
*[[Numerical matching with target sums]]
* Sombart, Werner (1913): ''Luxus und Kapitalismus.'' München: Duncker & Humblot, 1922. English translation: ''Luxury and capitalism.'' Ann Arbor: University of Michigan Press.
*[[Expected component sum]]
* Sombart, Werner (1934): ''Deutscher Sozialismus.'' Charlottenburg: Buchholz & Weisswange. English translation (1937, 1969): ''A New Social Philosophy.'' New York: Greenwood.
*[[Minimum sum of squares]]
*Sombart, Werner (1938): ''Vom Menschen. Versuch einer geisteswissenschaftlichen Anthropologie.'' Berlin: Duncker & Humblot.
*[[Kth largest subset]]
*Sombart, Werner (1956): ''Noo-Soziologie.'' Berlin: Duncker & Humblot.
*[[Kth largest m-tuple]]
*Sombart, Werner (2001): ''Economic Life in the Modern Age.'' Reiner Grundmann, eds. New Brunswick: Transaction. (New English translations of key articles and chapters by Sombart, including (1906) in full and the segment defining Capitalism from (1916))


=== Works about Sombart ===
=== Set partitions ===
*[[Median partition]]


== Storage and retrieval ==
*Appel, Michael (1992): ''Werner Sombart: Historiker und Theoretiker des modernen Kapitalismus.'' Marburg: Metropolis.
=== Data storage ===
*Backhaus, Jürgen G. (1996), ed. ''Werner Sombart (1863-1941): Social Scientist.'' 3 vols. Marburg: Metropolis. (The standard, all-encompassing work on Sombart in English.)
*[[Bin packing problem|Bin packing]]
*Backhaus, Jürgen G. (2000), ed. ''Werner Sombart (1863-1941): Klassiker der Sozialwissenschaft. Eine kritische Bestandsaufnahme.'' Marburg: Metropolis.
*[[Dynamic storage allocation]]
*Brocke, Bernhard vom (1987), ed.: ''Sombarts'' Moderner Kapitalismus. ''Materialien zur Kritik und Rezeption.'' München: dtv
*[[Pruned trie space minimization]]
*Drechsler, W. "Zu Werner Sombarts Theorie der Soziologie und zu seiner Biographie", in ''[http://www.metropolis-verlag.de/cgi-local/katalog.cgi?/data/d275.html Werner Sombart: Klassiker der Sozialwissenschaft. Eine kritische Bestandsaufnahme]'', Marburg: Metropolis, 2000, pp. 83-100.
*[[Expected retrieval cost]]
*Lenger, Friedrich (1994): ''Werner Sombart, 1863-1941. Eine Biographie.'' München: Beck.
*[[Rooted tree storage assignment]]
*Muller, Jerry Z., 2002. ''The Mind and the Market: Capitalism in Western Thought''. Anchor Books.
*[[Multiple copy file allocation]]
*Nussbaum, Frederick Louis (1933): ''A History of the Economic Institutions of Modern Europe: An Introduction of 'Der Moderne Kapitalismus' of Werner Sombart.'' New York: Crofts.
*[[Capacity assignment]]
*{{cite book|author=Kevin Repp|title=Reformers, Critics, and the Paths of German Modernity: Anti-Politics and the Search for Alternatives, 1890-1914|year=2000|publisher=Harvard University Press|location=Boston, MA.|id=ISBN 0-674-00057-9}}
*[[:de:Nicolaus Sombart|Sombart, Nicolaus]] (1991): ''Jugend in Berlin, 1933-1943. Ein Bericht.'' Frankfurt/Main: Fischer.
*[[:de:Nicolaus Sombart|Sombart, Nicolaus]] (1991): ''Die deutschen Männer und ihre Feinde. [[Carl Schmitt]] - ein deutsches Schicksal zwischen Männerbund und Matriachatsmythos.'' Munich: Hanser.


=== Compression and representation ===
==Notes==
*[[Shortest common supersequence]]
<references/>
*[[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 ===
==External links==
*[[Minimum cardinality key]]
{{wikiquote}}
*[[Additional key]]
{{History of economic thought}}
*[[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 ==
<!-- Metadata: see [[Wikipedia:Persondata]] -->
=== 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 ===
{{BD|1863|1941|Sombart, Werner}}
*[[Multiprocessor scheduling]]
*[[Precedence constrained scheduling]]
*[[Resource constrained scheduling]]
*[[Scheduling with individual deadlines]]
*[[Preemptive scheduling]]
*[[Scheduling to minimize weighted completion time]]


=== Shop scheduling ===
{{Persondata
*[[Open-shop scheduling]]
|NAME= Sombart, Werner
*[[Flow-shop scheduling]]
|ALTERNATIVE NAMES=
*[[No-wait flow-shop scheduling]]
|SHORT DESCRIPTION= [[Germany|German]] economist , sociologist , historian
*[[Two-processor flow-shop with bounded buffer]]
|DATE OF BIRTH= [[January 19]], [[1863]]
*[[Job-shop scheduling]]
|PLACE OF BIRTH= [[Ermsleben]]

|DATE OF DEATH= [[May 18]], [[1941]]
=== Miscellaneous ===
|PLACE OF DEATH= [[Berlin]]
*[[Timetable design]]
*[[Staff scheduling]]
*[[Production planning]]
*[[Deadlock avoidance]]

== Mathematical programming ==
[[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 ==
=== 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 ===
*[[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 ===
*[[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 ==
[[Alternating hitting set]]
*[[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]]

== Logic ==
=== Propositional logic ===
*[[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 ===
*[[Modal logic]] S5-Satisfiability
*[[Negation-free logic]]
*Conjunctive satisfiability with functions and inequalities
*[[Minimum axiom set]]
*[[First order subsumption]]
*[[Second order instantiation]]

== Automata and language theory ==
=== Automata theory ===
*Two-way [[finite state automaton]] non-emptiness
*[[Quasi-realtime automaton]] acceptance
*Reduction of incompletely specified automata
*[[Minimum inferred finite state automaton]]

=== Formal languages ===
*[[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 ==
=== Code generation ===
*[[Register sufficiency]]
*[[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
[[Category:People from the Province of Saxony]]
| last = Dunne
[[Category:German economists]]
| first = P.E
[[Category:German sociologists]]
| title = An annotated list of selected NP-complete problems
[[Category:Humboldt University of Berlin alumni]]
| publisher = COMP202, Dept. of Computer Science, [[University of Liverpool]]
[[Category:Humboldt University of Berlin faculty]]
| 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]]
[[Category:NP-complete problems|*]]


[[fr:Liste de problèmes NP-complets]]
[[de:Werner Sombart]]
[[pl:Lista problemów NP-zupełnych]]
[[es:Werner Sombart]]
[[fr:Werner Sombart]]
[[it:Werner Sombart]]
[[lb:Werner Sombart]]
[[ja:ヴェルナー・ゾンバルト]]
[[pl:Werner Sombart]]
[[pt:Werner Sombart]]
[[ro:Werner Sombart]]
[[ru:Зомбарт, Вернер]]
[[sk:Werner Sombart]]
[[sv:Werner Sombart]]

Revision as of 22:12, 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=Werner_Sombart&oldid=244457623"