Editing Ramsey's theorem (section)

=== Computational complexity ===
{{blockquote|text=[[Paul Erdős|Erdős]] asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of {{math|''R''(5, 5)}} or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for {{math|''R''(6, 6)}}. In that case, he believes, we should attempt to destroy the aliens.<ref>{{citation|title=Ten Lectures on the Probabilistic Method|page=[https://archive.org/details/tenlecturesonpro0000spen/page/4 4]|author=Joel H. Spencer|author-link=Joel H. Spencer|year=1994|publisher=[[Society for Industrial and Applied Mathematics|SIAM]]|isbn=978-0-89871-325-1|url=https://archive.org/details/tenlecturesonpro0000spen/page/4}}</ref>|author=[[Joel Spencer]]}}

A sophisticated computer program does not need to look at all colourings individually in order to eliminate all of them; nevertheless it is a very difficult computational task that existing software can only manage on small sizes. Each complete graph {{mvar|K{{sub|n}}}} has {{math|{{sfrac|1|2}}''n''(''n'' − 1)}} edges, so there would be a total of {{math|''c''{{sup|''n''(''n'' − 1)/2}}}} graphs to search through (for {{math|''c''}} colours) if brute force is used.<ref>[http://www.learner.org/channel/courses/mathilluminated/units/2/textbook/06.php 2.6 Ramsey Theory from Mathematics Illuminated]</ref> Therefore, the complexity for searching all possible graphs (via [[brute-force search|brute force]]) is {{math|''O''(''c''{{sup|''n''{{sup|2}}}})}} for {{mvar|c}} colourings and at most {{mvar|n}} nodes.

The situation is unlikely to improve with the advent of [[quantum computer]]s.  One of the best-known searching algorithms for unstructured datasets exhibits only a quadratic speedup (cf. [[Grover's algorithm]]) relative to classical computers, so that the [[Time complexity|computation time]] is still [[Exponential growth|exponential]] in the number of nodes.<ref>{{Cite journal |last=Montanaro |first=Ashley |date=2016 |title=Quantum algorithms: an overview |url=https://www.nature.com/articles/npjqi201523 |journal=[[npj Quantum Information]] |volume=2 |issue=1 |page=15023 |doi=10.1038/npjqi.2015.23 |arxiv=1511.04206 |bibcode=2016npjQI...215023M |s2cid=2992738 |via=Nature}}</ref><ref>{{Cite journal|last1=Wang|first1=Hefeng|year=2016|title=Determining Ramsey numbers on a quantum computer|journal=Physical Review A|volume=93|issue=3|pages=032301|arxiv=1510.01884|bibcode=2016PhRvA..93c2301W|doi=10.1103/PhysRevA.93.032301|s2cid=118724989}}</ref>