# completeness

Published articles for completeness.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## NP-hard does not mean hard

DevFeed: [NP-hard does not mean hard](<https://devfeed.tech/articles/np-hard-does-not-mean-hard-40418.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2017/12/29/np-hard-does-not-mean-hard/>)

Published: 2017-12-29T13:30:23Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Programming](<https://devfeed.tech/topics/programming.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [boolean](<https://devfeed.tech/tags/boolean.md>), [completeness](<https://devfeed.tech/tags/completeness.md>), [complexity-theory](<https://devfeed.tech/tags/complexity-theory.md>), [logic](<https://devfeed.tech/tags/logic.md>), [mario](<https://devfeed.tech/tags/mario.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [np-completeness](<https://devfeed.tech/tags/np-completeness.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [problems](<https://devfeed.tech/tags/problems.md>), [real-world](<https://devfeed.tech/tags/real-world.md>), [regular-languages](<https://devfeed.tech/tags/regular-languages.md>), [solve](<https://devfeed.tech/tags/solve.md>), [time](<https://devfeed.tech/tags/time.md>)

### AI overview

This article explains that NP-hardness is a worst-case mathematical property, not a claim that a problem is always difficult for humans or algorithms. Using Super Mario as an example, it shows how game levels can encode boolean logic and why solving the game in full generality would encompass hard computational problems, while ordinary real-world levels may still be solvable efficiently.

### Source excerpt

When NP-hardness pops up on the internet, say because some silly blogger wants to write about video games, it's often tempting to conclude that the problem being proved NP-hard is actually very hard! "Scientists proved Super Mario is NP-hard? I always knew there was a reason I wasn't very good at it!" Sorry, these two are unrelated. NP-hardness means hard in a narrow sense this post should hopefully make clear. After that, we'll explore what "hard" means in a mathematical sense that you can apply beyond NP-hardness to inform your work as a programmer.

## n-Colorability is Equivalent to Finite n-Colorability (A Formal Logic Proof)

DevFeed: [n-Colorability is Equivalent to Finite n-Colorability (A Formal Logic Proof)](<https://devfeed.tech/articles/n-colorability-is-equivalent-to-finite-n-colorability-a-formal-logic-proof-40241.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/09/04/n-colorability-is-equivalent-to-finite-n-colorability/>)

Published: 2011-09-04T22:41:27Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [completeness](<https://devfeed.tech/tags/completeness.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graph-coloring](<https://devfeed.tech/tags/graph-coloring.md>), [graph-theory](<https://devfeed.tech/tags/graph-theory.md>), [logic](<https://devfeed.tech/tags/logic.md>), [vertex](<https://devfeed.tech/tags/vertex.md>)

### AI overview

A formal logic proof shows that an infinite graph is n-colorable exactly when every finite subgraph is n-colorable. The proof encodes valid colorings as propositional formulas and applies the Compactness Theorem.

### Source excerpt

Warning: this proof requires a bit of familiarity with the terminology of propositional logic and graph theory. Problem: Let $ G$ be an infinite graph. Show that $ G$ is $ n$-colorable if and only if every finite subgraph $ G_0 \subset G$ is $ n$-colorable. Solution: One of the many equivalent versions of the Compactness Theorem for the propositional calculus states that if $ \Sigma \subset \textup{Prop}(A)$, where $ A$ is a set of propositional atoms, then $ \Sigma$ is satisfiable if and only if any finite subset of $ \Sigma$ is satisfiable.