Non-constructive algorithm existence proofs - Revision history

CitationNeededLOL: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-05-05T02:23:50Z

Link suggestions feature: 2 links added.

← Previous revision		Revision as of 02:23, 5 May 2025
Line 6:		Line 6:

	===In combinatorial game theory===		===In combinatorial game theory===
	A simple example of a non-constructive algorithm was published in 1982 by [[Elwyn R. Berlekamp]], [[John H. Conway]], and [[Richard K. Guy]], in their book ''[[Winning Ways for Your Mathematical Plays]]''. It concerns the game of [[Sylver Coinage]], in which players take turns specifying a positive integer that cannot be expressed as a sum of previously specified values, with a player losing when they are forced to specify the number 1. There exists an algorithm (given in the book as a flow chart) for determining whether a given first move is winning or losing: if it is a [[prime number]] greater than three, or one of a finite set of [[smooth number\|3-smooth numbers]], then it is a winning first move, and otherwise it is losing. However, the finite set is not known.		A simple example of a non-constructive algorithm was published in 1982 by [[Elwyn R. Berlekamp]], [[John H. Conway]], and [[Richard K. Guy]], in their book ''[[Winning Ways for Your Mathematical Plays]]''. It concerns the game of [[Sylver Coinage]], in which players take turns specifying a positive [[integer]] that cannot be expressed as a sum of previously specified values, with a player losing when they are forced to specify the number 1. There exists an algorithm (given in the book as a flow chart) for determining whether a given first move is winning or losing: if it is a [[prime number]] greater than three, or one of a [[finite set]] of [[smooth number\|3-smooth numbers]], then it is a winning first move, and otherwise it is losing. However, the finite set is not known.

	===In graph theory===		===In graph theory===

David Eppstein: dab

2025-03-26T06:06:38Z

dab

← Previous revision		Revision as of 06:06, 26 March 2025
Line 61:		Line 61:
	== Additional examples ==		== Additional examples ==
	* Some computational problems can be shown to be decidable by using the [[Law of Excluded Middle#Use in computer science proofs\|Law of Excluded Middle]]. Such proofs are usually not very useful in practice, since the problems involved are quite artificial.		* Some computational problems can be shown to be decidable by using the [[Law of Excluded Middle#Use in computer science proofs\|Law of Excluded Middle]]. Such proofs are usually not very useful in practice, since the problems involved are quite artificial.
	* An example from [[Quantum complexity theory]] (related to [[Quantum query complexity]]) is given in.<ref>{{Cite journal \| doi = 10.4086/cjtcs.2013.004\| year = 2013\| last1 = Kimmel \| first1 = S.\| title = Quantum Adversary (Upper) Bound\| journal = Chicago Journal of Theoretical Computer Science\| volume = 19\| pages = 1–14\| arxiv = 1101.0797\| s2cid = 119264518}}</ref>		* An example from [[Quantum complexity theory]] (related to [[Quantum complexity theory#Quantum query complexity\|Quantum query complexity]]) is given in.<ref>{{Cite journal \| doi = 10.4086/cjtcs.2013.004\| year = 2013\| last1 = Kimmel \| first1 = S.\| title = Quantum Adversary (Upper) Bound\| journal = Chicago Journal of Theoretical Computer Science\| volume = 19\| pages = 1–14\| arxiv = 1101.0797\| s2cid = 119264518}}</ref>

	== References ==		== References ==

TTWIDEE: Simplified link text

2024-10-28T10:39:36Z

Simplified link text

← Previous revision		Revision as of 10:39, 28 October 2024
Line 1:		Line 1:
	The vast majority of positive results about [[computational problem]]s are [[constructive proof]]s, 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.		The vast majority of positive results about [[computational problem]]s are [[constructive proof]]s, 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)\|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.		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.

Kaltenmeyer: an -> a

2023-12-18T20:18:42Z

an -> a

← Previous revision		Revision as of 20:18, 18 December 2023
Line 49:		Line 49:
	How many queries do you need? Obviously, ''n'' queries are always sufficient, because you can use ''n'' queries asking for the "sum" of a single element. But when ''d'' is sufficiently small, it is possible to do better. The general idea is as follows.		How many queries do you need? Obviously, ''n'' queries are always sufficient, because you can use ''n'' queries asking for the "sum" of a single element. But when ''d'' is sufficiently small, it is possible to do better. The general idea is as follows.

	Every query can be represented as a 1-by-''n'' vector whose elements are all in the set {0,1}. The response to the query is just the [[dot product]] of the query vector by ''v''. Every set of ''k'' queries can be represented by an ''k''-by-''n'' matrix over {0,1}; the set of responses is the product of the matrix by ''v''.		Every query can be represented as a 1-by-''n'' vector whose elements are all in the set {0,1}. The response to the query is just the [[dot product]] of the query vector by ''v''. Every set of ''k'' queries can be represented by a ''k''-by-''n'' matrix over {0,1}; the set of responses is the product of the matrix by ''v''.

	A matrix ''M'' is "good" if it enables us to uniquely identify ''v''. This means that, for every vector ''v'', the product ''M v'' is unique. A matrix ''M'' is "bad" if there are two different vectors, ''v'' and ''u'', such that ''M v'' = ''M u''.		A matrix ''M'' is "good" if it enables us to uniquely identify ''v''. This means that, for every vector ''v'', the product ''M v'' is unique. A matrix ''M'' is "bad" if there are two different vectors, ''v'' and ''u'', such that ''M v'' = ''M u''.

OAbot: Open access bot: doi updated in citation with #oabot.

2023-08-14T13:05:31Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 13:05, 14 August 2023
Line 9:		Line 9:

	===In graph theory===		===In graph theory===
	Non-constructive algorithm proofs for problems in [[graph theory]] were studied beginning in 1988 by [[Michael Fellows]] and [[Michael Langston]].<ref name=FellowsLangston1988>{{Cite journal \| doi = 10.1145/44483.44491\| title = Nonconstructive tools for proving polynomial-time decidability\| journal = Journal of the ACM\| volume = 35\| issue = 3\| pages = 727\| year = 1988\| last1 = Fellows \| first1 = M. R. \| last2 = Langston \| first2 = M. A. \| s2cid = 16587284}}</ref>		Non-constructive algorithm proofs for problems in [[graph theory]] were studied beginning in 1988 by [[Michael Fellows]] and [[Michael Langston]].<ref name=FellowsLangston1988>{{Cite journal \| doi = 10.1145/44483.44491\| title = Nonconstructive tools for proving polynomial-time decidability\| journal = Journal of the ACM\| volume = 35\| issue = 3\| pages = 727\| year = 1988\| last1 = Fellows \| first1 = M. R. \| last2 = Langston \| first2 = M. A. \| s2cid = 16587284\| doi-access = free}}</ref>

	A common question in graph theory is whether a certain input graph has a certain property. For example:		A common question in graph theory is whether a certain input graph has a certain property. For example:

Kku: link [dD]ot product

2023-01-26T15:07:47Z

link [dD]ot product

← Previous revision		Revision as of 15:07, 26 January 2023
Line 49:		Line 49:
	How many queries do you need? Obviously, ''n'' queries are always sufficient, because you can use ''n'' queries asking for the "sum" of a single element. But when ''d'' is sufficiently small, it is possible to do better. The general idea is as follows.		How many queries do you need? Obviously, ''n'' queries are always sufficient, because you can use ''n'' queries asking for the "sum" of a single element. But when ''d'' is sufficiently small, it is possible to do better. The general idea is as follows.

	Every query can be represented as a 1-by-''n'' vector whose elements are all in the set {0,1}. The response to the query is just the dot product of the query vector by ''v''. Every set of ''k'' queries can be represented by an ''k''-by-''n'' matrix over {0,1}; the set of responses is the product of the matrix by ''v''.		Every query can be represented as a 1-by-''n'' vector whose elements are all in the set {0,1}. The response to the query is just the [[dot product]] of the query vector by ''v''. Every set of ''k'' queries can be represented by an ''k''-by-''n'' matrix over {0,1}; the set of responses is the product of the matrix by ''v''.

	A matrix ''M'' is "good" if it enables us to uniquely identify ''v''. This means that, for every vector ''v'', the product ''M v'' is unique. A matrix ''M'' is "bad" if there are two different vectors, ''v'' and ''u'', such that ''M v'' = ''M u''.		A matrix ''M'' is "good" if it enables us to uniquely identify ''v''. This means that, for every vector ''v'', the product ''M v'' is unique. A matrix ''M'' is "bad" if there are two different vectors, ''v'' and ''u'', such that ''M v'' = ''M u''.

AltoStev: /* In combinatorial game theory */ Correct capitalization

2022-04-06T16:43:36Z

In combinatorial game theory: Correct capitalization

← Previous revision		Revision as of 16:43, 6 April 2022
Line 6:		Line 6:

	===In combinatorial game theory===		===In combinatorial game theory===
	A simple example of a non-constructive algorithm was published in 1982 by [[Elwyn R. Berlekamp]], [[John H. Conway]], and [[Richard K. Guy]], in their book ''[[Winning Ways for ~~your~~ Mathematical Plays]]''. It concerns the game of [[Sylver Coinage]], in which players take turns specifying a positive integer that cannot be expressed as a sum of previously specified values, with a player losing when they are forced to specify the number 1. There exists an algorithm (given in the book as a flow chart) for determining whether a given first move is winning or losing: if it is a [[prime number]] greater than three, or one of a finite set of [[smooth number\|3-smooth numbers]], then it is a winning first move, and otherwise it is losing. However, the finite set is not known.		A simple example of a non-constructive algorithm was published in 1982 by [[Elwyn R. Berlekamp]], [[John H. Conway]], and [[Richard K. Guy]], in their book ''[[Winning Ways for Your Mathematical Plays]]''. It concerns the game of [[Sylver Coinage]], in which players take turns specifying a positive integer that cannot be expressed as a sum of previously specified values, with a player losing when they are forced to specify the number 1. There exists an algorithm (given in the book as a flow chart) for determining whether a given first move is winning or losing: if it is a [[prime number]] greater than three, or one of a finite set of [[smooth number\|3-smooth numbers]], then it is a winning first move, and otherwise it is losing. However, the finite set is not known.

	===In graph theory===		===In graph theory===

93.85.185.151: /* Counting the algorithms */

2020-12-08T00:12:00Z

Counting the algorithms

← Previous revision		Revision as of 00:12, 8 December 2020
Line 51:		Line 51:
	Every query can be represented as a 1-by-''n'' vector whose elements are all in the set {0,1}. The response to the query is just the dot product of the query vector by ''v''. Every set of ''k'' queries can be represented by an ''k''-by-''n'' matrix over {0,1}; the set of responses is the product of the matrix by ''v''.		Every query can be represented as a 1-by-''n'' vector whose elements are all in the set {0,1}. The response to the query is just the dot product of the query vector by ''v''. Every set of ''k'' queries can be represented by an ''k''-by-''n'' matrix over {0,1}; the set of responses is the product of the matrix by ''v''.

	A matrix ''M'' is "good" if it enables us to uniquely identify ''v''. This means that, for every vector ''v'', the product ''M v'' is ~~different~~. A matrix ''M'' is "bad" if there are two different vectors, ''v'' and ''u'', such that ''M v'' = ''M u''.		A matrix ''M'' is "good" if it enables us to uniquely identify ''v''. This means that, for every vector ''v'', the product ''M v'' is unique. A matrix ''M'' is "bad" if there are two different vectors, ''v'' and ''u'', such that ''M v'' = ''M u''.

	Using some algebra, it is possible to bound the number of "bad" matrices. The bound is a function of ''d'' and ''k''. Thus, for a sufficiently small ''d'', there must be a "good" matrix with a small ''k'', which corresponds to an efficient algorithm for solving the identification problem.		Using some algebra, it is possible to bound the number of "bad" matrices. The bound is a function of ''d'' and ''k''. Thus, for a sufficiently small ''d'', there must be a "good" matrix with a small ''k'', which corresponds to an efficient algorithm for solving the identification problem.

93.85.185.151: /* In graph theory */

2020-12-08T00:08:38Z

In graph theory

← Previous revision		Revision as of 00:08, 8 December 2020
Line 20:		Line 20:
	However, there is a non-constructive proof that shows that linkedness is decidable in polynomial time. The proof relies on the following facts:		However, there is a non-constructive proof that shows that linkedness is decidable in polynomial time. The proof relies on the following facts:

	* The set of graphs for which the answer is "yes" is closed under taking [[minor (graph theory)\|minors]]. I.e., if a graph G can be embedded linklessly in 3-d space, then every minor of G can also be embedded linklessly.		* The set of graphs for which the answer is "yes" is closed under taking [[minor (graph theory)\|minors]]. I. e., if a graph G can be embedded linklessly in 3-d space, then every minor of G can also be embedded linklessly.
	* For every two graphs G and H, it is possible to find in polynomial time whether H is a minor of G.		* For every two graphs ''G'' and ''H'', it is possible to find in polynomial time whether ''H'' is a minor of ''G''.
	* By [[Robertson–Seymour theorem]], any set of finite graphs contains only a finite number of minor-minimal elements. In particular, the set of "yes" instances has a finite number of minor-minimal elements.		* By [[Robertson–Seymour theorem]], any set of finite graphs contains only a finite number of minor-minimal elements. In particular, the set of "yes" instances has a finite number of minor-minimal elements.

	Given an input graph G, the following "algorithm" solves the above problem:		Given an input graph ''G'', the following "algorithm" solves the above problem:
	:: For every minor-minimal element H:		:: For every minor-minimal element ''H'':
	:::: If H is a minor of G then return "yes".		:::: If ''H'' is a minor of ''G'' then return "yes".
	:: return "no".		:: return "no".

Citation bot: Add: url, s2cid. | You can use this bot yourself. Report bugs here. | Suggested by SemperIocundus | via #UCB_webform

2020-09-04T23:54:40Z

Add: url, s2cid. | You can use this bot yourself. Report bugs here. | Suggested by SemperIocundus | via #UCB_webform

← Previous revision		Revision as of 23:54, 4 September 2020
Line 9:		Line 9:

	===In graph theory===		===In graph theory===
	Non-constructive algorithm proofs for problems in [[graph theory]] were studied beginning in 1988 by [[Michael Fellows]] and [[Michael Langston]].<ref name=FellowsLangston1988>{{Cite journal \| doi = 10.1145/44483.44491\| title = Nonconstructive tools for proving polynomial-time decidability\| journal = Journal of the ACM\| volume = 35\| issue = 3\| pages = 727\| year = 1988\| last1 = Fellows \| first1 = M. R. \| last2 = Langston \| first2 = M. A. }}</ref>		Non-constructive algorithm proofs for problems in [[graph theory]] were studied beginning in 1988 by [[Michael Fellows]] and [[Michael Langston]].<ref name=FellowsLangston1988>{{Cite journal \| doi = 10.1145/44483.44491\| title = Nonconstructive tools for proving polynomial-time decidability\| journal = Journal of the ACM\| volume = 35\| issue = 3\| pages = 727\| year = 1988\| last1 = Fellows \| first1 = M. R. \| last2 = Langston \| first2 = M. A. \| s2cid = 16587284}}</ref>

	A common question in graph theory is whether a certain input graph has a certain property. For example:		A common question in graph theory is whether a certain input graph has a certain property. For example:
Line 41:		Line 41:
	Sometimes the number of potential algorithms for a given problem is finite. We can count the number of possible algorithms and prove that only a bounded number of them are "bad", so at least one algorithm must be "good".		Sometimes the number of potential algorithms for a given problem is finite. We can count the number of possible algorithms and prove that only a bounded number of them are "bad", so at least one algorithm must be "good".

	As an example, consider the following problem.<ref name=GrebinskyKucherov2000>{{Cite journal \| doi = 10.1007/s004530010033\| title = Optimal Reconstruction of Graphs under the Additive Model\| journal = Algorithmica\| volume = 28\| pages = 104–124\| year = 2000\| last1 = Grebinski \| first1 = V.\| last2 = Kucherov \| first2 = G.}}</ref>		As an example, consider the following problem.<ref name=GrebinskyKucherov2000>{{Cite journal \| doi = 10.1007/s004530010033\| title = Optimal Reconstruction of Graphs under the Additive Model\| journal = Algorithmica\| volume = 28\| pages = 104–124\| year = 2000\| last1 = Grebinski \| first1 = V.\| last2 = Kucherov \| first2 = G.\| s2cid = 33176053\| url = https://hal.inria.fr/inria-00073517/file/RR-3171.pdf}}</ref>

	I select a vector ''v'' composed of ''n'' elements which are integers between 0 and a certain constant ''d''.		I select a vector ''v'' composed of ''n'' elements which are integers between 0 and a certain constant ''d''.
Line 61:		Line 61:
	== Additional examples ==		== Additional examples ==
	* Some computational problems can be shown to be decidable by using the [[Law of Excluded Middle#Use in computer science proofs\|Law of Excluded Middle]]. Such proofs are usually not very useful in practice, since the problems involved are quite artificial.		* Some computational problems can be shown to be decidable by using the [[Law of Excluded Middle#Use in computer science proofs\|Law of Excluded Middle]]. Such proofs are usually not very useful in practice, since the problems involved are quite artificial.
	* An example from [[Quantum complexity theory]] (related to [[Quantum query complexity]]) is given in.<ref>{{Cite journal \| doi = 10.4086/cjtcs.2013.004\| year = 2013\| last1 = Kimmel \| first1 = S.\| title = Quantum Adversary (Upper) Bound\| journal = Chicago Journal of Theoretical Computer Science\| volume = 19\| pages = 1–14\| arxiv = 1101.0797}}</ref>		* An example from [[Quantum complexity theory]] (related to [[Quantum query complexity]]) is given in.<ref>{{Cite journal \| doi = 10.4086/cjtcs.2013.004\| year = 2013\| last1 = Kimmel \| first1 = S.\| title = Quantum Adversary (Upper) Bound\| journal = Chicago Journal of Theoretical Computer Science\| volume = 19\| pages = 1–14\| arxiv = 1101.0797\| s2cid = 119264518}}</ref>

	== References ==		== References ==