Content deleted Content added
LouScheffer (talk | contribs) →Connectivity in undirected graphs: Wording |
m lc common adjective Tags: Visual edit Mobile edit Mobile web edit Advanced mobile edit |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 4:
== Possible use cases ==
Even if they are never used in practice, galactic algorithms may still contribute to [[computer science]]:
* An algorithm, even if impractical, may show new techniques that may eventually be used to create practical algorithms.
* Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical.
* An impractical algorithm can still demonstrate that [[conjecture]]d bounds can be achieved, or that proposed bounds are wrong, and hence advance the theory of algorithms (see, for example, Reingold's algorithm for [[connectivity (graph theory)|connectivity]] in undirected graphs). As Lipton states:<ref name="seminal"/>{{quote |This alone could be important and often is a great reason for finding such algorithms. For example, if tomorrow there were a discovery that showed there is a factoring algorithm with a huge but provably polynomial time bound, that would change our beliefs about factoring. The algorithm might never be used, but would certainly shape the future research into factoring.}} Similarly, a hypothetical algorithm for the [[Boolean satisfiability problem]] with a large but polynomial time bound, such as <math>\Theta\bigl(n^{2^{100}}\bigr)</math>, although unusable in practice, would settle the [[P versus NP problem]], considered the most important open problem in computer science and one of the [[Millennium Prize Problems]].<ref>{{cite journal |author=Fortnow, L. |year=2009 |title=The status of the P versus NP problem |journal=Communications of the ACM |volume=52 |issue=9 |pages=78–86 |url=https://www.cs.cmu.edu/~15326-f23/CACM-Fortnow.pdf|doi=10.1145/1562164.1562186 |s2cid=5969255 }}</ref><ref>{{cite journal |author=Fortnow |first=Lance |year=2022 |title=Fifty Years of P Versus NP and the Possibility of the Impossible |url=https://dl.acm.org/doi/pdf/10.1145/3460351 |journal=Communications of the ACM |volume=65 |issue=1 |pages=76–85 |doi=10.1145/3460351 }}</ref>
Line 82:
=== Low-density parity-check codes ===
'''[[Low-density parity-check code]]s''', also known as '''LDPC''' or '''Gallager''' codes, are an example of an algorithm that was galactic when first developed, but became practical as computation improved. They were originally conceived by [[Robert G. Gallager]] in his doctoral dissertation<ref>{{cite thesis |last=Gallager |first=Robert G. |date= 1960 |title=Low density parity check codes |url=https://dspace.mit.edu/bitstream/handle/1721.1/11804/32786367-MIT.pdf |degree=Ph.D |publisher=Massachusetts Institute of Technology }}</ref> at the [[Massachusetts Institute of Technology]] in 1960.<ref>{{Cite news |last=Hardesty |first=L. |date=January 21, 2010 |title=Explained: Gallager codes |url=http://web.mit.edu/newsoffice/2010/gallager-codes-0121.html |access-date=August 7, 2013 |journal=MIT News}}</ref><ref name="G1962">{{cite journal |last=Gallager |first=R.G. |date=January 1962 |title=Low density parity check codes |journal=IRE Trans. Inf. Theory |volume=8 |issue=1 |pages=21–28 |doi=10.1109/TIT.1962.1057683 |s2cid=260490814 |hdl=1721.1/11804/32786367-MIT}}</ref> Although their performance was much better than other codes of that time, reaching the [[Gilbert–Varshamov bound for linear codes]], the codes were largely ignored as their iterative decoding algorithm was prohibitively computationally expensive for the hardware available.<ref>{{cite journal |title=The development of turbo and LDPC codes for deep-space applications |last1=Andrews |first1=Kenneth S |last2=Divsalar |first2=Dariush |last3=Dolinar |first3=Sam |last4=Hamkins |first4=Jon |last5=Jones |first5=Christopher R |last6=Pollara |first6=Fabrizio |journal=Proceedings of the IEEE |volume=95 |number=11 |pages=2142–2156 |year=2007 |publisher=IEEE |doi=10.1109/JPROC.2007.905132 |url=http://coding.jpl.nasa.gov/~hamkins/publications/journals/2007_11_turbo_LDPC.pdf |archive-date=2009-06-20 |access-date=2025-03-04 |archive-url=https://web.archive.org/web/20090620174506/http://coding.jpl.nasa.gov/~hamkins/publications/journals/2007_11_turbo_LDPC.pdf |url-status=bot: unknown }}</ref>
Renewed interest in LDPC codes emerged following the invention of the closely related [[turbo code]]s (1993), whose similarly iterative decoding algorithm outperformed other codes used at that time. LDPC codes were subsequently rediscovered in 1996
|title=Near Shannon limit performance of low density parity check codes
|last1=MacKay |first1=David JC |author1-link=David J. C. MacKay|last2=Neal |first2=Radford M |author2-link=Radford M. Neal
Line 103 ⟶ 93:
|year=1996
|publisher=IET
|doi=10.1049/el:19961141 |bibcode=1996ElL....32.1645M |url=https://docs.switzernet.com/people/emin-gabrielyan/060708-thesis-ref/papers/MacKay96.pdf}}</ref> and
== References ==
| |||