About: Non-constructive algorithm existence proofs

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Non-constructive algorithm existence proofs Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

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 (complexity) 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.

Attributes	Values
rdfs:label	Non-constructive algorithm existence proofs (en)
rdfs:comment	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 (complexity) 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. (en)
sameAs	Non-constructive algorithm existence proofs
dbp:wikiPageUsesTemplate	dbt:Cite_web dbt:Reflist
Subject	Computational complexity theory Constructivism (mathematics)
gold:hypernym	Proofs
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs?oldid=992950035&ns=0
Wikipage page ID	44465987 (xsd:integer)
page length (characters) of wiki page	8866 (xsd:nonNegativeInteger)
Wikipage revision ID	992950035 (xsd:integer)
Link from a Wikipage to another Wikipage	Smooth number Algorithm Computational complexity theory Constructivism (mathematics) P (complexity) Quantum complexity theory Winning Ways for Your Mathematical Plays Decision tree model Prime number Robertson–Seymour theorem Computational problem Constructive proof John Horton Conway Michael Fellows Michael Langston Elwyn Berlekamp Graph minor Graph theory Sylver coinage Existence theorem Stack Exchange Law of excluded middle Richard K. Guy
has abstract	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 (complexity) 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs
is Wikipage redirect of	Pure existence theorem of algorithm Pure existence theorem of an algorithm
is Link from a Wikipage to another Wikipage of	Constructive proof

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software