go-v.orgcodex
Menu
Page tools

codex · Philosophy

Non-constructive algorithm existence proofs

The vast majority of positive results about computational problems are constructive proofs, i.e., a computational problem is proved to be solvable by showing an algorithm that solves it; a computational problem is shown to be in P by showing an algorithm that solves it in time that is polynomial in the size of the input; etc. However, there are several non-constructive results, where an algorithm is proved to exist without showing the algorithm itself. Several techniques are used to provide such existence proofs.

Wikipedia contributors, "Non-constructive algorithm existence proofs", Wikipedia, revision 1322626215, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex