Content deleted Content added
Citation bot (talk | contribs) Alter: title. | You can use this bot yourself. Report bugs here. | Activated by Amigao | Category:Mathematical notation | via #UCB_Category |
m →Examples: Grammar correction (removed ungrammatical "and") |
||
Line 19:
| year = 2012}}.</ref>
*[[Claude Shannon]] showed a simple but impractical code that could reach the capacity of a channel. It requires assigning a random code word to every possible N bit message, then decoding by finding the closest code word. If N is chosen large enough, this beats any existing code and can get arbitrarily close to the capacity of the channel. Unfortunately, any N big enough to beat existing codes is also completely impractical.<ref>{{cite web |url=https://news.mit.edu/2010/explained-shannon-0115 |title=Explained: The Shannon limit |publisher=MIT News Office |author=Larry Hardesty |date=Jan 19, 2010}}</ref> These codes, though never used, inspired decades of research into more practical algorithms that today can achieve rates arbitrarily close to channel capacity.<ref>{{cite web |url=https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-451-principles-of-digital-communication-ii-spring-2005/video-lectures/chap13.pdf |title=Capacity-Approaching Codes}}</ref>
*The problem of [[decision problem|deciding]] whether a graph ''G'' contains ''H'' as a [[graph minor|minor]] is NP-complete in general, but where ''H'' is fixed, it can be solved in polynomial time. The running time for testing whether ''H'' is a minor of ''G'' in this case is ''O''(''n''<sup>2</sup>),<ref name="kkr12">{{cite journal |author=Kawarabayashi, K. I., Kobayashi, Y., & Reed, B. |year=2012 |title=The disjoint paths problem in quadratic time |journal=Journal of Combinatorial Theory, Series B |volume=102 |issue=2 |pages=424–435|doi=10.1016/j.jctb.2011.07.004 |doi-access=free }}</ref> where ''n'' is the number of vertices in ''G'' and the [[big O notation]] hides a constant that depends superexponentially on ''H''. The constant is greater than <math> c > 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math> (using [[Knuth's up-arrow notation]]),
*For cryptographers, a cryptographic "break" is anything faster than a brute-force attack – i.e., performing one trial decryption for each possible key in sequence. In many cases, even though they are the best known methods, they are still infeasible with current technology. One example is the best attack known against 128 bit [[Advanced Encryption Standard|AES]], which takes only 2<sup>126</sup> operations.<ref name=":0">{{cite book |author=Biaoshuai Tao |title = Information Security and Privacy|volume = 9144|pages = 39–56|author2=Hongjun Wu |last-author-amp=yes |date=2015|doi=10.1007/978-3-319-19962-7_3 |series = Lecture Notes in Computer Science|isbn = 978-3-319-19961-0}}</ref> Despite being impractical, theoretical breaks can sometimes provide insight into vulnerability patterns.
*There exists a single algorithm known as "Hutter search" that can solve any well-defined problem in an asymptotically optimal time, barring some caveats. However, its hidden constants in the running time are so large it would never be practical for anything.<ref>{{cite arxiv|last=Hutter|first=Marcus|date=2002-06-14|title=The Fastest and Shortest Algorithm for All Well-Defined Problems|eprint=cs/0206022}}</ref><ref>{{Cite journal|last=Gagliolo|first=Matteo|date=2007-11-20|title=Universal search|journal=Scholarpedia|language=en|volume=2|issue=11|pages=2575|doi=10.4249/scholarpedia.2575|issn=1941-6016|bibcode=2007SchpJ...2.2575G|doi-access=free}}</ref>
| |||