%PDF-1.5
%
10 0 obj
<< /S /GoTo /D (Outline0.1) >>
endobj
13 0 obj
(SAT and k-SAT)
endobj
14 0 obj
<< /S /GoTo /D (Outline0.2) >>
endobj
17 0 obj
(Subexponential time algorithms)
endobj
18 0 obj
<< /S /GoTo /D (Outline0.3) >>
endobj
21 0 obj
(ETH and SETH)
endobj
22 0 obj
<< /S /GoTo /D (Outline0.4) >>
endobj
25 0 obj
(Algorithmic lower bounds based on ETH)
endobj
26 0 obj
<< /S /GoTo /D (Outline0.5) >>
endobj
29 0 obj
(Algorithmic lower bounds based on SETH)
endobj
30 0 obj
<< /S /GoTo /D (Outline0.6) >>
endobj
33 0 obj
(Further Reading)
endobj
34 0 obj
<< /S /GoTo /D [35 0 R /Fit] >>
endobj
37 0 obj
<<
/Type /XObject
/Subtype /Form
/BBox [0 0 5669.291 8]
/FormType 1
/Matrix [1 0 0 1 0 0]
/Resources 38 0 R
/Length 15
/Filter /FlateDecode
>>
stream
xP(
endstream
endobj
38 0 obj
<<
/Shading << /Sh << /ShadingType 2 /ColorSpace /DeviceRGB /Domain [0.0 8.00009] /Coords [0 0.0 0 8.00009] /Function << /FunctionType 3 /Domain [0.0 8.00009] /Functions [ << /FunctionType 2 /Domain [0.0 8.00009] /C0 [1 1 1] /C1 [0.5 0.5 0.5] /N 1 >> << /FunctionType 2 /Domain [0.0 8.00009] /C0 [0.5 0.5 0.5] /C1 [0.5 0.5 0.5] /N 1 >> ] /Bounds [ 4.00005] /Encode [0 1 0 1] >> /Extend [false false] >> >>
/ProcSet [ /PDF ]
>>
endobj
39 0 obj
<<
/Type /XObject
/Subtype /Form
/BBox [0 0 8 8]
/FormType 1
/Matrix [1 0 0 1 0 0]
/Resources 40 0 R
/Length 15
/Filter /FlateDecode
>>
stream
xP(
endstream
endobj
40 0 obj
<<
/Shading << /Sh << /ShadingType 3 /ColorSpace /DeviceRGB /Domain [0 1] /Coords [4.00005 4.00005 0.0 4.00005 4.00005 4.00005] /Function << /FunctionType 2 /Domain [0 1] /C0 [0.5 0.5 0.5] /C1 [1 1 1] /N 1 >> /Extend [true false] >> >>
/ProcSet [ /PDF ]
>>
endobj
41 0 obj
<<
/Type /XObject
/Subtype /Form
/BBox [0 0 16 16]
/FormType 1
/Matrix [1 0 0 1 0 0]
/Resources 42 0 R
/Length 15
/Filter /FlateDecode
>>
stream
xP(
endstream
endobj
42 0 obj
<<
/Shading << /Sh << /ShadingType 3 /ColorSpace /DeviceRGB /Domain [0.0 8.00009] /Coords [8.00009 8.00009 0.0 8.00009 8.00009 8.00009] /Function << /FunctionType 3 /Domain [0.0 8.00009] /Functions [ << /FunctionType 2 /Domain [0.0 8.00009] /C0 [0.5 0.5 0.5] /C1 [0.5 0.5 0.5] /N 1 >> << /FunctionType 2 /Domain [0.0 8.00009] /C0 [0.5 0.5 0.5] /C1 [1 1 1] /N 1 >> ] /Bounds [ 4.00005] /Encode [0 1 0 1] >> /Extend [true false] >> >>
/ProcSet [ /PDF ]
>>
endobj
45 0 obj
<<
/Length 1132
/Filter /FlateDecode
>>
stream
xWKs"7+8T[-Q]R{0,6u~}Z۩fZ_?)a%zpd8>9B72aYmjO#
,'~6[ҏp&y7|8 85x{ \3=*G"0Z_ UnSDŽ*P6B!uXf[3HV;l!b+Qb![nJL,,h)xa!;غ
*B 1یXQh!BR%pf/"zƀJS뱱}lrU;IJh0JIN'_œ4v!%Kt"Te4H˩k-yYU}2'YvJ'NkžWZ-Y֩Վ@YT:eހvU*U-媼KU䪘^AǪ-Hڟϕ(ds
2Fw:iy;t'
aPCi0I-XApO
|)l)TqO)zVw}"m4I??z5]DIjORF%c0}OHCS+f^Noj.Wu|1\Wbu>Ϊp2j
Ļ#D1V[O%F oh F*K%VL'r~/İgk/
] 462g ~W"ńcz9ׅ=r,6b7<.yW,|*~z߆i=%.'f^?+ԏVG8nI`,S&K1ӕϛ6X.Eպ,!=rAj>i`xpƚDի#f,x̳)p&]b3u=uZQ`ܷ,26_Cs=c/\u,~HSB2,1-,US<ZUĦI7D[3̞Q&L]h}uc1NLNNBrN{v6]Z}S>4SƝF,B!.;Kr|"D
endstream
endobj
35 0 obj
<<
/Type /Page
/Contents 45 0 R
/Resources 44 0 R
/MediaBox [0 0 362.835 272.126]
/Trans << /S /R >>
/Parent 54 0 R
/Annots [ 43 0 R ]
>>
endobj
43 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [147.961 0.249 214.868 6.669]
/A << /S /GoTo /D (Navigation32) >>
>>
endobj
46 0 obj
<<
/D [35 0 R /XYZ 8.963 273.126 null]
>>
endobj
47 0 obj
<<
/D [35 0 R /XYZ 8.963 273.126 null]
>>
endobj
48 0 obj
<<
/D [35 0 R /XYZ 9.963 272.126 null]
>>
endobj
44 0 obj
<<
/ColorSpace 3 0 R /Pattern 2 0 R /ExtGState 1 0 R
/Font << /F17 49 0 R /F15 50 0 R /F7 51 0 R /F6 52 0 R /F26 53 0 R >>
/XObject << /Fm2 39 0 R /Fm3 41 0 R /Fm1 37 0 R >>
/ProcSet [ /PDF /Text ]
>>
endobj
56 0 obj
<<
/Type /XObject
/Subtype /Form
/BBox [0 0 11.512 11.512]
/FormType 1
/Matrix [1 0 0 1 0 0]
/Resources 57 0 R
/Length 15
/Filter /FlateDecode
>>
stream
xP(
endstream
endobj
57 0 obj
<<
/Shading << /Sh << /ShadingType 3 /ColorSpace /DeviceRGB /Domain [0.0 5.75627] /Coords [3.54233 8.41302 0.0 5.75627 5.75627 5.75627] /Function << /FunctionType 3 /Domain [0.0 5.75627] /Functions [ << /FunctionType 2 /Domain [0.0 5.75627] /C0 [0.72 0.72 0.895] /C1 [0.4 0.4 0.775] /N 1 >> << /FunctionType 2 /Domain [0.0 5.75627] /C0 [0.4 0.4 0.775] /C1 [0.226 0.226 0.541] /N 1 >> << /FunctionType 2 /Domain [0.0 5.75627] /C0 [0.226 0.226 0.541] /C1 [0.18999 0.18999 0.415] /N 1 >> << /FunctionType 2 /Domain [0.0 5.75627] /C0 [0.18999 0.18999 0.415] /C1 [1 1 1] /N 1 >> ] /Bounds [ 1.94826 3.89655 5.31345] /Encode [0 1 0 1 0 1 0 1] >> /Extend [true false] >> >>
/ProcSet [ /PDF ]
>>
endobj
67 0 obj
<<
/Length 976
/Filter /FlateDecode
>>
stream
xIo@st$<}9E@M8 иiDyKR;
Z)w͛|~ACD j)9ÆK4Ô)Τ'h1DK]ʠx1&(c>[=jBweB`)
leKe6ۘiNN/FT`.C;d$10QKqY[NեcU1Χ #`¤ %R%ϮfT\-wkϫ;nD HN`3
:! qׅ֠4y]]b#9؎1,IuNKIPo@P ˍ#$
md<"RT'A`LQy
1P$Er_W?'PPibDOn>CK1fNjd2̪vuZBLbI*V
7Y(mVYݒI/ W>
/Parent 54 0 R
/Annots [ 58 0 R 59 0 R 60 0 R 61 0 R 62 0 R 63 0 R 64 0 R ]
>>
endobj
58 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 199.95 89.304 209.469]
/A << /S /GoTo /D (Navigation3) >>
>>
endobj
59 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 168.983 154.615 180.441]
/A << /S /GoTo /D (Navigation9) >>
>>
endobj
60 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 141.892 89.968 151.412]
/A << /S /GoTo /D (Navigation12) >>
>>
endobj
61 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 110.926 192.058 122.383]
/A << /S /GoTo /D (Navigation14) >>
>>
endobj
62 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 81.897 197.593 93.354]
/A << /S /GoTo /D (Navigation25) >>
>>
endobj
63 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 52.868 90.287 64.325]
/A << /S /GoTo /D (Navigation31) >>
>>
endobj
64 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [147.961 0.249 214.868 6.669]
/A << /S /GoTo /D (Navigation1) >>
>>
endobj
68 0 obj
<<
/D [66 0 R /XYZ 8.963 273.126 null]
>>
endobj
69 0 obj
<<
/D [66 0 R /XYZ 8.963 273.126 null]
>>
endobj
65 0 obj
<<
/ColorSpace 3 0 R /Pattern 2 0 R /ExtGState 1 0 R
/Font << /F17 49 0 R /F26 53 0 R /F15 50 0 R >>
/XObject << /Fm4 56 0 R >>
/ProcSet [ /PDF /Text ]
>>
endobj
77 0 obj
<<
/Type /XObject
/Subtype /Form
/BBox [0 0 11.512 11.512]
/FormType 1
/Matrix [1 0 0 1 0 0]
/Resources 78 0 R
/Length 15
/Filter /FlateDecode
>>
stream
xP(
endstream
endobj
78 0 obj
<<
/Shading << /Sh << /ShadingType 3 /ColorSpace /DeviceRGB /Domain [0.0 5.75627] /Coords [3.54233 8.41302 0.0 5.75627 5.75627 5.75627] /Function << /FunctionType 3 /Domain [0.0 5.75627] /Functions [ << /FunctionType 2 /Domain [0.0 5.75627] /C0 [0.944 0.944 0.979] /C1 [0.88 0.88 0.955] /N 1 >> << /FunctionType 2 /Domain [0.0 5.75627] /C0 [0.88 0.88 0.955] /C1 [0.8452 0.8452 0.9082] /N 1 >> << /FunctionType 2 /Domain [0.0 5.75627] /C0 [0.8452 0.8452 0.9082] /C1 [0.838 0.838 0.883] /N 1 >> << /FunctionType 2 /Domain [0.0 5.75627] /C0 [0.838 0.838 0.883] /C1 [1 1 1] /N 1 >> ] /Bounds [ 1.94826 3.89655 5.31345] /Encode [0 1 0 1 0 1 0 1] >> /Extend [true false] >> >>
/ProcSet [ /PDF ]
>>
endobj
87 0 obj
<<
/Length 1018
/Filter /FlateDecode
>>
stream
xKo7<.qLQA-,APK%i}}JzYp
Ā59g>.auj5[ZP+#(,rq1
,H[i-U[
kV)exEϨŇЗB)
`U
UATWT?N.}pE҂L (@&wחlQ>M~sQ}aTqiIڀ_S!c 0x;'Dh;2JsPꤟ=p|Jpe P&V:,bG5i8N߈ޟ+V:SrjATXǔ:X$Zn9Rx0l@Le$R& o".և=91c2Uh,Z)PHS:Zy~de6Rle{X~yZERTht-("3lQ{>eIJtRq}SFAJW;,&mEG2i/px)7/GYߡ~ZxVrél^$^F8`9[og%Yaꌾy=H6$3$
dɶv\d6V&Uٍozc09:>ŞL$BN(*xS%K;}3Mn#/e6f᧗*5LWEsrhz{i~~^
9B멎XًUx{}:ƿ<2hD9F (Sr^ei}ľ,_"*ӻ (7 Vwu-icH]K]cG;'kvP:ΕYP.'ĻpX]MWxƒS%Fl'/7c;SfOM}F.f;|oz+ԘT/bᏦk< ij)zI7jN,mN(eVt>eI|g}żXCCψRA).uCv\9wd
endstream
endobj
86 0 obj
<<
/Type /Page
/Contents 87 0 R
/Resources 85 0 R
/MediaBox [0 0 362.835 272.126]
/Trans << /S /R >>
/Parent 54 0 R
/Annots [ 76 0 R 79 0 R 80 0 R 81 0 R 82 0 R 83 0 R 84 0 R ]
>>
endobj
76 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 199.95 89.304 209.469]
/A << /S /GoTo /D (Navigation3) >>
>>
endobj
79 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 168.983 154.615 180.441]
/A << /S /GoTo /D (Navigation9) >>
>>
endobj
80 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 141.892 89.968 151.412]
/A << /S /GoTo /D (Navigation12) >>
>>
endobj
81 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 110.926 192.058 122.383]
/A << /S /GoTo /D (Navigation14) >>
>>
endobj
82 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 81.897 197.593 93.354]
/A << /S /GoTo /D (Navigation25) >>
>>
endobj
83 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [21.143 52.868 90.287 64.325]
/A << /S /GoTo /D (Navigation31) >>
>>
endobj
84 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [147.961 0.249 214.868 6.669]
/A << /S /GoTo /D (Navigation1) >>
>>
endobj
70 0 obj
<<
/D [86 0 R /XYZ 8.963 273.126 null]
>>
endobj
88 0 obj
<<
/D [86 0 R /XYZ 8.963 273.126 null]
>>
endobj
11 0 obj
<<
/D [86 0 R /XYZ 9.963 272.126 null]
>>
endobj
85 0 obj
<<
/ColorSpace 3 0 R /Pattern 2 0 R /ExtGState 1 0 R
/Font << /F17 49 0 R /F26 53 0 R /F15 50 0 R >>
/XObject << /Fm4 56 0 R /Fm5 77 0 R >>
/ProcSet [ /PDF /Text ]
>>
endobj
92 0 obj
<<
/Length 1298
/Filter /FlateDecode
>>
stream
xZ[o6~ϯ
I(nPS%Qk˩eߡHR|P4"*"yxs$[DyRh) A\1lDL3LBmMڸ_&%4-U.x'hNR+KiѮbl+ŕ*/3,@L2LD*|3,
^w4j6 r.Oh~f9Xi(ɸu_#9B[,hh0 *BA`*(bYl D% PG9BBhM˞Țx֨O2HϦ'>gG/"1M>8ih4-oY<#olo
i*.t>Zu`7)Ri88ˮ[=BM$4
+%uSle?ܔi299$RcfdiX:>3ka|?uhP0ZroZ{!?Il9aDTM!@_'B6=4~=bzWldo P&J5Vy83AiK%4gq2zW`M\q8ld0dWuUr'PrC/=S[4faHx'v5Q$p[\pZEQoq' ؔҴ1w3 `
B !m9O>T^1`]sV9VH0&84b@ 2(?Cf&4Cai|?3gF0B7E-r4ۊFuorwiӇxt?LbI+Kg fPυrѪxix+Xؐi]ae7g[=
Sj
>P&)LLUdYTTXVO W[{{]&wr@mb]aFȉFَ~cMX/\nʟ$\weu_jqI-bGݵ_p֟\?hrxlqŶ
S0\G@#C4ytn陌Ĭ 9*Q/1(y% "|sWݔ#qSqD|tuT1 I%vZ~-T`;̳8K2w7(-(H-<AvK7cbcZ/Y5%#x1-^"jHh@8tGhY{
endstream
endobj
91 0 obj
<<
/Type /Page
/Contents 92 0 R
/Resources 90 0 R
/MediaBox [0 0 362.835 272.126]
/Trans << /S /R >>
/Parent 54 0 R
/Annots [ 89 0 R ]
>>
endobj
89 0 obj
<<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/N/C[.5 .5 .5]
/Rect [147.961 0.249 214.868 6.669]
/A << /S /GoTo /D (Navigation1) >>
>>
endobj
93 0 obj
<<
/D [91 0 R /XYZ 8.963 273.126 null]
>>
endobj
94 0 obj
<<
/D [91 0 R /XYZ 8.963 273.126 null]
>>
endobj
90 0 obj
<<
/ColorSpace 3 0 R /Pattern 2 0 R /ExtGState 1 0 R
/Font << /F17 49 0 R /F27 95 0 R /F15 50 0 R /F11 96 0 R /F8 97 0 R /F14 98 0 R /F28 99 0 R /F7 51 0 R /F26 53 0 R >>
/ProcSet [ /PDF /Text ]
>>
endobj
100 0 obj
<<
/Type /XObject
/Subtype /Form
/BBox [0 0 4.693 4.693]
/FormType 1
/Matrix [1 0 0 1 0 0]
/Resources 101 0 R
/Length 15
/Filter /FlateDecode
>>
stream
xP(
endstream
endobj
101 0 obj
<<
/Shading << /Sh << /ShadingType 3 /ColorSpace /DeviceRGB /Domain [0.0 2.34677] /Coords [1.5279 3.3476 0.0 2.34677 2.34677 2.34677] /Function << /FunctionType 3 /Domain [0.0 2.34677] /Functions [ << /FunctionType 2 /Domain [0.0 2.34677] /C0 [0.88 0.88 0.955] /C1 [0.4 0.4 0.775] /N 1 >> << /FunctionType 2 /Domain [0.0 2.34677] /C0 [0.4 0.4 0.775] /C1 [0.14 0.14 0.49] /N 1 >> << /FunctionType 2 /Domain [0.0 2.34677] /C0 [0.14 0.14 0.49] /C1 [0.09999 0.09999 0.34999] /N 1 >> << /FunctionType 2 /Domain [0.0 2.34677] /C0 [0.09999 0.09999 0.34999] /C1 [1 1 1] /N 1 >> ] /Bounds [ 0.72784 1.45572 2.00165] /Encode [0 1 0 1 0 1 0 1] >> /Extend [true false] >> >>
/ProcSet [ /PDF ]
>>
endobj
105 0 obj
<<
/Length 1607
/Filter /FlateDecode
>>
stream
xYmo6_21|'U+uغ!QZr(RoXIXD{xGtzqlF
xBW.S*A~Z4y.QJjm a