Content deleted Content added
→Cryptographic breaks: Rephrase and link relevant articles |
Jasper Deng (talk | contribs) →Sub-graphs: clarify a bit Tags: Mobile edit Mobile web edit Advanced mobile edit |
||
Line 28:
=== Sub-graphs ===
The problem of [[decision problem|deciding]] whether a graph <math>G</math> contains <math>H</math> as a [[graph minor|minor]] is [[NP-complete]] in general, but where <math>H</math> is fixed, it can be solved in polynomial time. The running time for testing whether <math>H</math> is a minor of <math>G</math> in this case is <math>O(n^2)</math>,<ref name="kkr12">{{cite journal |last1=Kawarabayashi | first1=Ken-ichi |last2=Kobayashi | first2=Yusuke |last3=Reed | first3=Bruce | authorlink3=Bruce Reed (mathematician) |year=2012 |title=The disjoint paths problem in quadratic time |journal=[[Journal of Combinatorial Theory]] | series=Series B |volume=102 |issue=2 |pages=424–435|doi=10.1016/j.jctb.2011.07.004 |doi-access=free }}</ref> where <math>n</math> is the number of vertices in <math>G</math> and the [[big O notation]] hides a constant that depends superexponentially on <math>H</math>. The constant is greater than <math>2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math> in [[Knuth's up-arrow notation]], where <math>h</math> is the number of vertices in <math>H</math>.<ref>{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of Algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |citeseerx=10.1.1.114.3864 |doi=10.1016/0196-6774(87)90043-5 }}</ref> Even the case of <math>h = 4</math> cannot be reasonably computed as the constant is greater than 2 [[tetrated]] by 65536, that is, <math>{^{65536}2 = \ \atop {\ }} {{\underbrace{2^{2^{\cdot^{\cdot^{2}}}}}} \atop 65536}</math>.
=== Cryptographic breaks ===
| |||