8¡§¦'C¡edgf¢DHCI PQ¡§%GD¤rts

§

‰yCÉE

‡

ˆ

‡de



Ô£7e

Èكfqˆqu

ñ

ewc

ˆ‰y

b

ÐfrWyӀˆqy

ew…w‡de

ªˆ

pt‡‘i

‰y

i

u

b

ˆ

Ï

yCИƒ

ew…–Ñ

ƒ

ewcf…t‡

v

Ês‡

yCÉ

ie‡‘i×

ƒ

i‰iq‡¬Ïtb

yƒ

etb

Ð

‡¬eØcªÊ

y‚qÐ

b¬‡dÑ«‡

ˆ‰y

…

É

c

Ð

Ô

¢

y‚v

c’bdb

ˆ

p

yŸyCÓ

c’Ñ«×tb

yu

i

y

…¥‡de

ˆ

p

y

×

‰ƒ€ƒ’È©ƒ’È

Å

p

yCƒf‰y

Ñ

fÔ²å

ˆ

iqp

ƒ•É

i

ˆ

pwc

ˆ

y

Ê

y

e–Ê

y‚qÐ

iq‡¬Ñ«×tb

y

Ït‡¬e¯c

‰Ð

ʀ‡

yCÉ

i

‰y

ew…

y‚

ê

§

‡de

vCƒ

Ñ«×tb

yˆqy

ÔWå‹ew…

yCy

…

r'ˆ

p

y

ʀ‡

yCÉ

i

u

i

y

…

ˆ

p

y‚qy

c

qy§ˆ‰qy‚y

i

r

c’e¯…¢…w‡uÒ

yCÈِqƒ

ѳiq‡¬Ñ«×tb

y

×wc

ˆ

pwiÏ

Ð

¨

u

i

ˆ

cXiq‡¬e



b

y—y

…

˜y

Ԓå‹e

ˆ

pt‡‘ii

y‚v(ˆ

‡

ƒ

e

ɱy

iqp

ƒ•É³ˆ

pwc

ˆ

ê

§

‡‘i

vƒ

Ñ«×tb

yCˆqy

ã

c’ew…

ˆ

p

y‚qyCÈكf‰y

…

yˆ‰yC

Ñe‡dewc

vÐ

‡diŸ…

y‚v

‡d…tcfÏtb

y

ä

‡de

ˆ

p

y

v

cfi

y§É

p

yC‰y±ˆ

p

y

…tc

ˆ

cfÏwcfi

y

i

v

p

y

Ñ«c ‡‘i©c Ït‡¬e¯c

‰ÐXqy

bdc

ˆ

‡

ƒ

e

R

r

cfew…

ÌGvƒ

e¯i·‡‘i

ˆ

i

ƒ’È

c iq‡de



b

y

Ês‡

yCÉ

P

k

(x, y) = ∃x

1

. . . ∃x

k

−1

R(x, x

1

) ∧ R(x

1

, x

2

) ∧ . . . ∧ R(x

k

−1

, y)

É

p

yC‰y

k ≥ 2

r

×

qƒ

ʀ‡‘…w‡de

7ˆ

p

y

e

ƒ

…

y

i

vƒ

ete

y~v(ˆqy

…«Ï

Ð

cž×wc

ˆ

p

ƒ’È

b

y

e

fˆ

p

k

Ԙg

ƒ’ˆqy§ˆ

pwc

ˆˆ

p

y

v

cfi

yžÉ

p

yC‰yhˆ

p

y

ʀ‡

yCÉ

‡de¥ce×wc

ˆ

p

ƒfÈ

b

y

e

fˆ

p

ž‡di

ˆ‰

‡dʀ‡dcfbyi·‡de

vyžˆ

p

y

e

ˆ

p

y

Ês‡

yCÉ

×

‰ƒ

ʀ‡d…

y

i

ˆ

p

yXy

e

ˆ

‡

‰y

…tc

ˆ

c’Ïwc˜i

y

Ô

è

y

iqp

ƒ•Éˈ

p

yžÈك

bdb

ƒ•É

‡de



Ô

V6W

3¢D

F©3

$



465

ÜCÝ

Q



Ü

YU7@9

`g$

ÜCÞdc

î

h•ÜÞ

R

Y’á²Û

k ≥ 2

A

F

à

G

P

#

P

k

Q

Ý

&

ÜCá

Q

&

Y•â%YU7@9VÞqÜç©Þ(à¨Ý´à¨áfe™à¨áÇ݋ÜCÞ(߁â

î

#

P

k

A

F

à¨à

G¡ §àih•Üá

YU7@9

`g$

ÜCÞdc

Q

R©à¨Ý±à‘âÛ˜Ü

í

à¹Û¦Y



ðdÜeç

&

ÜCÝ

&

ÜÞ

P

k

Q

A

 

Þ

î~î

#

A

å‹e™Ê€‡

y‚É˃’È

ã

‡¬Ê

ä

ƒ’È

§

‰ƒ

×

ƒ

iq‡

ˆ

‡

ƒ

e

rfˆ

p

yhyCÓ

‡di

ˆqy

e

vyhƒ’È

c«ê

§

qy‚ÉE

‡

ˆ

‡de



‡‘i¤…

y‚v

‡d…

ñ

c’Ïtb

yfr

i

ƒ

ã

‡d‡

ä

Èك

b¬b

ƒ•É

i

Èِqƒ

Ñ

ã

‡

ä

Ô

ê

ƒ

ewiq‡d…

yC

ã

‡

ä

Ô

sHyˆ

Q

Ï

y

c¤ê

§

c’ew…Øi

u

×t×

ƒ

i

y

P

k

Q

Ô

è

y

iqp

ƒ•É&ˆ

pwc

ˆ«ˆ

p

yC‰y

‡di

cÖê

§

‰yCÉE

‡

ˆ

‡¬e

Çƒ’È

Q

u

iq‡¬e



P

k

Ô

Å

ƒÇˆ

pt‡‘i

y

ew…

r'ɤyIvƒ

ewi

ˆq‰uwv(ˆˆ{ɤƒª„

et‡

ˆ‰y

‡dewi

ˆ

cfe

vy

i

I

c’e¯…

J

i

uwv

p

ˆ

p¯c

ˆ

P

k

(I) = P

k

(J)

r

J

vƒ

e¯i·‡‘i

ˆ

i

ƒ’È

i

y

Ê

yC

c’b@…w‡‘i

¨

ƒ

‡¬e

ˆŸvCƒ

×t‡

y

i

ƒ’È

D

0

r

c’ew…

¯

x ∈ Q(I)

Ô

Å

pt‡di7‡¬Ñ«×tbd‡

y

i

ˆ

pwc

ˆ

¯

x ∈ Q(D

0

)

cfew…

ã

‡

ä

Èك

bdb

ƒ•É

i

Èِqƒ

Ñ

§

qƒ

×

ƒ

i·‡

ˆ

‡

ƒ

e

fÔ

Å

p

y™vƒ

ewi

ˆq‰uwv(ˆ

‡

ƒ

e

ƒfÈ

I

c’ew…

J

‡di…

ƒ

e

y›u

i·‡de



c

v

c

qyCÈÙu

b@Ñ

ƒ

…w‡

„¯v

c

ˆ

‡

ƒ

e

ƒ’Ȥˆ

p

yIv

pwcfi

y

×

qƒwvCy

…

ut‰y

Ô

ê

ƒ

ewiq‡d…

yCˆ

p

y

Ï

y‚

‡detet‡de

`ƒfȗˆ

p

yv

pwc˜i

y

i

y~Ƙuwy

e

vCy

c˜iŸ…

yC„

e

y

…–‡de

x€y~v(ˆ

‡

ƒ

e

tÔ

s9yCˆ

D

0

= [Q]

r

S

0

= V (D

0

)

r

D

0

= V

−1

(S

0

)

r

V

1

= V (D

0

)

r

c’ew…

S

1

= V

1

− S

0

Ô

 

3#$

$

6£¢ 4

S

0

Y•áƒÛ

S

1

&

Yh’Ü«Û•à‘⥤

î

à¨áwݗÛ

î

ßpY’à¨átâ

A

}‰ö

p

v

m

—‚|‹˜wš¢¡9vw•’gji~k‚‰¤£€™wš¦¥hv¤¥¤fu—‚™’‰

 

Þ

î~î

#

A

x€u

×t×

ƒ

i

yªˆ

pwc

ˆ

a, b ∈ P

k

(D

0

)

Èكf

i

ƒ

Ñ

y

a ∈ dom(S

0

)

ã

ˆ

p

y

v

cfi

yªÉ

p

y

e

b ∈ dom(S

0

)

‡di±i·‡dÑ«‡¬b‘c



ä

Ô

è

y

iqp

ƒ•É°ˆ

pwc

ˆ

b

v

cfete

ƒ’ˆ

Ï

y

‡de

dom(D

0

) − dom(S

0

)

Ô

x

‡de

vCy

a, b ∈ P

k

(D

0

)

r9ˆ

p

y‚qy

‡‘ic×wc

ˆ

p

ƒfÈ

b

y

e

’ˆ

p

k

Èِqƒ

Ñ

a

ˆ‰ƒ

b

Ô¥g

ƒ’ˆ‰y«ˆ

pwc

ˆ

D

0

pwcfiže

ƒ

vÐwv

b

y

i

ƒfÈ

b

y

e

fˆ

pÖb

y

iqi

ˆ

pwc’e

k

ÔHå

ˆXÈك

bdb

ƒ•É

i

ˆ

p¯c

ˆy

‡

ˆ

p

yC

a = b

ƒf

d(a, b) = k

Ô9å‹e

ˆ

p

y

„w

i

ˆŸv

cfi

y¢É±y

c

qy

…

ƒ

e

y

ﴌ

È

d(a, b) = k

r

Ï

ÐÖvCƒ

ewi

ˆq‰uwv(ˆ

‡

ƒ

e

ƒ’È

D

0

r

b

v

cfe

ƒ

etb

Ð

Ï

y

‡de

dom(S

0

)

Ô

2

g

yӀˆ~r

b

yˆŸu

i

vCƒ

ewi

ˆq‰uwv(ˆ

cÇi·×

y‚v

‡dcfb±Ït‡dewc

qÐ`qy

bdc

ˆ

‡

ƒ

e

M

cfi

Èك

bdb

ƒ•É

i‚Ô

Å

p

y

…

ƒ

Ñ¢c’‡de

ƒ’È

M

vƒ

ewi·‡‘i

ˆ

i

ƒ’È

dom(S

1

)

c’e¯…

rWÈكf¢y

c

v

p

α ∈ dom(S

1

)

r

e

yCÉ

…w‡di

ˆ

‡de

vˆ›y

b

y

Ñ

y

e

ˆ

i

x

α

1

, . . . , x

α

k

−1

Ô

M

pwcfi

ˆ

p

yžÈك

bdb

ƒ•É

‡¬e

ey

…

fy

i

Ú

ÈكfEy

c

v

p

α ∈ dom(S

1

)

rwˆ

p

yXy

…

˜y

i

α → x

α

1

→ . . . → x

α

k

−1

;

c’ew…

Èكf7y

c

v

p

α, β ∈ S

1

,

c’e

y

…

fy

x

α

k

−1

→ β.

Å

p

yžÈك

bdb

ƒ•É

‡de



‡di

y

cfiq‡db

Ð

iqp

ƒ•É

eÏ

ÐIvƒ

e¯i

ˆ‰quwvˆ

‡

ƒ

e

ƒ’È

M

Ô

 

3#$

$

6¡ 

4

5

ÜCÝ

M



Ü

íjî

átâ(Ý´Þ

$

í

݋ÜjÛ

Y•âpY



î

h’Ü

A

&

Üá

P

k

(M )

íjî

átâ(à‘â(ݹâ

î

#

k

ەà‘⥤

î

à¨áwÝ

í‰î

ï²à¹Üâ

î

#

S

1

A£¢’ïwÜ

í

à

&

í

Y•ð¨ðqc

R

α, β ∈ S

1

à

¥

α, β ∈ P

k

(M )

Y’á²Û

x

α

i

, x

β

i

∈ P

k

(M )

#

î

Þ

1 ≤ i ≤ k − 1

A

è

y

e

ƒ•ÉVu

i

y

M

ˆqƒ™vCƒ

ewi

ˆq‰uwv(ˆ ƒfut

…

y

iq‡

qy

…T‡¬ewi

ˆ

cfe

vy

i

I

c’ew…

J

Ô

s9yˆ

I

vCƒ

ewiq‡‘i

ˆ7ƒfÈ

k

…t‡di7¨

ƒ

‡de

ˆŸvƒ

×t‡

y

i

ƒ’È

[Q]

ˆqƒf˜yˆ

p

yCÉ

‡

ˆ

p

M

r

c’ew…

J

vCƒ

ewiq‡‘i

ˆƒfÈ

k

…w‡‘i

¨

ƒ

‡¬e

ˆŸvCƒ

×t‡

y

i

ƒfÈ

D

0

Ô

Å

p

y

eTÏ

ЙsHy

Ñ«Ñ¢cpQ

rwqy

i·×

y‚vˆ

‡dÊ

y

b

ЛsHy

Ñ«Ñ¢c



r

P

k

(J)

c’ew…

P

k

(I)

Ï

ƒfˆ

p

vƒ

ewi·‡‘i

ˆ§ƒfÈ

k

…t‡di7¨

ƒ

‡de

ˆXvCƒ

×t‡

y

i

ƒfÈ

S

0

c’ew…

k

…w‡di7¨

ƒ

‡de

ˆvƒ

×t‡

y

i

ƒ’È

S

1

Ôa0

Ð

c’×t×

‰ƒ

×



‡‘c

ˆ‰y

b

Ð¥qy

ewc’Ñ«‡de



y

b

y

Ñ

y

e

ˆ

ihcfiEe

yCy

…

y

…

r¯É±yXƒ

Ï

ˆ

cf‡¬e

P

k

(I) = P

k

(J)

Ô

x

‡de

vCy

P

k

Q

r

Q(I) = Q(J)

Ô

0

uwˆ

¯

x ∈ Q(I)

i·‡de

vy

I

vƒ

e

ˆ

c’‡dewi

[Q]

Ôwå

ˆ—Èك

b¬b

ƒ•É

i

ˆ

pwc

ˆ

¯

x ∈ Q(J)

Ô

x

‡¬e

vCy

J

qyCˆq

c

vˆ

i

ˆ‰ƒ

D

0

‡

ˆ Èك

bdb

ƒ•É

i

ˆ

p¯c

ˆ

¯

x ∈ Q(D

0

)

i

ƒ

Ï

Ð

§

‰ƒ

×

ƒ

iq‡

ˆ

‡

ƒ

e



r

Q

p¯cfi cTê

§

‰yCÉE

‡

ˆ

‡¬e



‡de

ˆqy‚

Ñ¢i

ƒ’È

P

k

Ô

Å

pw‡di

vCƒ

Ñ«×tb

yˆ‰y

i

ˆ

p

y

×

qƒ€ƒfÈ¥ƒ’È

Å

p

y‚ƒf‰y

Ñ

wÔ

2

¤

¢`À±½7Ã

¨·Â

€Ä{À½

x€y

Ê

yC

c’bs‡¬Ñ«×

ƒfqˆ

c’e

ˆ©Æsuty

i

ˆ

‡

ƒ

ewi

‰y

Ñ¢c’‡de

u

e

qy

i

ƒ

b¬Ê

y

…

Èك˜@vƒ

e©¨

u

e

vˆ

‡dÊ

y§Æ˜uwyC

‡

y

iCԕÕ'‡



i

ˆ‚r

…

y

ñ

v

‡‘…tc’Ït‡dbd‡

ˆ{Ðeƒ’È

…

yCˆqyC

Ñ«‡¬e¯c

vÐe‰y

Ñ¢c’‡dewi

ƒ

×

y

e¢‡¬e™Ï

ƒfˆ

p

ˆ

p

y—„

et‡

ˆqy

c’ew…

u

e

qy

i

ˆ‰

‡

v(ˆ‰y

…

v

cfi

y

i‚Ô

å‹e

È

c

v(ˆ~r

‡

ˆqy

Ñ¢c’‡dewi

ƒ

×

y

e

É

p

yCˆ

p

y‚u

e

‰y

i

ˆq

‡

v(ˆqy

…

c’ew…

„

et‡

ˆqy

…

yˆ‰yC

Ñe‡dewc

vÐÇvCƒ

‡de

v

‡‘…

y

Ô

g

ƒ’ˆ‰y›ˆ

pwc

ˆ

‡

ÈEˆ

p

y

b‘c

ˆ·ˆ‰yC

p

ƒ

b‘…ti

rHˆ

pt‡di‡¬Ñ«×tbd‡

y

ie…

y‚v

‡d…tcfÏt‡db¬‡

ˆ{Ð`ƒfÈ

…

yˆ‰yC

Ñ«‡¬ewc

vÐ

ÔHå‹ew…

y‚y

…

r

ˆ

p

y

e™…

yˆ‰yC

Ñ«‡¬ewc

vÐeɱƒ˜u

b‘…¢Ï

yh

Ô

y

Ô

ã

u

iq‡de

ˆ

p

yhv

pwc˜i

y

×

qƒwvCy

…

ut‰y

ä

c’ew…

vCƒ

ñ



Ô

y

Ô

ã

Ï

y‚v

c

u

i

y

È

c’‡db

ut‰yžƒ’È'„

et‡

ˆqy

…

yCˆqy‚

Ñ«‡dewc

vCÐ

‡di

É

‡

ˆ

e

y

i‰i

y

…IÏ

Т„

et‡

ˆ‰y

‡¬e¯i

ˆ

c’e

vCy

i

ä

Ô

å

È

‡

ˆ§ˆ‰ut

e¯i

ƒ˜uwˆ§ˆ

pwc

ˆ±„

et‡

ˆ‰y

c’ew…™‡¬e

„

et‡

ˆ‰y

…

yˆ‰yC

Ñe‡dewc

vÐ

c

‰y

…t‡di

ˆ

‡de

v(ˆ§Èك˜

ê

§

i

rsˆ

p

y

e

‡

ˆ

Ñ¢c

Ð

Ï

y«ˆ

p

yIv

cfi

yŸˆ

pwc

ˆu

e

‰y

i

ˆq

‡

vˆqy

…`…

yCˆqy‚

Ñ«‡dewc

vCÐ

‡diX…

y‚v

‡‘…tcfÏtb

y˜r9É

pt‡db

y«„

et‡

ˆ‰y

…

y

ñ

ˆqyC

Ñ«‡¬e¯c

vÐ

‡di«e

ƒfˆ

Ô@a7bdi

ƒwr©É¤y¥v

c’e

ƒ

Ï

ˆ

c’‡deØÕ! 

‰yCÉE

‡

ˆ

‡¬e



i

É

p

y

e

y

Ê

y‚«Ì

…

yˆqy‚

Ñ«‡de

y

i

Q

‡de

ˆ

p

y«u

e

‰y

i

ˆq

‡

vˆqy

…

v

c˜i

y˜rƒÉ

pt‡¬b

yeˆ

p

y

Ï

y

i

ˆXvCƒ

Ñ«×tb

yˆ‰y

b‘c’e

fu

c

fy

‡de

ˆ

p

ye„

et‡

ˆqy¢v

cfi

y

qy

Ñ«cf‡¬e¯i

∃

x

 

∩ ∀

x

 ŸÔ

x

‡¬e

vyžu

e

‰y

i

ˆq

‡

vˆqy

…™…

yCˆqyC

Ñ«‡¬e¯c

vÐ

‡dÑ«×tbd‡

y

i

„

et‡

ˆqy

…

yˆ‰yC

Ñ«‡¬ewc

vИr

c’e`cfb

˜ƒf

‡

ˆ

ptÑ

Èكf ˆ‰y

i

ˆ

‡de

Tu

e

‰y

i

ˆq

‡

vˆqy

…`…

yˆ‰yC

Ñ«‡¬ewc

vЪvCƒfu

b‘…ªÏ

y«u

i

y

…LJdeÖ×



c

v(ˆ

‡

vCy

c˜i

c–i

ƒ˜u

ew…

Ï

utˆ

‡de

vƒ

Ñ«×tb

yCˆqy

cfb

˜ƒf

‡

ˆ

ptÑ

Èكf›ˆ‰y

i

ˆ

‡de

¤„

ew‡

ˆ‰y

…

yCˆqyC

Ñ«‡¬e¯c

vЃÚ

c’bdb7×

ƒ

iq‡

ˆ

‡¬Ê

y

c’ewi

ɱy‚

i

ɤƒfu

b‘…–‡dÑ«×tb

Ж„

et‡

ˆqy

…

yˆ‰yC

Ñ«‡¬ewc

vИr

Ï

uwˆ«ˆ

p

y

c’b

fƒ˜

‡

ˆ

pwÑ

vCƒfu

b‘…

‰yˆ‰ut

e

È

c’b‘i

y

e

yC

c

ˆ

‡dÊ

y

iCÔ

è

p

y

e

ˆ

p

y

c’b

fƒ˜

‡

ˆ

pwÑ

c

vCvy

×

ˆ

i

r'ɱyIɱƒ˜u

bd…ºc’b‘i

ƒ

pwc’Ê

y

c

fu

c



cfe

ˆqyCy

…

Õ( 

d¤g‰{g‰z{­Xfh™€—C‰–—‚™sr

o

gqŒ©z{fh{fh™˜ižk‚ŽH”'k‚™‚‘´‰s™sq{fut~g¡ ¤‰sg‰z{fhgj|@“¤|‹fh™˜i'¥¤fhg‰Œ@|

}a 

qy‚ÉE

‡

ˆ

‡de



Ô

Å

p

u

i

r˜ˆ

p

y u

e

‰y

i

ˆq

‡

vˆqy

…

v

c˜i

y

Ñ«c

Ðeˆ‰ut

e

ƒfutˆ±ˆ‰ƒ

Ï

y ƒfÈ

×



c

vˆ

‡

v

c’b²‡de

ˆ‰yC‰y

i

ˆ

‡

È

„

et‡

ˆqy

…

yCˆqyC

Ñ«‡¬e¯c

vÐ

‡di

u

e¯…

y‚v

‡d…tcfÏtb

yfrtƒ˜§ˆqƒ«ƒ

Ï

ˆ

c’‡deÕ! 

‰yCÉE

‡

ˆ

‡de



i‚Ô

è

pt‡¬b

y É±y yÓ

‡dÏt‡

ˆ‰y

…i

ƒ

Ñ

y v

bdc˜iqi

y

i

ƒ’È

ê

§

Ês‡

yCÉ

i

Èك˜¤É

pw‡

v

p¥ê