Hướng dẫn các chứng minh mà không cần tiết lộ thông tin phần 3

Đầu vào: hai đồ thị đẳng cấu G1 và G2 ,mỗi đồ thị có tập đỉnh {1...n} 1. 2. 3. 4. 5. 6. 7. 8. 9. T = (G1, G2) For j = 1 to n do Xác định tàng thái cũ bằng trạng thái (V*) Repeat Chọn ngẫu ij=1 hoặc 2 Chọn pj là phép hoán vị ngẫu nhiên của {1...n}
Nội dung trích xuất từ tài liệu:
Hướng dẫn các chứng minh mà không cần tiết lộ thông tin phần 3Vietebooks Nguyễn Hoàng Cương §Çu vµo: hai ®å thÞ ®¼ng cÊu G1 vµ G2 ,mçi ®å thÞ cã tËp ®Ønh {1...n} 1. T = (G1, G2) 2. For j = 1 to n do 3. X¸c ®Þnh tµng th¸i cò b»ng tr¹ng th¸i (V*) 4. Repeat 5. Chän ngÉu ij=1 hoÆc 2 6. Chän pj lµ phÐp ho¸n vÞ ngÉu nhiªn cña {1...n} TÝnh Hj lµ ¶nh cña Gi theo ρj 7. 8. Gäi V* víi ®Çu vµo Hj ta thu ®−îc mét yªu cÇu I’, 9. If ij = I’j then ghÐp (Hj, ij, ρj) vµo ®u«i cña T Else ThiÕt lËp l¹i V* b»ng c¸ch x¸c ®Þnh tr¹ng th¸i (V*) = tr¹ng th¸i cò 10. Until ij=i’j §Ó chøng minh r»ng hÖ thèng chøng minh lµ kh«ng tiÕt lé th«ng tinhoµn thiÖn ta cÇn mét phÐp biÕn ®æi chung ®Ó x©y dùng mét bé m« pháng S*tõ V* bÊt kú. Ta sÏ tiÕp tôc thùc hiÖn viÖc nµy ®èi víi hÖ thèng chøng minhcho tÝnh ®¼ng cÊu ®å thÞ. Bé m« pháng sÏ ®ãng vai trß cña Peggy sö dông V*nh− mét “ch−¬ng tr×nh con” cã kh¶ n¨ng khëi t¹o l¹i. Nãi mét c¸ch kh«ngh×nh thøc S* sÏ cè g¾ng gi¶ ®Þnh mét yªu cÇu ij mµ V*sÏ ®−a ra trong mçivßng j. tøc lµ S* sÏ t¹o ra mét bé ba hîp lÖ ngÉu nhiªn cã d¹ng (Hj, Þj, ρj) vµthùc hiÖn thuËt to¸n V* ®Î thÊy ®−îc yªu cÇu cña nã dµnh cho vßng j. nÕu gi¶®Þnh ij gièng nh− yªu cÇu i’j(nh− ®−îc t¹o bëi V*) th× bé ba (Hj, Þj, ρj) sÏ®−îc g¾n vµo b¶n sao gi¶ m¹o. nÕu kh«ng thÞ bé ba nµy sÏ bÞ lo¹i bá, S* sÏgi¶ ®Þnh mét yªu cÇu míi ij vµ thuËt to¸n V* sÏ ®−îc khëi ®éng l¹i sau khithiÕt lËp l¹i tr¹ng th¸i cña nã vÒ trµng th¸i b¾t ®Çu cña vßng hiÖn thêi . thuËtng÷ “tr¹ng th¸i ”®−îc hiÓu lµ c¸c gi¸ trÞ cña tÊt c¶ c¸c biÕn dïng trong thuËtto¸n. B©y giê ta sÏ ®−a ra mét m« t¶ chi tiÕt h¬n vÒ thuËt to¸n m« pháng S*.ëthêi ®Ióm b¸t kú cho tr−íc, trong khi thùc hiªn ch−¬ng tr×nh V* tr¹ng th¸ihiÖn thêi cña V* sÏ ®−îc ký hiÖu lµ state (V*). Mét m« t¶ gi¶ m· cña thuËtto¸n m« pháng ®−îc cho ë h×nh 13.7 Trang 11Vietebooks Nguyễn Hoàng Cương Cã kh¶ n¨ng bé m« pháng sÏ kh«ng dõng l¹i nÕu kh«ng x¶y ra ij = i’j.tuy nhiªn cã thÓ chøng tá r»ng thêi gian ch¹y trung b×nh cña bé m« pháng lµthêi gian ®a thøc vµ hai ph©n bè x¸c suÊt ????????(T)vµ ???????(T)lµ ®ångnhÊt.§Þnh lý 13.2 HÖ thèng chøng minh t−¬ng hç cho tÝnh ®¼ng cÊu ®å thÞ lµ mét hÖ th«ngchøng minh kh«ng tiÕt lé th«ng tin hoµn thiÖn.Chøng minh: Tr−íc tiªn ta thÊy r»ng bÊt luËn V* t¹o ra c¸c yªu cÇu cña nã ra sao,x¸c suÊt ®Ó gi¶ ®Þnh i’j lµ b»ng 1/2. Nh− vËy trung b×nh S* ph¶I t¹o ®−îc haibé ba ®Ó t¹o ®−îc hai bé ba ,®Ó t¹o ®−îc mét bé ba g¾n voµ b¶n sao gi¶ m¹o.Do ®ã thêi gian ch¹y trung b×nh lµ thêi gian ®a thøc theo n . NhiÖm vô khã kh¨n h¬n lµ ph¶I chøng tá r»ng hai ph©n bè x¸c suÊt????????(T)vµ ????????????(T) lµ nh− nhau.ë ®Þnh lý 13.1(trong ®ã Vic lµng−êi kiÓm tra trung thùc) ta ®· tÝnh ®−îc hai ph©n bè x¸c suÊt vµ thÊy r»ngchóng lµ ®ång nhÊt. Ta còng ®· sö dông mét yÕu tè lµ c¸c bé ba (H, i, ρ)®−îc ë c¸c vßng kh¸c nhau cña phÐp chøng minh lµ ®éc lËp. Tuy nhiªn trongb¸i to¸n nµy ta kh«ng cã c¸ch tÝnh to¸n t−êng minh hai ph©n bè x¸c suÊt.H¬n n÷a c¸c bé ba ®−îc t¹o ë c¸c vßng kh¸c nhau cña phÐp chøng minh l¹ikh«ng ®éc lËp. VÝ dô yªu cÇu mµ V* ®−a ra vßng j cã thÓ phô phuéc theo 1kiÓu rÊt phøc t¹p nµo ®ã vµo c¸c yªu cÇu ë c¸c vßng tr−íc vµ vµo c¸ch Peggy®¸p øng c¸c yªu cÇu ®ã. C¸ch kh¾c phôc c¸c khã kh¨n nµy lµ ph¶i xem xÐt c¸c ph©n bè x¸cxuÊt trªn c¸c b¶n sao bé phËn cã thÓ cã trong qu¸ tr×nh m« pháng hoÆc chøngminh t−¬ng hç vµ sau ®ã tiÕp tôc b»ng ph−¬ng ph¸p quy n¹p trªn sè c¸cvßng. Víi 0 ≤ j ≤ n ta x¸c ®Þnh c¸c ph©n bè x¸c xuÊt pτ,v,j(T) vµ pτ,v,n(T) trªntËp c¸c b¶n sao bé phËn Tj xuÊt hiÖn ë cuèi vßng j. Chó ý r»ng pτ,v,j(T) =pτ,v(T)vµ pτ,v,n(T) = pτ,v(T). Bëi vËy nÕu cã thÓ chøng tá r»ng hai ph©n bèpτ,v,j(T) vµ pτ,v,j(T) lµ ®ång nhÊt víi mäi j th× ta cã ®iÒu cÇn chøng minh . Tr−êng hîp j = 0 øng víi khi b¾t ®Çu thuËt to¸n : lóc nµy b¶n sao chØ gåmhai ®å thÞ G1 vµ G2 .Bëi vËy c¸c ph©n bè x¸c suÊt lµ ®ång nhÊt khi j = 0 .Ta sÏsö dông ®iÒu kiÖn ®Ó b¾t ®Çu phÐp quy n¹p. Trang 12Vietebooks Nguyễn Hoàng Cương Tr−íc tiªn ta gi¶ sö hai ph©n bè x¸c suÊt pτ,v,j-1(T), vµ pτ,v,j-1(T) trªn τj-1 lµ®ång nhÊt víi gi¸ trÞ j ≥ 1 nµo ®ã. Sau ®ã ta sÏ chøng tá r»ng hai ph©n bè x¸csuÊt pτ,v,j(T) vµ pτ,v,j(T) trªn τj lµ ®ång nhÊt . XÐt ®iÒu sÏ x¶y ra trong vßng j cña phÐp chøng minh t−¬ng hç. X¸csuÊt ®Ó yªu cÇu cña V lµ ij =1 lµ mét sè thùc p nµo ®ã vµ x¸c suÊt ®Ó yªu cÇucña V ij = 2 lµ 1-pi. ë ®©y pj phô thuéc vµo tr¹ng th¸i cña thuËt to¸n V khi b¾t®Çu vßng lÆp j. ë trªn ®· nhËn xÐt r»ng trong phÐ ...