# P vs. NP, A Primer (And a Proof Written in Racket)

DevFeed: [P vs. NP, A Primer (And a Proof Written in Racket)](<https://devfeed.tech/articles/p-vs-np-a-primer-and-a-proof-written-in-racket-40263.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/02/23/p-vs-np-a-primer-and-a-proof-written-in-racket/>)

Published: 2012-02-23T19:57:35Z

Content type: tutorial

Language: en

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

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

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [big-o-notation](<https://devfeed.tech/tags/big-o-notation.md>), [class](<https://devfeed.tech/tags/class.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [computing](<https://devfeed.tech/tags/computing.md>), [decidability](<https://devfeed.tech/tags/decidability.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [fast](<https://devfeed.tech/tags/fast.md>), [halting-problem](<https://devfeed.tech/tags/halting-problem.md>), [input](<https://devfeed.tech/tags/input.md>), [language](<https://devfeed.tech/tags/language.md>), [machine](<https://devfeed.tech/tags/machine.md>), [np-completeness](<https://devfeed.tech/tags/np-completeness.md>), [p-versus-np](<https://devfeed.tech/tags/p-versus-np.md>), [primer](<https://devfeed.tech/tags/primer.md>), [racket](<https://devfeed.tech/tags/racket.md>), [solve](<https://devfeed.tech/tags/solve.md>), [theory](<https://devfeed.tech/tags/theory.md>), [turing-machine](<https://devfeed.tech/tags/turing-machine.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

## AI overview

A primer on the distinction between decidability and computational efficiency, introducing the complexity class P and its definition in terms of polynomial-time decision by a Turing machine. It also discusses efficient algorithms and gives a card-sorting example.

## Source excerpt

Decidability Versus Efficiency In the early days of computing theory, the important questions were primarily about decidability. What sorts of problems are beyond the power of a Turing machine to solve? As we saw in our last primer on Turing machines, the halting problem is such an example: it can never be solved a finite amount of time by a Turing machine. However, more recently (in the past half-century) the focus of computing theory has shifted away from possibility in favor of determining feasibility.