New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:18, 15 February 2023 Kmett (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [296 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*log(h)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://www.schoolofhaskell.com/user/edwardk/online-lca")
- 11:18, 15 February 2023 Fischer, Heun (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m+n)$ == Space Complexity == $O(n)$ words (https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5439) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5439")
- 11:18, 15 February 2023 Schieber; Vishkin (Parallel) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m+log(n)$) == Space Complexity == $O(n)$ total (auxiliary?) words (https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217079?journalCode=smjcat")
- 11:18, 15 February 2023 Harel, Tarjan (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e46f9daf65174")
- 11:18, 15 February 2023 Harel, Tarjan (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) (hist | edit) [487 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e...")
- 11:18, 15 February 2023 Sleator and Tarjan (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(n)$) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 11:18, 15 February 2023 Sleator and Tarjan (Linking and Cutting) (Lowest Common Ancestor with Linking and Cutting Lowest Common Ancestor) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(n)$) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 11:18, 15 February 2023 Modified van Leeuwen (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(log(n)$)) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == (Unpublished report)")
- 11:18, 15 February 2023 Modified van Leeuwen (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(log(n)$)) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == (Unpublished report)")
- 11:18, 15 February 2023 Aho, Hopcroft, and Ullman (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m+n)$*log(log(n))) == Space Complexity == $O(n*log(log(n)$)) words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 11:18, 15 February 2023 Brent-Dekker Method (General Root Computation Root Computation) (hist | edit) [539 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2} along with function values f_i, f_{i-1}, f_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1973 ==...")
- 11:18, 15 February 2023 Aho, Hopcroft, and Ullman (Offline) (Off-Line Lowest Common Ancestor Lowest Common Ancestor) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 11:18, 15 February 2023 Aho, Hopcroft, and Ullman (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) (hist | edit) [354 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m+n)$*log(n)) == Space Complexity == $O(n*log(n)$) words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 11:18, 15 February 2023 Inverse quadratic interpolation (General Root Computation Root Computation) (hist | edit) [490 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2} along with function values f_i, f_{i-1}, f_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?)...")
- 11:18, 15 February 2023 Steffensen's method (General Root Computation Root Computation) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous estimate x_i; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?) == Reference ==")
- 11:18, 15 February 2023 Householder's Method (Root Computation with continuous derivatives (up to d) Root Computation) (hist | edit) [497 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(d*n_max)$? == Space Complexity == $O(d)$ words (Store current estimate x_i and the derivatives f' through f^{(d)} (assuming these take O(1) space each); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?...")
- 11:18, 15 February 2023 ITP Method (General Root Computation Root Computation) (hist | edit) [437 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_0+log((b-a)$/epsilon)) == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940? == Reference == -")
- 11:18, 15 February 2023 Anderson–Björck algorithm (General Root Computation Root Computation) (hist | edit) [470 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1973 == Reference == https://link.springer.com/article/10.1007/BF01951936")
- 11:18, 15 February 2023 Illinois Algorithm (General Root Computation Root Computation) (hist | edit) [470 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1971 == Reference == https://link.springer.com/article/10.1007/BF01934364")
- 11:18, 15 February 2023 Gabow, Galil, Spencer (general Maximum-weight matching) (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(log(log(n)$/log({2}+m/n))) + n^{2}*log(n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://ieeexplore.ieee.org/abstract/document/715935")
- 11:18, 15 February 2023 Galil, Micali, Gabow (general Maximum-weight matching) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www.proquest.com/docview/919855909?pq-origsite=gscholar&fromopenview=true")
- 11:18, 15 February 2023 Gabow (general Maximum-weight matching) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://www.proquest.com/docview/287948024?pq-origsite=gscholar&fromopenview=true")
- 11:18, 15 February 2023 Johnson (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(n)$/log({2}+m/n)) == Space Complexity == $O(n^{2})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www.sciencedirect.com/science/article/pii/0020019075900010")
- 11:18, 15 February 2023 Fredman-Tarjan (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn+n^{2}log(n)$) == Space Complexity == $O(n^{2})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/28869.28874")
- 11:18, 15 February 2023 Edmonds-Karp (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [581 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*(SP+))$ where $(SP+)$ denotes the time for one SSSP computation on a nonnegatively weighted graph. Initially $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Keeps track of current flow, which is of size O(n^2), and an O(n)-sized labeling function. SSSP computation has time bounded by O(n^2) and thus should use O(n^2) space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Co...")
- 11:18, 15 February 2023 Zaks' prefix reversal algorithm ( All permutations) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ on specific permutations == Space Complexity == $O(n)$ auxiliary (see NEXT algorithm in same paper) words (https://link.springer.com/content/pdf/10.1007/BF01937486.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://link.springer.com/article/10.1007/BF01937486")
- 11:18, 15 February 2023 Ives' algorithm c ( All permutations) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n) words needed to keep track of which elements have cycled how many times) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/abs/10.1145/359997.360002")
- 11:18, 15 February 2023 Ord-Smith ( All permutations) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n)-sized array q (as in paper) necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://dl.acm.org/doi/pdf/10.1145/362896.362913")
- 11:18, 15 February 2023 Langdon ( All permutations) (hist | edit) [391 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ per permutation == Space Complexity == $O({1})$ auxiliary words (Only need the auxiliary variable N, according to the flowchart in the paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://dl.acm.org/doi/pdf/10.1145/363282.363315")
- 11:18, 15 February 2023 Wells ( All permutations) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n)-sized array for t_k's necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1961 == Reference == https://www.jstor.org/stable/2004229#metadata_info_tab_contents")
- 11:18, 15 February 2023 Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*log(n)$) == Space Complexity == $O(log(n)$) auxiliary? words (Need to keep track of the specific indices where the minimums occur, up to depth log(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840359")
- 11:18, 15 February 2023 Micali, Vazirani (general graph Maximum cardinality matching) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{0.5} E)$ == Space Complexity == $O(E)$ auxiliary? words (Manipulates a constant number of graphs? Contractions can be kept track of in O(E) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/4567800")
- 11:18, 15 February 2023 Blossom Algorithm (general graph Maximum cardinality matching) (hist | edit) [498 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}E)$ == Space Complexity == $O(E)$ auxiliary? words (Manipulates a constant number of graphs? Contractions can be kept track of in O(E) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1961 == Reference == https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/paths-trees-and-flowers/08B492B72...")
- 11:18, 15 February 2023 Alt, Blum, Mehlhorn, Paul (bipartite graph Maximum cardinality matching) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{1.5}*(E/logV)$^{0.5}) == Space Complexity == $O(E)$ auxiliary? words (Uses constant number of O(E)-sized data structures in pseudocode of algorithm) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1991 == Reference == https://www.sciencedirect.com/science/article/pii/002001909190195N")
- 11:18, 15 February 2023 Masek, Paterson (Edit sequence, constant-size alphabet Sequence Alignment) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn/log(n)$) == Space Complexity == $O(mn/log(n)$) words (https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub")
- 11:18, 15 February 2023 Wagner-Fischer algorithm (Edit sequence, constant-size alphabet Sequence Alignment) (hist | edit) [334 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (https://dl.acm.org/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/doi/abs/10.1145/321796.321811")
- 11:18, 15 February 2023 Wagner-Fischer algorithm (Edit distance, constant-size alphabet Sequence Alignment) (hist | edit) [303 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/doi/abs/10.1145/321796.321811")
- 11:18, 15 February 2023 Wu and Manber, Fuzzy String Matching ( String Search) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk \lceil m/w \rceil)$ == Space Complexity == $O(ms + k \lceil m/w \rceil)$ (https://dl.acm.org/doi/pdf/10.1145/135239.135244) == Description == == Approximate? == Approximate Approximation Factor: Levensthein Distance = k == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 1992 == Reference == https://dl.acm.org/doi/pdf/10.1145/135239.135244")
- 11:18, 15 February 2023 Focused D* ( Informed Search) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.8257")
- 11:18, 15 February 2023 D* Lite ( Informed Search) (hist | edit) [308 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://doi.org/10.1109%2Ftro.2004.838026")
- 11:18, 15 February 2023 Anytime Dynamic A* (ADA*) ( Informed Search) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://www.ri.cmu.edu/publications/anytime-dynamic-a-an-anytime-replanning-algorithm/")
- 11:18, 15 February 2023 Shi 2009 (NAE 3SAT Boolean Satisfiability) (hist | edit) [480 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({12}m*t_extract + {2}m*t_discard + {2}n*t_append + (n+{2}m)$*t_merge + (n-{1})*t_amplify) == Space Complexity == $O(n)$ tubes or $O({2}^n)$ library strands (https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5211463) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Adelman-Lipton == Year == 2009 == Reference == https://ieeexplore.ieee.org/abstract/document/52...")
- 11:18, 15 February 2023 Hertli (Modified PPSZ) (4SAT Boolean Satisfiability) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.46899}^n)$ == Space Complexity == $O(kn)$ words (Not sure, please look) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2014 == Reference == https://epubs.siam.org/doi/abs/10.1137/120868177")
- 11:18, 15 February 2023 Hertli (Modified PPSZ) (3SAT Boolean Satisfiability) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.30704}^n)$ == Space Complexity == $O(kn)$ words (Not sure, please look) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2014 == Reference == https://epubs.siam.org/doi/abs/10.1137/120868177")
- 11:18, 15 February 2023 Paturi, Pudlák, Saks, Zane (PPSZ) 2005 (k-SAT Boolean Satisfiability) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == O^*({2}^{n-cn/k}) == Space Complexity == $O(kn)$ words (Derived in notes) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2005 == Reference == https://dl.acm.org/doi/abs/10.1145/1066100.1066101")
- 11:18, 15 February 2023 Lewis 1978 (Renamable Horn Boolean Satisfiability) (hist | edit) [270 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1978 == Reference == https://dl.acm.org/doi/10.1145/322047.322059")
- 11:18, 15 February 2023 Quantum Adiabatic Algorithm (QAA) (CNF-SAT Boolean Satisfiability) (hist | edit) [310 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(poly(n)$) qubits () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Quantum == Year == 2001 == Reference == https://arxiv.org/pdf/quant-ph/0001106.pdf")
- 11:17, 15 February 2023 WalkSAT (CNF-SAT Boolean Satisfiability) (hist | edit) [316 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*mt*mf)$ == Space Complexity == $O(n)$ (same as above) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1994 == Reference == https://www.aaai.org/Papers/AAAI/1994/AAAI94-051.pdf")
- 11:17, 15 February 2023 GSAT (CNF-SAT Boolean Satisfiability) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*mt*mf)$ == Space Complexity == $O(n)$ (derived in notes) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1992 == Reference == http://www.cs.cornell.edu/selman/papers/pdf/92.aaai.gsat.pdf")
- 11:17, 15 February 2023 Conflict-Driven Clause Learning (CDCL) (CNF-SAT Boolean Satisfiability) (hist | edit) [268 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/document/769433")