Oracle phổ quát bậc 2 ?

Ok, đây là tôi tự bổ túc văn hóa về complexity thôi.

Trong lý thuyết complexity, người ta nói đến các oracle, tức là các “hộp đen” để tính các hàm (hay trả lời các câu hỏi) nào đó,  chỉ cần cho input (thuộc loại nào đó) vào đấy thì sẽ ra ngay output, coi như là chỉ mất 1 bước tính toán, thay vì nhiều bước trong thực tế.  Kiểu như đi xem bói, hỏi oracle vậy, hỏi câu nào thì oracle trả lời ngay câu đó, không cần “suy luận dài dòng”.

Bây giờ tôi muốn “nặn” ra một cái oracle phổ quát bậc hai như sau:

Với mọi ánh xạ bậc hai F từ {0,1}^n vào {0,1}^n (tức là các thành phần của F đều viết được dưới dạng đa thức bậc 2 trên trường {0,1}), thì oracle này tính ngược hay tính xuôi F cũng đều được (chỉ mất 1 bước tính toán). Tính ngược ở đây hiểu là tìm các preimages nếu có và nếu không có thì bảo là không có.

Vì là để tính F bằng thuật toán thông thường thì thời gian tính cũng là đa thức thôi (kể cả tính xuôi lẫn tính ngược — khi tính ngược thì hạn chế só preimage mà nó tìm), nên oracle này sẽ không làm thay đổi lớp các ánh xạ tính được (xuôi hay ngược) theo thời gian đa thức ?!

Bây giờ ta xét ánh xạ mà là hợp của k cái ánh xạ bậc hai:

F = F1 ° F2 ° … ° Fk

trong đó k là một số chạy từ 1 đến n

Vấn đề tính xuôi cho F: dùng oracle thì mất (nhiều nhất là) k bước

Để tính ngược F, cần *trung bình* tối thiểu là bao nhiêu bước ?!

Con số này phụ thuộc vào k, và tăng theo k ?! (Vì sao tăng ?!)

Gọi nó là số B(k)

Nếu như B(k) tăng một cách super-polynomially theo k, thì điều này sẽ chứng tỏ là NP khác P ?!

Làm sao mà ước lượng chẳng hạn B(2), rồi các B(k) tiếp theo, bằng qui nạp ?!

Với oracle phổ quát bậc 2, thì B(k) có stable theo n (với điệu kiện n đủ lớn) không ?!

 

 

 

 

 

 

 

 

Print Friendly

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

This blog is kept spam free by WP-SpamFree.