Bạn Thắng có vài câu hỏi về phân tích độ phức tạp thuật toán, tôi trả lời vắn tắt dưới đây.
1) “intractable problems” là gì trong 2 đáp án sau:
1.a) Là bài toán đã bị chứng minh là cận dưới của độ phức tạp thuật toán là super-polinominal.
1.b) Là bài toán mà cho đến nay người ta chỉ tìm được thuật toán có độ phức tạp superpolinominal, ngoài ra chưa thể kết luận gì thêm được.
(Trong trường hợp đáp án là 1.b) thì các bài toán 1.a) có thuật ngữ riêng để gọi không ? Đó là thuật ngữ gì ?)2) “intractable problems” không đồng nghĩa với “NP-complete” hoặc “NP-hard”, “intractable problems” là khái niệm không liên quan gì đến NP, NP-hard. Phát biểu này đúng hay sai ?
3) Có thể xảy ra (dù khả năng là vô cùng nhỏ) NP-hard = NP ?
4) Phát biểu “Non-Determined Turing Machine là máy có khả năng siêu nhiên: khi nó phải quyết định chuyển trạng thái với nhiều lựa chọn thì nó sẽ biết trạng thái tối ưu để chuyển. Tuy nhiên ngay cả khi có khả năng siêu nhiên nó cũng có thể thất bại.” là đúng hay sai ?
5) Giả sử có một máy non-determined Turing machine được chạy 2 lần với cùng trạng thái ban đầu. Kết quả của 2 lần chạy có giống nhau không ?
6) Bài toán: “Liệt kê (in ra màn hình) tất cả các giá trị có thể có của một xâu nhị phân n bit. Tức là liệt kê ra 2^n – 1 xâu: 00…00, 00…01, 00…10, … … … , 11…11.”
6.1) Theo như định nghĩa “NP problems là các problems mà ta có thể verify lời giải của nó trong thời gian đa thức” thì bài toán trên có là NP không ?
6.2) Thuật toán giải bài này hiển nhiên phải chứa thao tác in được 2^n – 1 xâu ra màn hình. Nếu mỗi thao tác in ra màn hình chỉ in được 1 xâu thì thuật toán là O(2^n). Liệu có thể nào mà mỗi thao tác in ra màn hình có thể in được f(n) xâu, và do đó thuật toán là O(2^n/f(n)) ? (nếu không thể nào 1 lần in mà in được f(n) xâu thì chứng tỏ độ phức tạp thuật toán của bài toán này có cận dưới là 2^n.)
7. Người ta nghĩ về máy Turing nhưng lại ngồi gõ bàn phím máy Intel. Liệu trong lịch sử “Theory of computation” có bài báo nào chứng minh: “Máy Turing quả thật có thể mô phỏng hoạt động của máy Intel (giả sử với bộ vi xử lý sơ khai nhất của hãng) mà số bước mô phỏng chỉ bị chậm đi với hệ nhân O(n^k).” Chiều ngược lại thì đơn giản. Điều này được gọi là máy Turing và máy Intel tương đương đa thức với nhau về khả năng tính toán hiệu quả (độ phức tạp thuật toán).
Trả lời (vắn tắt):
1. & 2. Tại sao lại cho multiple-choice khi mà bạn chưa biết câu trả lời là gì? (Đây là tôi giả sử bạn hỏi thật lòng, không phải đánh đố.)
Intractable problems cũng giống như phụ nữ đẹp. Không có một định nghĩa toán học cho “intractability”. Người ta thường (nhưng không phải luôn luôn) dùng “intractable problems” để nói về các bài toán mà lời giải tốt nhất mà ta biết nhiều khả năng là không hoạt động được trên thực tế. Giả sử có bài toán mà thuật toán tốt nhất mà ta biết giải được trong thời gian O(n), nhưng cái hằng số trong big-O bằng tổng số nguyên tử trong vũ trụ, thì bài toán đó là “intractable”.
3. NP-hard khác NP. Bài toán dừng (halting problem) là NP-hard nhưng không thuộc NP.
4. Tôi không hiểu câu hỏi. “Thất bại” là sao? “Siêu nhiên” là sao? Một trong những cách hiểu NTM là nó là cái máy “may mắn” tuyệt đối.
5. NTM chỉ là một công cụ toán học để mô tả sức mạnh và giới hạn của một kiểu tính toán, không thể “chạy” nó được như DTM (cái dùng để mô hình hóa một quá trình tính toán cụ thể và vì thế có thể chạy được).
6.1. Bài toán “in” của bạn không phải là decision-problem, chẳng thuộc P hay NP hay EXP.
6.2. Tùy theo mô hình tính toán của bạn là gì. Nếu cụm từ “in ra màn hình” ý nói đến việc “Máy Turing ghi từng bit ra output tape” thì dĩ nhiên độ phức tạp thời gian của bài toán ít nhất là 
7 Tính tương đương của máy tính hiện đại dùng bộ vi xử lý mới nhất thì chưa ai chứng minh. Nhưng cũng không cần phải chứng minh. Những thứ có cấu hình tương tự như một máy tính hiện đại (ví dụ như lớp các mô hình Register Machine, và trường hợp đặc biệt là Random Access Machine) thì người ta đã chứng minh lâu rồi. Nói chung, trừ phi bộ vi xử lý mới toanh của Intel có thể tính được một hàm số nào mà TM không tính được, sự tương đương là hiển nhiên. Các tập lệnh kiểu cộng trừ nhân chia, if .. then .. else, goto đều có thể mô phỏng được bằng TM hết.
11 Comments
1 & 2. Những cái multiple-choice là những cách hiểu khác nhau của em cho một vấn đề mà chưa biết cách hiểu nào là đúng. Em chỉ muốn chọn lấy một cái chính xác nhất để ghi nhớ, nhưng hóa ra không có định nghĩa rõ ràng, chặt chẽ cả.
6. Bài toán “in” thuộc dạng function problems (http://en.wikipedia.org/wiki/Function_problems), không phải decision problems. Có thể hiểu function problems thì tổng quát hơn là decision problems; nếu như decision problems có lớp P, NP thì function problems cũng có lớp FP, FNP tương ứng.
=> câu hỏi của em có thể sửa lại thành dạng tương ứng.
“Bài toán “in” thuộc FP hay FNP”.
Bài toán “in” rất quan trọng đối với em vì nó tương đương với một bài toán X mà em đang làm. Bài toán X cho đến nay lời giải tốt nhất vẫn là O(2^n) và em mong có thể hạ xuống còn O(2^n/f(n)) với ít nhất f(n) = căn bậc hai của n hoặc thậm chí n.
Từ mỗi bước “in ra màn hình một xâu n bit” chỉ cần thêm một thao tác O(n) thì sẽ thành một bước trong thuật toán tốt nhất hiện nay cho bài toán X. Như vậy cận dưới của bài toán “in” sẽ cho biết cận dưới của bài toán X. Nhưng như anh trả lời thì dường như bài toán “in” chỉ có thể là O(2^n) thôi không thể thấp hơn được nữa. Do đó việc em cố gắng tìm thuật toán tốt hơn cho bài toán X là insanely ? Em hi vọng lối thoát nằm ở Quantum computer với tính chồng chập trạng thái lượng tử để có thể tại một bước in ra được f(n) xâu nhị phân do đó hạ bài toán X ban đầu xuống O(2^n/ f(n)).
Tiếp tục con đường này có ổn không anh ?
6.3) Em rất sợ mình đang cố gắng tìm thuật toán đa thức cho một … NP-complete ! Mặc dù như anh nói bài toán “in” (và do đó bài toán X) không phải là decision problem nên nó không là P, NP, EXP được. Tuy nhiên có thể phát biểu lại bài toán “in” cho nó thành decision problems:
Bài toán converted “in”: “Có thể nào trong k bước in ra được tất cả các xâu n bit được không ?”
Vậy bài toán này có phải là NP hay không ?
Nếu nó là NP rồi thì em không biết mình sẽ nên – chứng minh nó là NPC để dừng luôn lại hay là tiếp tục tìm thuật toán đa thức.
Mong anh cho lời khuyên.
6.4 Em không thấy có lớp NP-complete cho các function problems (tạm gọi là FNP-complete) trong Complexity zoo (http://qwiki.stanford.edu/wiki/Complexity_Zoo:F). Người ta chưa chỉ ra được một bài toán nào là FNP-complete hả anh, hay là vấn đề là như thế nào mà em chưa rõ.
Chào Thắng,
Bài toán “in” có kích thước input là
, kích thước output là 
. Do đó nó không thuộc FNP. Bạn có thể tự nghĩ ra tên cho nó, như F-EXPEXP chẳng hạn. Bài toán này có độ phức tạp thời gian 
một cách hiển nhiên (giả sử TM in 1 bit trong 1 bước). Bây giờ nếu không dùng TM mà dùng mô hình khác, mỗi “bước” in được 
ký tự, thì cứ thế mà chia.
Cái formulation của bạn không phải là decision problem theo kiểu định nghĩa P, NP, EXP, v.v.
Cái hàm số mà bạn muốn tính là total function, input nào thì cũng có output cả. Điều này khác với một số hàm số có phiên bản yes/no một cách tự nhiên. Ví dụ như bài toán FSAT, tính một satisfying assignment cho một công thức Bool, là bài toán có phiên bản yes/no. Có định nghĩa FNP-complete và chứng minh rằng FSAT là FNP-complete không khó gì, gần giống hệt như chứng minh SAT là NP-complete. Theo nghĩa này thì các bài toán cho các hàm không phải là hàm total (như kiểu FSAT) đều có decision-analog và nghiên cứu chúng cũng tương tự như nghiên cứu các decision-versions của chúng. Ta có thể chứng minh được NP = P nếu và chỉ nếu FNP=FP, vân vân.
Tuy nhiên có một tập con của FNP không có phiên bản decision (ví dụ như bài toán FACTORING), dành cho các hàm total. Người ta thường dùng TFNP để chỉ tập các bài toán này. Bài toán của bạn là một loại hàm total, vì thế phải dùng TF-XYZ để mô tả nó. Nhưng “bài toán in” không thuộc TFNP.
Dùng khái niệm “completeness” để chứng minh độ khó của “bài toán in” là giết gà bằng giao mổ trâu, vì như đã nói độ phức tạp của nó là hiển nhiên. Và, quan trọng hơn hết, “bài toán in” không thể là một bài toán “complete” trong bất kỳ một lớp complexity thông thường nào. Cái output của nó không ở dạng “tìm lời giải”, không chứa bất kỳ thông tin gì để có thể “encode” các bài toán khác trong cùng lớp complexity. Chắc chắn là không có cái reduction nào từ FACTORING hay là SAT/FSAT đến “bài toán in”. Nếu thay “bài toán in” của bạn bằng bài toán in ra
con số 0, thì bạn sẽ thấy là nó không có “thông tin” gì để encode các bài toán khác.
Anh Hưng ơi em hỏi thêm tí nữa,
Như cái link này
http://britton.disted.camosun.bc.ca/jbhanoi.htm
nó chỉ ra: ánh xạ 1-1 giữa mỗi bước chuyển đĩa trong lời giải của bài toán tháp Hanoi n đĩa VÀ xâu nhị phân n bit và thấy rằng: dãy các bước chuyển đĩa trong bài toán tháp Hà nội là tương đương với dãy 2^n -1 xâu nhị phân n bit được liệt kê từ nhỏ đến lớn.
Như vậy có thể coi bài toán tháp Hà Nội tương đương với bài toán in xâu nhị phân n bit ở trên (mà anh gọi là “bài toán in”.) Nếu em muốn cải tiến bài toán tháp Hà Nội thì chỉ cần cải tiến bài toán in này là được chứ ?
Nhưng em có cảm giác 2 bài toán này không tương đương nhau nhất là khi anh nói ở trên là “bài toán in không phải là bài toán ở dạng “tìm lời giải”". Anh có thể nói rõ hơn cho em được không.
Anh có lời khuyên gì về việc nghiên cứu không anh.
@Thang,
Ánh xạ 1-1 tồn tại không có nghĩa là “in ra” các bước của lời giải tối ưu bài THN cần đến
bits. Mỗi “move” mình chỉ cần biết chuyển đĩa từ cọc nào sang cọc nào, do đó chỉ cân 
bits để mã hóa 
moves.
Nhưng Thang nói đúng là bài toán in ra lời giải tối ưu của bài toán THH tương đương với một “bài toán in” kiểu tương tự như bài trên (dù không cần in đến
bits). Tuy nhiên, đây là lời giải tối ưu (up to polymorphisms) cho bài THH, nên cả 2 bài toán (THH và in) đều không cải tiến được nữa.
Ý tôi nói bài toán “tìm lời giải” là loại bài toán sau đây: cho một kích thước input nhất định, ít nhất là tập các “instances” của bài toán phải thật lớn trong đó có nhiều loại instances khác nhau (ví dụ như với
biến và 
clauses thì có cực kỳ nhiều instances của bài 3SAT). Khi đó việc giải quyết xem một instance có thỏa mãn tính chất gì không mới có khả năng chứa nhiều thông tin về cái “không gian instance” đó và vì thế mới chứa thông tin để mã hóa cấu trúc của một bài toán khác. (Và do đó có thể quy chuyển bài toán khác về nó, và do đó mới có cơ hội là bài toán “complete”)
Bài toán THH hay bài toán in chỉ có 1 instance cho mỗi tham số.
Về nghiên cứu thì nên nghiên cứu những gì mình thích và thấy nó thật sự quan trọng. Đừng nghiên cứu chỉ vì mình có thể viết bài báo được nhận.
anh Hung da~ doc cai’ chung’ minh PNP chua:
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf
cai’ do’ theo anh co’ dung’ ko?
Chào Vinh, tôi chưa đọc chứng minh đó. Bạn có thể theo dõi phát triển của sự kiện này ở đây. Đến nay thì có vẻ chứng minh đó đang bị lỗi, chưa hoàn tất. Nhiều khả năng là sai.
Ngày xưa hồi học toán rời rạc em cũng có làm một chứng minh cho sự tương đồng giữa bài toán tháp Hà Nội và mã Gray bằng một ánh xạ 1-1 thì phải.
Ủa, mà cái này ko delete comment được ạ, giờ em mới thấy cái nút reply @_@
Em đang định cải tiến bài toán in ra lời giải tối ưu bài toán THN bằng cách deal with bài toán tương đương là bài toán in các xâu n bit theo thứ tự từ 00…00 đến 11…11 nhưng anh lại viết:
“…nên cả 2 bài toán (THN và in) đều không cải tiến được nữa”
Với bài toán in ra lời giải THN thì hiện nay với mỗi bước mới in ra được 1 bước chuyển đĩa nhưng vẫn hi vọng có thể in được f(n) bước để cải tiến. Câu trên của anh nghĩa là f(n) > 1 là không tưởng.
Tương tự như vậy, bài toán in xâu vẫn còn hi vọng chứ anh.
Nếu quả thực 2 bài này không cải tiến được nữa thì em dừng.
Hi Thang,
Mỗi bước in ra f(n) là thay đổi mô hình tính toán. Cái cải tiến đó không phải là cải tiến thuật toán. Tôi nghĩ Thang không nên nghĩ tiếp về việc cải tiến BTI nữa, trừ phi nó có giá trị thực tiễn gì sâu xa gì đó.
Printing all n-length string of bit 0|1 is trivial. Although the printing has time complexity is 2^n. A NP-complete problem requires more than time complexity. A sample NP-complete is parallel job scheduling problem on n processors (n > 2), duration time of each job is not equal. Objective function is minimize of makespan (all job are completed). In the scheduling problem, there are not exist any algorithm to make a schedule for these parallel jobs on n processors in limited time.