Tính không khác biệt của cấu trúc bọt biển

Trong trường hợp cấu trúc bọt biển, nó được chứng minh là có thể phân biệt được với RO. Trong bài báo của Bertoni và cộng sự, nút bị bão hòa có nghĩa là gì. Làm thế nào để nó trở nên bão hòa và điều kiện dẫn đến lỗi trong trình giả lập là không rõ ràng.

Liên kết giấy: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=09F733C00E75E6BB3E3537ACFAE4396E?doi=10.1.1.544.7974&rep=rep1&type=pdf

Độ bão hòa được định nghĩa trong phần 4.1 là điều kiện $R \cup O = C$, ở đâu $O$ là tập hợp các siêu nút với các cạnh hướng ra ngoài và $R$ là tập hợp các siêu nút gốc và $C$ là lớp tương đương của tất cả các nút có phần "C" bằng nhau.

Ý tưởng là bất kỳ truy vấn nào đối với tiên tri nén sẽ chỉ hiển thị một đường dẫn duy nhất trong biểu đồ khi nút bắt đầu được root. Nếu nút bắt đầu không được root, một đường dẫn ngẫu nhiên sẽ được chọn nhưng không được tiết lộ cho đối thủ.

Để thực hiện điều đó, chúng tôi tránh các siêu nút có gốc với các cạnh hướng ra ngoài; mặt khác, điều này tiết lộ nhiều con đường hơn cho kẻ thù. Do đó, trình mô phỏng không thể sử dụng thủ thuật này khi biểu đồ đã bão hòa, tức là $O = C$và các câu trả lời sẽ không nhất quán nữa.

Định lý là bão hòa chỉ xảy ra sau $2^c$ truy vấn, ở đâu $c$ là năng lực.