text:
Lý thuyết độ phức tạp tính toán
Lý thuyết độ phức tạp tính toán là một nhánh của lý thuyết tính toán trong lý thuyết khoa học máy tính và toán học tập trung vào phân loại các vấn đề tính toán theo độ khó nội tại của chúng. Ở đây, một vấn đề tính toán được hiểu là một vấn đề có thể giải được bằng máy tính (nói chung có nghĩa là vấn đề có thể được diễn đạt dưới dạng toán học). Một vấn đề tính toán có thể hiểu là một tập các trường hợp và lời giải cho các trường hợp đó. Ví dụ như kiểm tra tính nguyên tố là vấn đề xác định xem một số cho trước có phải số nguyên tố hay không. Mỗi trường hợp của vấn đề là một số tự nhiên, và lời giải cho mỗi trường hợp là có hoặc không tùy theo số đó có là nguyên tố hay không.
Một vấn đề được coi là khó nếu lời giải của nó đòi hỏi nhiều tài nguyên, bất kể sử dụng thuật toán nào. Lý thuyết độ phức tạp tính toán chuyển ý tưởng trực quan này thành mệnh đề toán học chặt chẽ, bằng cách đưa ra các mô hình tính toán để nghiên cứu các vấn đề này và tính lượng tài nguyên cần thiết để giải quyết chúng, chẳng hạn như thời gian hay bộ nhớ. Ngoài ra còn có những tài nguyên khác cũng được sử dụng, chẳng hạn như lượng thông tin liên lạc (dùng trong độ phức tạp truyền thông), số lượng cổng logic trong mạch (dùng trong độ phức tạp mạch) và số lượng bộ xử lý (dùng trong tính toán song song). Một trong những nhiệm vụ của lý thuyết độ phức tạp tính toán là xác định các giới hạn của những gì máy tính có thể làm và không thể làm.
Hai ngành khác trong lý thuyết khoa học máy tính có liên hệ chặt chẽ với độ phức tạp tính toán là phân tích thuật toán và lý thuyết khả tính. Điểm khác biệt mấu chốt giữa phân tích thuật toán và lý thuyết độ phức tạp tính toán là ngành thứ nhất tập trung vào phân tích lượng tài nguyên cần thiết cho một thuật toán nhất định, trong khi ngành thứ hai nghiên cứu các câu hỏi về tất cả các thuật toán có thể dùng để giải quyết vấn đề. Cụ thể hơn, nó tìm cách phân loại các vấn đề theo lượng tài nguyên cần thiết để giải quyết chúng. Việc giới hạn lượng tài nguyên là điểm khác biệt giữa độ phức tạp tính toán và lý thuyết khả tính: lý thuyết khả tính nghiên cứu xem những vấn đề nào có thể giải được về mặt nguyên tắc, mà không giới hạn tài nguyên.
Mục lục
- 1 Vấn đề (bài toán) tính toán
- 2 Các mô hình tính toán và các thông số độ phức tạp
- 3 Các lớp độ phức tạp
- 4 Các bài toán mở quan trọng
- 5 Lịch sử
- 6 Ghi chú
Vấn đề (bài toán) tính toán[sửa | sửa mã nguồn]
Trường hợp[sửa | sửa mã nguồn]
Một vấn đề tính toán có thể xem là một tập vô hạn các trường hợp cùng với lời giải cho mỗi trường hợp. Không nên nhầm lẫn giữa dữ liệu vào cho mỗi vấn đề tính toán, còn gọi là một trường hợp, và bản thân vấn đề. Trong lý thuyết độ phức tạp tính toán, một vấn đề là một câu hỏi trừu tượng cần giải quyết. Một trường hợp là một trường hợp cụ thể của câu hỏi trừu tượng đó. Để rõ hơn, ta xem xét vấn đề kiểm tra tính nguyên tố. Một trường hợp là một số nguyên (ví dụ như 15) và lời giải là "có" nếu như số đó là nguyên tố và "không" nếu nó không là nguyên tố (trong trường hợp này, lời giải là "không").
Biểu diễn trường hợp[sửa | sửa mã nguồn]
Khi xem xét các vấn đề tính toán, một trường hợp là một xâu kí tự trong một bảng chữ cái nhất định. Bảng chữ cái thường dùng là bảng chữ cái nhị phân (gồm 2 kí tự 0 và 1). Cũng như trong máy tính trên thực tế, các đối tượng toán học cần phải được mã hóa hợp lý dưới dạng các dãy bit. Ví dụ như một số nguyên cần phải được biểu diễn dưới dạng nhị phân, đồ thị có thể được biểu diễn dưới dạng ma trận kề, hoặc mã hóa danh sách kề dưới dạng nhị phân.
Mặc dù một số chứng minh của các định lý trong lý thuyết độ phức tạp tính toán giả sử một mã hóa nhất định của dữ liệu vào, người ta thường cố gắng giữ cho các lập luận đủ trừu tượng để không phụ thuộc vào cách mã hóa. Điều này có thể đạt được bằng cách đảm bảo có thể được chuyển từ cách mã hóa này sang cách mã hóa khác một cách hiệu quả.
Bài toán quyết định dưới dạng ngôn ngữ hình thức[sửa | sửa mã nguồn]
Bài toán quyết định là một trong những đối tượng trọng tâm nghiên cứu của lý thuyết độ phức tạp tính toán. Một bài toán quyết định là một trường hợp đặc biệt của bài toán tính toán, với câu trả lời là có hoặc không, hay nói cách khác là 0 hoặc 1. Một bài toán quyết định có thể được xem là một ngôn ngữ hình thức, trong đó các xâu kí tự thành viên của ngôn ngữ là các những trường hợp có câu trả lời là có, các xâu kí tự không là thành viên là những trường hợp có câu trả lời là không. Mục tiêu của bài toán là sử dụng một thuật toán để quyết định xem một xâu cho trước có là thành viên của ngôn ngữ hình thức đang xem xét hay không. Nếu thuật toán quyết định là có, thì ta nói thuật toán chấp nhận xâu dữ liệu vào, nếu không thì ta nói thuật toán từ chối xâu dữ liệu vào.
Một ví dụ của bài toán quyết định là như sau. Dữ liệu vào là một đồ thị bất kì. Bài toán yêu cầu quyết định xem đồ thị có liên thông hay không. Ngôn ngữ hình thức tương ứng cho bài toán này là tập tất cả các đồ thị liên thông. Dĩ nhiên để định nghĩa chặt chẽ bài toán, cần phải quyết định xem đồ thị được mã hóa như thế nào dưới dạng xâu nhị phân.
Bài toán hàm[sửa | sửa mã nguồn]
Một bài toán hàm là một bài toán tính toán trong đó mỗi dữ liệu vào cho đúng một kết quả, nhưng kết quả đó phức tạp hơn kết quả của bài toán quyết định, nghĩa là nó không chỉ là có hay không. Ví dụ như bài toán người bán hàng, và bài toán phân tích ra thừa số nguyên tố.
Thoạt nhìn có vẻ khái niệm bài toán hàm là rộng hơn khái niệm bài toán tính toán. Tuy nhiên, điều này không hẳn là đúng do các bài toán hàm có thể được viết lại dưới dạng bài toán quyết định. Ví dụ như bài toán nhân hai số nguyên có thể được biểu diễn dưới dạng tập hợp các bộ ba (a, b, c) sao cho a × b < c. Quyết định xem liệu một bộ ba cho trước có phải là thành viên của tập hợp đó hay không tương ứng với việc nhân hai số.
Kích thước của trường hợp[sửa | sửa mã nguồn]
Để đánh giá độ khó của một bài toán tính toán, một thước đo phổ biến là lượng thời gian thuật toán tốt nhất cần dùng để giải nó. Tuy nhiên, thời gian cần thiết nói chung phụ thuộc vào từng trường hợp cụ thể. Trường hợp lớn hơn thường đòi hỏi nhiều thời gian hơn. Do đó thời gian cần thiết để giải quyết bài toán (hoặc bộ nhớ, hay bất kì một thông số độ phức tạp nào) là một hàm số của kích thước trường hợp. Kích thước thường được đo bằng kích thước dữ liệu vào với đơn vị bit. Lý thuyết độ phức tạp quan tâm đến hành vi của thuật toán khi kích thước dữ liệu vào tăng lên. Ví dụ như trong bài toán kiểm tra xem một đồ thị có liên thông hay không, thời gian cần thiết để kiểm tra một đồ thị kích thước 2n là bao nhiêu so với thời gian để kiểm tra đồ thị kích thước n?
Khi kích thước dữ liệu vào là n, thời gian có thể được biểu diễn dưới dạng một hàm số của n. Do thời gian cần thiết cho các trường hợp cùng kích thước có thể khác nhau, thời gian trong trường hợp xấu nhất T(n) được định nghĩa là lượng thời gian lớn nhất trong tất cả các trường hợp có kích thước n. Nếu T(n) là đa thức của n, thì ta nói thuật toán chạy thời gian đa thức.
Các mô hình tính toán và các thông số độ phức tạp[sửa | sửa mã nguồn]
Máy Turing[sửa | sửa mã nguồn]
Máy Turing là một mô hình toán học cho một máy tính tổng quát. Nó là một thiết bị lý thuyết thao tác trên các kí hiệu nằm trên một dải băng. Máy Turing không nhằm thiết kế thiết bị tính toán trên thực tế, mà chỉ là một thiết bị trừu tượng đại diện cho máy tính. Người ta tin rằng nếu một vấn đề có thể được giải quyết bởi một thuật toán, thì cũng có một máy Turing giải quyết vấn đề đó. Tất cả các mô hình tính toán hiện nay chẳng hạn như máy RAM, Trò chơi cuộc sống của Conway, automat tế bào, hay bất kì ngôn ngữ lập trình nào cũng đều có thể tính được trên máy Turing. Do máy Turing phù hợp cho việc nghiên cứu bằng toán học, và được xem là mạnh ngang bất kì mô hình tính toán nào, máy Turing là mô hình tính toán phổ biến nhất trong lý thuyết độ phức tạp tính toán.
Các mô hình khác[sửa | sửa mã nguồn]
Có nhiều mô hình khác ngoài mô hình chuẩn máy Turing nhiều băng đã được nghiên cứu, chẳng hạn như máy truy cập ngẫu nhiên. Tất cả các mô hình này đều có thể được chuyển hóa lẫn nhau mà không cần thêm khả năng tính toán đặc biệt nào. Tuy vậy, thời gian và bộ nhớ của các mô hình khác nhau có thể khác nhau.[1].
Các thông số độ phức tạp[sửa | sửa mã nguồn]
Để định nghĩa cụ thể thời gian và bộ nhớ cần thiết để giải quyết một vấn đề, cần định rõ một mô hình tính toán cụ thể, chẳng hạn như máy Turing tất định. Thời gian cần thiết cho một máy Turing M giải quyết dữ liệu vào x là số lượng lần chuyển trạng thái, hay số bước, của máy trước khi máy ngừng và thông báo kết quả ("có" hoặc "không"). Một máy Turing chạy trong thời gian f(n) nếu thời gian máy sử dụng cho tất cả các dữ liệu vào kích thước n là không quá f(n). Có thể định nghĩa lượng bộ nhớ cần thiết một cách tương tự như vậy. Mặc dù thời gian và bộ nhớ là hai thông số phổ biến nhất, nhiều thông số phức tạp khác cũng có thể xem là tài nguyên tính toán. Các thông số độ phức tạp được định nghĩa tổng quát bởi các tiên đề độ phức tạp Blum. Một vài thông số độ phức tạp khác được dùng trong lý thuyết độ phức tạp bao gồm độ phức tạp truyền thông, độ phức tạp mạch, và độ phức tạp cây quyết định.
Các lớp độ phức tạp[sửa | sửa mã nguồn]
Định nghĩa lớp độ phức tạp[sửa | sửa mã nguồn]
Một lớp độ phức tạp là một tập hợp các vấn đề có độ phức tạp tương tự nhau. Các lớp độ phức tạp thường được định nghĩa theo các yếu tố sau:
- Thể loại vấn đề: thể loại phổ biến nhất là bài toán quyết định. Ngoài ra còn có bài toán hàm, bài toán đếm, bài toán tối ưu, bài toán có lời hứa, v.v.
- Mô hình tính toán: mô hình phổ biến nhất là máy Turing tất định. Ngoài ra còn có máy Turing bất định, mạch Boole, máy Turing lượng tử, mạch đơn điệu, v.v.
- Loại tài nguyên bị giới hạn và giới hạn cụ thể: chẳng hạn như "thời gian đa thức", "bộ nhớ lôgarit", v.v.
Các lớp độ phức tạp quan trọng[sửa | sửa mã nguồn]
Theo định lý Savitch, PSPACE = NPSPACE và EXPSPACE = NEXPSPACE.
Một số lớp độ phức tạp quan trọng khác bao gồm BPP, ZPP, RP là các lớp định nghĩa trên máy Turing ngẫu nhiên, AC và NC là các lớp định nghĩa trên mạch logic Boole, và BQP và QMA là các lớp định nghĩa trên máy Turing lượng tử. #P là một lớp độ phức tạp quan trọng cho các bài toán đếm. Các lớp như IP và AM được định nghĩa thông qua hệ thống chứng minh tương tác. ALL là lớp tất cả các bài toán quyết định.
Các định lý cấp bậc[sửa | sửa mã nguồn]
Với các lớp độ phức tạp định nghĩa như trên, một vấn đề đáng quan tâm là liệu với nhiều tài nguyên hơn, chẳng hạn như nhiều thời gian hơn, tập hợp các bài toán giải được có nhiều lên hay không. Cụ thể hơn, mặc dù DTIME(n) rõ ràng là tập hợp con của DTIME(n2), một câu hỏi lý thú là liệu mối quan hệ tập hợp con có chặt hay không. Với thời gian và bộ nhớ, câu hỏi trên được trả lời bởi các định lý cấp bậc thời gian và bộ nhớ. Cụ thể hơn, định lý cấp bậc thời gian là
- .
- .
Các định lý cấp bậc thời gian và bộ nhớ là cơ sở cho hầu hết các kết quả phân tách các lớp độ phức tạp. Ví dụ như định lý cấp bậc thời gian cho ta thấy P là tập hợp con chặt của EXPTIME, và định lý cấp bậc bộ nhớ cho ta thấy L là tập con chặt của PSPACE.
Quy về[sửa | sửa mã nguồn]
Nhiều lớp độ phức tạp được định nghĩa thông qua khái niệm phép quy về. Một phép quy về là một biến đổi từ một bài toán này thành một bài toán khác. Nó thâu tóm khái niệm trực giác một bài toán ít nhất là khó bằng một bài toán khác. Nếu một bài toán X có thể được giải bằng thuật toán cho bài toán Y thì X không khó hơn Y, và ta nói X quy về Y. Có nhiều kiểu quy về khác nhau, tùy theo phương pháp quy về, chẳng hạn như phép quy về Cook, phép quy về Karp, phép quy về Levin, và tùy theo độ phức tạp của phép quy về, chẳng hạn như quy về trong thời gian đa thức, hoặc quy về trong bộ nhớ lôgarit.
Phép quy về phổ biến nhất là quy về trong thời gian đa thức. Điều này có nghĩa là thuật toán quy về chạy trong thời gian đa thức. Ví dụ như bài toán tính bình phương của một số nguyên có thể được quy về bài toán nhân hai số nguyên. Có nghĩa là thuật toán nhân hai số nguyên có thể dùng để tính bình phương một số bằng cách dùng số nguyên cần tính bình phương làm cả hai thừa số cho thuật toán nhân số. Do đó, tính bình phương không khó hơn phép nhân, bởi vì tính bình phương có thể quy về phép nhân.
Định nghĩa trên dẫn tới khái niệm khó cho một lớp độ phức tạp. Một bài toán X là khó cho lớp bài toán C nếu mọi bài toán trong C có thể quy về X. Khi đó, không có bài toán nào trong C là khó hơn X do một thuật toán cho X có thể giải bất kì bài toán nào trong C. Dĩ nhiên khái niệm bài toán khó tùy thuộc vào loại quy về được sử dụng. Cho các lớp độ phức tạp lớn hơn P, quy về trong thời gian đa thức thường được sử dụng. Ví dụ như tập hợp các bài toán khó cho NP là tập hợp các bài toán NP-khó.
Nếu bài toán X nằm trong C và là khó cho C, thì X là đầy đủ cho C. Điều này có nghĩa là X là bài toán khó nhất trong C. (Do có thể có nhiều bài toán cùng độ khó, có thể nói là X là một trong những bài toán khó nhất trong C). Do vậy, lớp NP-đầy đủ chứa những bài toán khó nhất trong NP, theo nghĩa chúng là những bài toán có nhiều khả năng nhất không giải được trong P. Do bài toán P = NP vẫn chưa được giải, nếu có thể quy một bài toán NP-đầy đủ, Π2 về bài toán Π1 thì chưa có thuật toán thời gian đa thức nào cho Π1. Bởi vì nếu có thuật toán thời gian đa thức cho Π1 thì cũng có thuật toán thời gian đa thức cho Π2. Tương tự như vậy, do mọi bài toán trong NP đều có thể quy về các bài toán NP-đầy đủ, nếu có thể giải được một bài toán NP-đầy đủ trong thời gian đa thức thì P = NP.[2]
Các bài toán mở quan trọng[sửa | sửa mã nguồn]
Bài toán P so với NP[sửa | sửa mã nguồn]
Lớp độ phức tạp P thường được xem là mô hình toán học cho các vấn đề tính toán có thuật toán hiệu quả. Giả thuyết này được gọi là luận đề Cobham-Edmonds. Trong khi đó lớp độ phức tạp NP chứa nhiều bài toán quan trọng cần được giải quyết hiệu quả, nhưng vẫn chưa có thuật toán hiệu quả nào, chẳng hạn như bài toán thỏa mãn biểu thức logic, bài toán đường đi Hamilton, và bài toán phủ đỉnh. Do máy Turing đơn định là trường hợp đặc biệt của máy Turing không đơn định, có thể dễ dàng nhận thấy mọi bài toán trong P đều nằm trong NP.
Câu hỏi liệu P có bằng NP hay không là một trong những câu hỏi quan trọng nhất trong lý thuyết khoa học máy tính do tính áp dụng rộng rãi của lời giải.[2] Nếu câu trả lời là có, thì nhiều bài toán quan trọng có thể được giải quyết hiệu quả. Những bài toán này bao gồm nhiều loại quy hoạch nguyên trong vận trù học, nhiều vấn đề trong hậu cần, dự đoán cấu trúc protein trong sinh học,[3] và khả năm tìm chứng minh chặt chẽ cho các định lý toán học.[4] Bài toán P so với NP là một trong những bài toán giải thưởng thiên niên kỷ lựa chọn bởi viện toán học Clay. Có một giải thưởng US$1.000.000 cho việc giải quyết bài toán.[5]
Bài toán trong NP không nằm trong P và không là NP-đầy đủ[sửa | sửa mã nguồn]
Ladner đã chứng minh rằng nếu P ≠ NP thì tồn tại bài toán trong NP không nằm trong P cũng như không là NP-đầy đủ.[6] Các bài toán như vậy gọi là bài toán NP-trung bình. Bài toán đồ thị đẳng cấu, bài toán tính lôga rời rạc, và bài toán phân tích ra thừa số nguyên tố là các ví dụ của những bài toán được tin là NP-trung bình. Chúng nằm trong số rất ít bài toán trong NP không biết có nằm trong P và cũng không biết có là NP-đầy đủ.
Phân biệt giữa các lớp độ phức tạp khác[sửa | sửa mã nguồn]
Có nhiều lớp độ phức tạp được tin là khác nhau những vẫn chưa được chứng minh. Ví dụ như P ⊆ NP ⊆ PP ⊆ PSPACE và hoàn toàn có thể P=PSPACE. Nếu P không bằng NP thì P không bằng PSPACE. Do có rất nhiều lớp độ phức tạp giữa P và PSPACE, chẳng hạn như RP, BPP, PP, BQP, MA, PH, v.v., hoàn toàn có thể là tất cả các lớp này đều bằng nhau. Chứng minh bất kì hai lớp nào trong số đó là khác nhau sẽ là một bước tiến lớn trong lý thuyết độ phức tạp.
Tương tự như vậy, co-NP là lớp chứa các bài toán phần bù (các bài toán với câu trả lời có/không đảo ngược) của các bài toán trong NP. Người ta tin rằng [7] NP không bằng co-NP, nhưng điều này vẫn chưa được chứng minh. Nếu hai lớp này không bằng nhau thì P cũng không bằng NP.
Tương tự như vậy, vẫn chưa biết liệu L (tập hợp các bài toán giải được trong bộ nhớ lôgarit) có bằng P hay không. Có nhiều lớp độ phức tạp nằm giữa hai lớp, chẳng hạn như NL và NC, và vẫn chưa biết liệu chúng bằng nhau hay khác nhau.
P và BPP có nhiều khả năng là bằng nhau. Tuy nhiên hiện vẫn chưa biết liệu BPP có bằng NEXP.
Lịch sử[sửa | sửa mã nguồn]
Trước khi có các nghiên cứu chuyên về độ phức tạp tính toán của các thuật toán, nhiều vấn đề cơ sở đã được các nhà nghiên cứu tìm hiểu. Có ảnh hưởng lớn nhất là định nghĩa máy Turing của Alan Turing năm 1936, một định nghĩa rất vững chắc và linh hoạt cho máy tính.
Theo Fortnow & Homer (2003), việc nghiên cứu có hệ thống độ phức tạp tính toán bắt đầu từ bài báo quan trọng mang tên "On the Computational Complexity of Algorithms" của Juris Hartmanis và Richard Stearns (1965). Bài báo này đã đưa ra định nghĩa của độ phức tạp thời gian và bộ nhớ và chứng minh các định lý cấp bậc.
Theo Fortnow & Homer (2003), các bài báo đầu tiên nghiên cứu các bài toán giải được bằng máy Turing với giới hạn tài nguyên bao gồm định nghĩa của John Myhill cho automat giới hạn tuyến tính (Myhill 1960), nghiên cứu của Raymond Smullyan về các tập hợp thô sơ (1961), bài báo của Hisao Yamada về tính toán thời gian thực (1962).[8] Trước đó, Boris Trakhtenbrot (1956), một nhà nghiên cứu tiên phong trong ngành ở Liên Xô, cũng đã nghiên cứu một thông số độ phức tạp khác.[9]
Năm 1967, Manuel Blum đã xây dựng các tiên đề cho lý thuyết độ phức tạp và chứng minh một kết quả quan trọng, nay gọi là định lý tăng tốc. Lý thuyết độ phức tạp bắt đầu phát triển mạnh sau khi nhà nghiên cứu Mỹ Stephen Cook và, một cách độc lập, nhà nghiên cứu Liên Xô Leonid Levin, chứng minh rằng tồn tại bài toán có liên hệ thực tế là NP-đầy đủ. Năm 1972, Richard Karp đã đưa ra một bước tiến lớn với bài báo "Reducibility Among Combinatorial Problems", trong đó ông chứng minh 21 bài toán rất khác nhau trong tổ hợp và lý thuyết đồ thị, tất cả đều rất nổi bật về độ khó, là NP-đầy đủ.[10]
Ghi chú[sửa | sửa mã nguồn]
- ^ Xem Arora & Barak 2009, Chương 1: The computational model and why it doesn't matter
- ^ a ă Xem Sipser 2006, Chương 7: Time complexity
- ^ Berger, Bonnie A.; Leighton, T (1998), “Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete”, Journal of Computational Biology 5 (1): p27–40, doi:10.1089/cmb.1998.5.27, PMID 9541869. Đã định rõ hơn một tham số trong
|number=và
|issue=(trợ giúp)
- ^ Cook, Stephen (April năm 2000), The P versus NP Problem, Clay Mathematics Institute, truy cập ngày 18 tháng 10 năm 2006.
- ^ Jaffe, Arthur M. (2006), “The Millennium Grand Challenge in Mathematics”, Notices of the AMS 53 (6), truy cập ngày 18 tháng 10 năm 2006.
- ^ Ladner, Richard E. (1975), “On the structure of polynomial time reducibility” (PDF), Journal of the ACM (JACM) 22 (1): 151–171, doi:10.1145/321864.321877.
- ^ Khóa học của Boaz Barak về lý thuyết độ phức tạp tính toán Bài giảng thứ 2
- ^ Yamada, H. (1962). “Real-Time Computation and Recursive Functions Not Real-Time Computable”. IEEE Transactions on Electronic Computers. EC-11 (6): 753–760. doi:10.1109/TEC.1962.5219459.
- ^ Trakhtenbrot, B.A.: Signalizing functions and tabular operators. Uchionnye Zapiski Penzenskogo Pedinstituta (Transactions of the Penza Pedagogoical Institute) 4, 75–87 (1956) (tiếng Nga)
- ^ Richard M. Karp (1972), “Reducibility Among Combinatorial Problems”, trong R. E. Miller and J. W. Thatcher (editors), Complexity of Computer Computations, New York: Plenum, tr. 85–103
Sách tham khảo[sửa | sửa mã nguồn]
- Sanjeev Arora, Boaz Barak, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4 Đã định rõ hơn một tham số trong
|last1=và
|author=(trợ giúp)
- Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity, John Wiley & Sons, ISBN 978-0-471-34506-0 Đã bỏ qua tham số không rõ
|country=(trợ giúp)
- Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press
- van Leeuwen, Jan biên tập (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, ISBN 978-0-444-88071-0
- Papadimitriou, Christos (1994), Computational Complexity (ấn bản 1), Addison Wesley, ISBN 0201530821
- Sipser, Michael (2006), Introduction to the Theory of Computation (ấn bản 2), USA: Thomson Course Technology, ISBN 0534950973
Bài báo tổng quan[sửa | sửa mã nguồn]
- Khalil, Hatem; Ulery, Dana (1976), A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations, ACM '76 Proceedings of the 1976 Annual Conference, tr. 197, doi:10.1145/800191.805573
- Cook, Stephen (1983), “An overview of computational complexity”, Commun. ACM (ACM) 26 (6): 400–408, doi:10.1145/358141.358144, ISSN 0001-0782
- Fortnow, Lance; Homer, Steven (2003), “A Short History of Computational Complexity”, Bulletin of the EATCS 80: 95–133
- Mertens, Stephan (2002), “Computational Complexity for Physicists”, Computing in Science and Engg. (Piscataway, NJ, USA: IEEE Educational Activities Department) 4 (3): 31–47, arXiv:cond-mat/0012185, doi:10.1109/5992.998639, ISSN 1521-9615 Đã bỏ qua tham số không rõ
|unused_data=(trợ giúp)

markdown:
# Lý thuyết độ phức tạp tính toán
**Lý thuyết độ phức tạp tính toán** là một nhánh của [lý thuyết tính toán](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_t%C3%ADnh_to%C3%A1n&action=edit&redlink=1) trong [lý thuyết khoa học máy tính](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_khoa_h%E1%BB%8Dc_m%C3%A1y_t%C3%ADnh&action=edit&redlink=1) và [toán học](/wiki/To%C3%A1n_h%E1%BB%8Dc) tập trung vào phân loại các vấn đề tính toán theo độ khó nội tại của chúng. Ở đây, một vấn đề tính toán được hiểu là một vấn đề có thể giải được bằng máy tính (nói chung có nghĩa là vấn đề có thể được diễn đạt dưới dạng toán học). Một vấn đề tính toán có thể hiểu là một tập các trường hợp và lời giải cho các trường hợp đó. Ví dụ như [kiểm tra tính nguyên tố](/wiki/Ki%E1%BB%83m_tra_t%C3%ADnh_nguy%C3%AAn_t%E1%BB%91) là vấn đề xác định xem một số cho trước có phải số nguyên tố hay không. Mỗi trường hợp của vấn đề là một số tự nhiên, và lời giải cho mỗi trường hợp là *có* hoặc *không* tùy theo số đó có là nguyên tố hay không.
Một vấn đề được coi là khó nếu lời giải của nó đòi hỏi nhiều tài nguyên, bất kể sử dụng thuật toán nào. Lý thuyết độ phức tạp tính toán chuyển ý tưởng trực quan này thành mệnh đề toán học chặt chẽ, bằng cách đưa ra các
[mô hình tính toán](/w/index.php?title=M%C3%B4_h%C3%ACnh_t%C3%ADnh_to%C3%A1n&action=edit&redlink=1) để nghiên cứu các vấn đề này và tính lượng tài nguyên cần thiết để giải quyết chúng, chẳng hạn như thời gian hay bộ nhớ. Ngoài ra còn có những tài nguyên khác cũng được sử dụng, chẳng hạn như lượng thông tin liên lạc (dùng trong [độ phức tạp truyền thông](/wiki/%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng)), số lượng [cổng logic](/w/index.php?title=C%E1%BB%95ng_logic&action=edit&redlink=1) trong mạch (dùng trong [độ phức tạp mạch](/w/index.php?title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_m%E1%BA%A1ch&action=edit&redlink=1)) và số lượng bộ xử lý (dùng trong [tính toán song song](/wiki/T%C3%ADnh_to%C3%A1n_song_song)). Một trong những nhiệm vụ của lý thuyết độ phức tạp tính toán là xác định các giới hạn của những gì [máy tính](/wiki/M%C3%A1y_t%C3%ADnh) có thể làm và không thể làm.
Hai ngành khác trong lý thuyết khoa học máy tính có liên hệ chặt chẽ với độ phức tạp tính toán là
[phân tích thuật toán](/w/index.php?title=Ph%C3%A2n_t%C3%ADch_thu%E1%BA%ADt_to%C3%A1n&action=edit&redlink=1) và [lý thuyết khả tính](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_kh%E1%BA%A3_t%C3%ADnh&action=edit&redlink=1). Điểm khác biệt mấu chốt giữa phân tích thuật toán và lý thuyết độ phức tạp tính toán là ngành thứ nhất tập trung vào phân tích lượng tài nguyên cần thiết cho một thuật toán nhất định, trong khi ngành thứ hai nghiên cứu các câu hỏi về tất cả các thuật toán có thể dùng để giải quyết vấn đề. Cụ thể hơn, nó tìm cách phân loại các vấn đề theo lượng tài nguyên cần thiết để giải quyết chúng. Việc giới hạn lượng tài nguyên là điểm khác biệt giữa độ phức tạp tính toán và lý thuyết khả tính: lý thuyết khả tính nghiên cứu xem những vấn đề nào có thể giải được về mặt nguyên tắc, mà không giới hạn tài nguyên.
## Mục lục
[1 Vấn đề (bài toán) tính toán](#V.E1.BA.A5n_.C4.91.E1.BB.81_.28b.C3.A0i_to.C3.A1n.29_t.C3.ADnh_to.C3.A1n) [2 Các mô hình tính toán và các thông số độ phức tạp](#C.C3.A1c_m.C3.B4_h.C3.ACnh_t.C3.ADnh_to.C3.A1n_v.C3.A0_c.C3.A1c_th.C3.B4ng_s.E1.BB.91_.C4.91.E1.BB.99_ph.E1.BB.A9c_t.E1.BA.A1p) [3 Các lớp độ phức tạp](#C.C3.A1c_l.E1.BB.9Bp_.C4.91.E1.BB.99_ph.E1.BB.A9c_t.E1.BA.A1p) [4 Các bài toán mở quan trọng](#C.C3.A1c_b.C3.A0i_to.C3.A1n_m.E1.BB.9F_quan_tr.E1.BB.8Dng) [5 Lịch sử](#L.E1.BB.8Bch_s.E1.BB.AD) [6 Ghi chú](#Ghi_ch.C3.BA)
## Vấn đề (bài toán) tính toán[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=1)]
### Trường hợp[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=2)]
Một vấn đề tính toán có thể xem là một tập vô hạn các
*trường hợp* cùng với *lời giải* cho mỗi trường hợp. Không nên nhầm lẫn giữa dữ liệu vào cho mỗi vấn đề tính toán, còn gọi là một trường hợp, và bản thân vấn đề. Trong lý thuyết độ phức tạp tính toán, một vấn đề là một câu hỏi trừu tượng cần giải quyết. Một trường hợp là một trường hợp cụ thể của câu hỏi trừu tượng đó. Để rõ hơn, ta xem xét vấn đề [kiểm tra tính nguyên tố](/wiki/Ki%E1%BB%83m_tra_t%C3%ADnh_nguy%C3%AAn_t%E1%BB%91). Một trường hợp là một số nguyên (ví dụ như 15) và lời giải là "có" nếu như số đó là nguyên tố và "không" nếu nó không là nguyên tố (trong trường hợp này, lời giải là "không").
### Biểu diễn trường hợp[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=3) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=3)]
Khi xem xét các vấn đề tính toán, một trường hợp là một
[xâu kí tự](/w/index.php?title=X%C3%A2u_k%C3%AD_t%E1%BB%B1&action=edit&redlink=1) trong một [bảng chữ cái](/wiki/B%E1%BA%A3ng_ch%E1%BB%AF_c%C3%A1i) nhất định. Bảng chữ cái thường dùng là bảng chữ cái nhị phân (gồm 2 kí tự 0 và 1). Cũng như trong máy tính trên thực tế, các đối tượng toán học cần phải được mã hóa hợp lý dưới dạng các dãy bit. Ví dụ như một số nguyên cần phải được biểu diễn dưới dạng nhị phân, đồ thị có thể được biểu diễn dưới dạng ma trận kề, hoặc mã hóa danh sách kề dưới dạng nhị phân.
Mặc dù một số chứng minh của các định lý trong lý thuyết độ phức tạp tính toán giả sử một mã hóa nhất định của dữ liệu vào, người ta thường cố gắng giữ cho các lập luận đủ trừu tượng để không phụ thuộc vào cách mã hóa. Điều này có thể đạt được bằng cách đảm bảo có thể được chuyển từ cách mã hóa này sang cách mã hóa khác một cách hiệu quả.
### Bài toán quyết định dưới dạng ngôn ngữ hình thức[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=4) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=4)] [Bài toán quyết định](/w/index.php?title=B%C3%A0i_to%C3%A1n_quy%E1%BA%BFt_%C4%91%E1%BB%8Bnh&action=edit&redlink=1) là một trong những đối tượng trọng tâm nghiên cứu của lý thuyết độ phức tạp tính toán. Một bài toán quyết định là một trường hợp đặc biệt của bài toán tính toán, với câu trả lời là *có* hoặc *không*, hay nói cách khác là 0 hoặc 1. Một bài toán quyết định có thể được xem là một [ngôn ngữ hình thức](/wiki/Ng%C3%B4n_ng%E1%BB%AF_h%C3%ACnh_th%E1%BB%A9c), trong đó các xâu kí tự thành viên của ngôn ngữ là các những trường hợp có câu trả lời là *có*, các xâu kí tự không là thành viên là những trường hợp có câu trả lời là *không*. Mục tiêu của bài toán là sử dụng một [thuật toán](/wiki/Thu%E1%BA%ADt_to%C3%A1n) để quyết định xem một xâu cho trước có là thành viên của ngôn ngữ hình thức đang xem xét hay không. Nếu thuật toán quyết định là *có*, thì ta nói thuật toán chấp nhận xâu dữ liệu vào, nếu không thì ta nói thuật toán từ chối xâu dữ liệu vào.
Một ví dụ của bài toán quyết định là như sau. Dữ liệu vào là một
[đồ thị](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B) bất kì. Bài toán yêu cầu quyết định xem đồ thị có [liên thông](/wiki/T%E1%BA%ADp_h%E1%BB%A3p_li%C3%AAn_th%C3%B4ng) hay không. Ngôn ngữ hình thức tương ứng cho bài toán này là tập tất cả các đồ thị liên thông. Dĩ nhiên để định nghĩa chặt chẽ bài toán, cần phải quyết định xem đồ thị được mã hóa như thế nào dưới dạng xâu nhị phân.
### Bài toán hàm[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=5) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=5)]
Một
[bài toán hàm](/w/index.php?title=B%C3%A0i_to%C3%A1n_h%C3%A0m&action=edit&redlink=1) là một bài toán tính toán trong đó mỗi dữ liệu vào cho đúng một kết quả, nhưng kết quả đó phức tạp hơn kết quả của [bài toán quyết định](/w/index.php?title=B%C3%A0i_to%C3%A1n_quy%E1%BA%BFt_%C4%91%E1%BB%8Bnh&action=edit&redlink=1), nghĩa là nó không chỉ là có hay không. Ví dụ như [bài toán người bán hàng](/wiki/B%C3%A0i_to%C3%A1n_ng%C6%B0%E1%BB%9Di_b%C3%A1n_h%C3%A0ng), và bài toán [phân tích ra thừa số nguyên tố](/w/index.php?title=Ph%C3%A2n_t%C3%ADch_ra_th%E1%BB%ABa_s%E1%BB%91_nguy%C3%AAn_t%E1%BB%91&action=edit&redlink=1).
Thoạt nhìn có vẻ khái niệm bài toán hàm là rộng hơn khái niệm bài toán tính toán. Tuy nhiên, điều này không hẳn là đúng do các bài toán hàm có thể được viết lại dưới dạng bài toán quyết định. Ví dụ như bài toán nhân hai số nguyên có thể được biểu diễn dưới dạng tập hợp các bộ ba
*(a, b, c)* sao cho *a × b < c*. Quyết định xem liệu một bộ ba cho trước có phải là thành viên của tập hợp đó hay không tương ứng với việc nhân hai số.
### Kích thước của trường hợp[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=6) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=6)]
Để đánh giá độ khó của một bài toán tính toán, một thước đo phổ biến là lượng thời gian thuật toán tốt nhất cần dùng để giải nó. Tuy nhiên, thời gian cần thiết nói chung phụ thuộc vào từng trường hợp cụ thể. Trường hợp lớn hơn thường đòi hỏi nhiều thời gian hơn. Do đó thời gian cần thiết để giải quyết bài toán (hoặc bộ nhớ, hay bất kì một thông số độ phức tạp nào) là một hàm số của kích thước trường hợp. Kích thước thường được đo bằng kích thước dữ liệu vào với đơn vị bit. Lý thuyết độ phức tạp quan tâm đến hành vi của thuật toán khi kích thước dữ liệu vào tăng lên. Ví dụ như trong bài toán kiểm tra xem một đồ thị có liên thông hay không, thời gian cần thiết để kiểm tra một đồ thị kích thước
*2n* là bao nhiêu so với thời gian để kiểm tra đồ thị kích thước *n*?
Khi kích thước dữ liệu vào là
*n*, thời gian có thể được biểu diễn dưới dạng một hàm số của *n*. Do thời gian cần thiết cho các trường hợp cùng kích thước có thể khác nhau, thời gian trong trường hợp xấu nhất T( *n*) được định nghĩa là lượng thời gian lớn nhất trong tất cả các trường hợp có kích thước *n*. Nếu T( *n*) là đa thức của *n*, thì ta nói thuật toán chạy thời gian đa thức.
## Các mô hình tính toán và các thông số độ phức tạp[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=7) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=7)]
### Máy Turing[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=8) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=8)]
Máy Turing là một mô hình toán học cho một máy tính tổng quát. Nó là một thiết bị lý thuyết thao tác trên các kí hiệu nằm trên một dải băng. Máy Turing không nhằm thiết kế thiết bị tính toán trên thực tế, mà chỉ là một thiết bị trừu tượng đại diện cho máy tính. Người ta tin rằng nếu một vấn đề có thể được giải quyết bởi một thuật toán, thì cũng có một máy Turing giải quyết vấn đề đó. Tất cả các mô hình tính toán hiện nay chẳng hạn như
[máy RAM](/w/index.php?title=M%C3%A1y_RAM&action=edit&redlink=1), [Trò chơi cuộc sống của Conway](/w/index.php?title=Tr%C3%B2_ch%C6%A1i_cu%E1%BB%99c_s%E1%BB%91ng_c%E1%BB%A7a_Conway&action=edit&redlink=1), [automat tế bào](/w/index.php?title=Automat_t%E1%BA%BF_b%C3%A0o&action=edit&redlink=1), hay bất kì ngôn ngữ lập trình nào cũng đều có thể tính được trên máy Turing. Do máy Turing phù hợp cho việc nghiên cứu bằng toán học, và được xem là mạnh ngang bất kì mô hình tính toán nào, máy Turing là mô hình tính toán phổ biến nhất trong lý thuyết độ phức tạp tính toán.
### Các mô hình khác[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=9) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=9)]
Có nhiều mô hình khác ngoài mô hình chuẩn
[máy Turing nhiều băng](/w/index.php?title=M%C3%A1y_Turing_nhi%E1%BB%81u_b%C4%83ng&action=edit&redlink=1) đã được nghiên cứu, chẳng hạn như [máy truy cập ngẫu nhiên](/w/index.php?title=M%C3%A1y_truy_c%E1%BA%ADp_ng%E1%BA%ABu_nhi%C3%AAn&action=edit&redlink=1). Tất cả các mô hình này đều có thể được chuyển hóa lẫn nhau mà không cần thêm khả năng tính toán đặc biệt nào. Tuy vậy, thời gian và bộ nhớ của các mô hình khác nhau có thể khác nhau. . [1]
### Các thông số độ phức tạp[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=10) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=10)]
Để định nghĩa cụ thể thời gian và bộ nhớ cần thiết để giải quyết một vấn đề, cần định rõ một mô hình tính toán cụ thể, chẳng hạn như
[máy Turing tất định](/w/index.php?title=M%C3%A1y_Turing_t%E1%BA%A5t_%C4%91%E1%BB%8Bnh&action=edit&redlink=1). *Thời gian* cần thiết cho một máy Turing *M* giải quyết dữ liệu vào *x* là số lượng lần chuyển trạng thái, hay số bước, của máy trước khi máy ngừng và thông báo kết quả ("có" hoặc "không"). Một máy Turing chạy trong thời gian *f(n)* nếu thời gian máy sử dụng cho tất cả các dữ liệu vào kích thước *n* là không quá *f(n)*. Có thể định nghĩa lượng bộ nhớ cần thiết một cách tương tự như vậy. Mặc dù thời gian và bộ nhớ là hai thông số phổ biến nhất, nhiều thông số phức tạp khác cũng có thể xem là tài nguyên tính toán. Các thông số độ phức tạp được định nghĩa tổng quát bởi các [tiên đề độ phức tạp Blum](/w/index.php?title=Ti%C3%AAn_%C4%91%E1%BB%81_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_Blum&action=edit&redlink=1). Một vài thông số độ phức tạp khác được dùng trong lý thuyết độ phức tạp bao gồm [độ phức tạp truyền thông](/wiki/%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_truy%E1%BB%81n_th%C3%B4ng), [độ phức tạp mạch](/w/index.php?title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_m%E1%BA%A1ch&action=edit&redlink=1), và [độ phức tạp cây quyết định](/w/index.php?title=%C4%90%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_c%C3%A2y_quy%E1%BA%BFt_%C4%91%E1%BB%8Bnh&action=edit&redlink=1).
## Các lớp độ phức tạp[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=11) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=11)]
### Định nghĩa lớp độ phức tạp[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=12) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=12)]
Một lớp độ phức tạp là một tập hợp các vấn đề có độ phức tạp tương tự nhau. Các lớp độ phức tạp thường được định nghĩa theo các yếu tố sau:
- Thể loại vấn đề: thể loại phổ biến nhất là bài toán quyết định. Ngoài ra còn có
[bài toán hàm](/w/index.php?title=B%C3%A0i_to%C3%A1n_h%C3%A0m&action=edit&redlink=1), [bài toán đếm](/w/index.php?title=B%C3%A0i_to%C3%A1n_%C4%91%E1%BA%BFm&action=edit&redlink=1), [bài toán tối ưu](/w/index.php?title=B%C3%A0i_to%C3%A1n_t%E1%BB%91i_%C6%B0u&action=edit&redlink=1), [bài toán có lời hứa](/w/index.php?title=B%C3%A0i_to%C3%A1n_c%C3%B3_l%E1%BB%9Di_h%E1%BB%A9a&action=edit&redlink=1), v.v.
- Mô hình tính toán: mô hình phổ biến nhất là máy Turing tất định. Ngoài ra còn có
[máy Turing bất định](/w/index.php?title=M%C3%A1y_Turing_b%E1%BA%A5t_%C4%91%E1%BB%8Bnh&action=edit&redlink=1), [mạch Boole](/w/index.php?title=M%E1%BA%A1ch_Boole&action=edit&redlink=1), [máy Turing lượng tử](/w/index.php?title=M%C3%A1y_Turing_l%C6%B0%E1%BB%A3ng_t%E1%BB%AD&action=edit&redlink=1), [mạch đơn điệu](/w/index.php?title=M%E1%BA%A1ch_%C4%91%C6%A1n_%C4%91i%E1%BB%87u&action=edit&redlink=1), v.v.
- Loại tài nguyên bị giới hạn và giới hạn cụ thể: chẳng hạn như "thời gian đa thức", "bộ nhớ lôgarit", v.v.
### Các lớp độ phức tạp quan trọng[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=13) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=13)]
|Lớp độ phức tạp||Mô hình tính toán||Giới hạn tài nguyên|
|
|f( n)) *f*( *n*) [P](/wiki/P_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)) *n*) [EXPTIME](/w/index.php?title=EXPTIME&action=edit&redlink=1) poly( *n*) [NTIME](/w/index.php?title=NTIME&action=edit&redlink=1)( *f*( *n*)) *f*( *n*) [NP](/wiki/NP_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)) *n*) [NEXPTIME](/w/index.php?title=NEXPTIME&action=edit&redlink=1) poly( *n*) [DSPACE](/w/index.php?title=DSPACE&action=edit&redlink=1)( *f*( *n*)) *f*( *n*) [L](/wiki/L_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)) *n*) [PSPACE](/wiki/PSPACE) *n*) [EXPSPACE](/w/index.php?title=EXPSPACE&action=edit&redlink=1) poly( *n*) [NSPACE](/w/index.php?title=NSPACE&action=edit&redlink=1)( *f*( *n*)) *f*( *n*) [NL](/wiki/NL_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)) *n*) [NPSPACE](/w/index.php?title=NPSPACE&action=edit&redlink=1) *n*) [NEXPSPACE](/w/index.php?title=NEXPSPACE&action=edit&redlink=1) poly( *n*)
Theo
[định lý Savitch](/w/index.php?title=%C4%90%E1%BB%8Bnh_l%C3%BD_Savitch&action=edit&redlink=1), PSPACE = NPSPACE và EXPSPACE = NEXPSPACE.
Một số lớp độ phức tạp quan trọng khác bao gồm
[BPP](/wiki/BPP_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)), [ZPP](/wiki/ZPP_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)), [RP](/wiki/RP_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)) là các lớp định nghĩa trên [máy Turing ngẫu nhiên](/w/index.php?title=M%C3%A1y_Turing_ng%E1%BA%ABu_nhi%C3%AAn&action=edit&redlink=1), [AC](/w/index.php?title=AC_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)&action=edit&redlink=1) và [NC](/wiki/NC_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)) là các lớp định nghĩa trên mạch logic Boole, và [BQP](/w/index.php?title=BQP_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)&action=edit&redlink=1) và [QMA](/w/index.php?title=QMA_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)&action=edit&redlink=1) là các lớp định nghĩa trên máy Turing lượng tử. [#P](/w/index.php?title=Sharp-P&action=edit&redlink=1) là một lớp độ phức tạp quan trọng cho các bài toán đếm. Các lớp như [IP](/w/index.php?title=IP_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)&action=edit&redlink=1) và [AM](/w/index.php?title=AM_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)&action=edit&redlink=1) được định nghĩa thông qua [hệ thống chứng minh tương tác](/w/index.php?title=H%E1%BB%87_th%E1%BB%91ng_ch%E1%BB%A9ng_minh_t%C6%B0%C6%A1ng_t%C3%A1c&action=edit&redlink=1). [ALL](/w/index.php?title=ALL_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)&action=edit&redlink=1) là lớp tất cả các bài toán quyết định.
### Các định lý cấp bậc[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=14) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=14)]
Với các lớp độ phức tạp định nghĩa như trên, một vấn đề đáng quan tâm là liệu với nhiều tài nguyên hơn, chẳng hạn như nhiều thời gian hơn, tập hợp các bài toán giải được có nhiều lên hay không. Cụ thể hơn, mặc dù DTIME(
*n*) rõ ràng là tập hợp con của DTIME( *n 2*), một câu hỏi lý thú là liệu mối quan hệ tập hợp con có chặt hay không. Với thời gian và bộ nhớ, câu hỏi trên được trả lời bởi các định lý cấp bậc thời gian và bộ nhớ. Cụ thể hơn, [định lý cấp bậc thời gian](/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_c%E1%BA%A5p_b%E1%BA%ADc_th%E1%BB%9Di_gian)là
.
.
Các định lý cấp bậc thời gian và bộ nhớ là cơ sở cho hầu hết các kết quả phân tách các lớp độ phức tạp. Ví dụ như định lý cấp bậc thời gian cho ta thấy P là tập hợp con chặt của EXPTIME, và định lý cấp bậc bộ nhớ cho ta thấy L là tập con chặt của PSPACE.
### Quy về[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=15) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=15)]
Nhiều lớp độ phức tạp được định nghĩa thông qua khái niệm phép quy về. Một phép quy về là một biến đổi từ một bài toán này thành một bài toán khác. Nó thâu tóm khái niệm trực giác một bài toán ít nhất là khó bằng một bài toán khác. Nếu một bài toán
*X* có thể được giải bằng thuật toán cho bài toán *Y* thì *X* không khó hơn *Y*, và ta nói *X* *quy về* *Y*. Có nhiều kiểu quy về khác nhau, tùy theo phương pháp quy về, chẳng hạn như phép quy về Cook, phép quy về Karp, phép quy về Levin, và tùy theo độ phức tạp của phép quy về, chẳng hạn như [quy về trong thời gian đa thức](/w/index.php?title=Quy_v%E1%BB%81_trong_th%E1%BB%9Di_gian_%C4%91a_th%E1%BB%A9c&action=edit&redlink=1), hoặc [quy về trong bộ nhớ lôgarit](/w/index.php?title=Quy_v%E1%BB%81_trong_b%E1%BB%99_nh%E1%BB%9B_l%C3%B4garit&action=edit&redlink=1).
Phép quy về phổ biến nhất là quy về trong thời gian đa thức. Điều này có nghĩa là thuật toán quy về chạy trong thời gian đa thức. Ví dụ như bài toán tính bình phương của một số nguyên có thể được quy về bài toán nhân hai số nguyên. Có nghĩa là thuật toán nhân hai số nguyên có thể dùng để tính bình phương một số bằng cách dùng số nguyên cần tính bình phương làm cả hai thừa số cho thuật toán nhân số. Do đó, tính bình phương không khó hơn phép nhân, bởi vì tính bình phương có thể quy về phép nhân.
Định nghĩa trên dẫn tới khái niệm khó cho một lớp độ phức tạp. Một bài toán
*X* là khó cho lớp bài toán *C* nếu mọi bài toán trong *C* có thể quy về *X*. Khi đó, không có bài toán nào trong *C* là khó hơn *X* do một thuật toán cho *X* có thể giải bất kì bài toán nào trong *C*. Dĩ nhiên khái niệm bài toán khó tùy thuộc vào loại quy về được sử dụng. Cho các lớp độ phức tạp lớn hơn P, quy về trong thời gian đa thức thường được sử dụng. Ví dụ như tập hợp các bài toán khó cho NP là tập hợp các bài toán [NP-khó](/wiki/NP-kh%C3%B3).
Nếu bài toán
*X* nằm trong *C* và là khó cho *C*, thì *X* là * cho đầy đủ* *C*. Điều này có nghĩa là *X*là bài toán khó nhất trong *C*. (Do có thể có nhiều bài toán cùng độ khó, có thể nói là *X*là một trong những bài toán khó nhất trong *C*). Do vậy, lớp [NP-đầy đủ](/wiki/NP-%C4%91%E1%BA%A7y_%C4%91%E1%BB%A7)chứa những bài toán khó nhất trong NP, theo nghĩa chúng là những bài toán có nhiều khả năng nhất không giải được trong P. Do bài toán P = NP vẫn chưa được giải, nếu có thể quy một bài toán NP-đầy đủ, *Π*về bài toán 2 *Π*thì chưa có thuật toán thời gian đa thức nào cho 1 *Π*. Bởi vì nếu có thuật toán thời gian đa thức cho 1 *Π*thì cũng có thuật toán thời gian đa thức cho 1 *Π*. Tương tự như vậy, do mọi bài toán trong NP đều có thể quy về các bài toán NP-đầy đủ, nếu có thể giải được một bài toán NP-đầy đủ trong thời gian đa thức thì P = NP. 2 [[2]](#cite_note-Sipser2006-2)
## Các bài toán mở quan trọng[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=16) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=16)]
### Bài toán P so với NP[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=17) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=17)]
Lớp độ phức tạp P thường được xem là mô hình toán học cho các vấn đề tính toán có thuật toán hiệu quả. Giả thuyết này được gọi là
[luận đề Cobham-Edmonds](/w/index.php?title=Lu%E1%BA%ADn_%C4%91%E1%BB%81_Cobham-Edmonds&action=edit&redlink=1). Trong khi đó lớp độ phức tạp NP chứa nhiều bài toán quan trọng cần được giải quyết hiệu quả, nhưng vẫn chưa có thuật toán hiệu quả nào, chẳng hạn như [bài toán thỏa mãn biểu thức logic](/w/index.php?title=B%C3%A0i_to%C3%A1n_th%E1%BB%8Fa_m%C3%A3n_bi%E1%BB%83u_th%E1%BB%A9c_logic&action=edit&redlink=1), bài toán [đường đi Hamilton](/wiki/%C4%90%C6%B0%E1%BB%9Dng_%C4%91i_Hamilton), và bài toán [phủ đỉnh](/w/index.php?title=Ph%E1%BB%A7_%C4%91%E1%BB%89nh&action=edit&redlink=1). Do máy Turing đơn định là trường hợp đặc biệt của máy Turing không đơn định, có thể dễ dàng nhận thấy mọi bài toán trong P đều nằm trong NP.
Câu hỏi liệu P có bằng NP hay không là một trong những câu hỏi quan trọng nhất trong lý thuyết khoa học máy tính do tính áp dụng rộng rãi của lời giải.
Nếu câu trả lời là có, thì nhiều bài toán quan trọng có thể được giải quyết hiệu quả. Những bài toán này bao gồm nhiều loại [2] [quy hoạch nguyên](/w/index.php?title=Quy_ho%E1%BA%A1ch_nguy%C3%AAn&action=edit&redlink=1)trong [vận trù học](/wiki/V%E1%BA%ADn_tr%C3%B9_h%E1%BB%8Dc), nhiều vấn đề trong [hậu cần](/wiki/H%E1%BA%ADu_c%E1%BA%A7n), [dự đoán cấu trúc protein](/w/index.php?title=D%E1%BB%B1_%C4%91o%C3%A1n_c%E1%BA%A5u_tr%C3%BAc_protein&action=edit&redlink=1)trong [sinh học](/wiki/Sinh_h%E1%BB%8Dc), và khả năm tìm chứng minh chặt chẽ cho các định lý toán học. [[3]](#cite_note-3) Bài toán P so với NP là một trong những [[4]](#cite_note-4) [bài toán giải thưởng thiên niên kỷ](/w/index.php?title=B%C3%A0i_to%C3%A1n_gi%E1%BA%A3i_th%C6%B0%E1%BB%9Fng_thi%C3%AAn_ni%C3%AAn_k%E1%BB%B7&action=edit&redlink=1)lựa chọn bởi [viện toán học Clay](/w/index.php?title=Vi%E1%BB%87n_to%C3%A1n_h%E1%BB%8Dc_Clay&action=edit&redlink=1). Có một giải thưởng US$1.000.000 cho việc giải quyết bài toán. [[5]](#cite_note-5)
### Bài toán trong NP không nằm trong P và không là NP-đầy đủ[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=18) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=18)]
Ladner đã chứng minh rằng nếu
**P** ≠ **NP** thì tồn tại bài toán trong **NP** không nằm trong **P** cũng như không là **NP-đầy đủ**. Các bài toán như vậy gọi là bài toán [6] [NP-trung bình](/w/index.php?title=NP-trung_b%C3%ACnh&action=edit&redlink=1). Bài toán [đồ thị đẳng cấu](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_%C4%91%E1%BA%B3ng_c%E1%BA%A5u&action=edit&redlink=1), [bài toán tính lôga rời rạc](/w/index.php?title=B%C3%A0i_to%C3%A1n_t%C3%ADnh_l%C3%B4ga_r%E1%BB%9Di_r%E1%BA%A1c&action=edit&redlink=1), và bài toán [phân tích ra thừa số nguyên tố](/w/index.php?title=Ph%C3%A2n_t%C3%ADch_ra_th%E1%BB%ABa_s%E1%BB%91_nguy%C3%AAn_t%E1%BB%91&action=edit&redlink=1)là các ví dụ của những bài toán được tin là NP-trung bình. Chúng nằm trong số rất ít bài toán trong NP không biết có nằm trong **P**và cũng không biết có là **NP-đầy đủ**.
### Phân biệt giữa các lớp độ phức tạp khác[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=19) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=19)]
Có nhiều lớp độ phức tạp được tin là khác nhau những vẫn chưa được chứng minh. Ví dụ như
**P** ⊆ **NP** ⊆ [ ⊆ PP](/w/index.php?title=PP_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)&action=edit&redlink=1) **PSPACE**và hoàn toàn có thể **P**= **PSPACE**. Nếu **P**không bằng **NP**thì **P**không bằng **PSPACE**. Do có rất nhiều lớp độ phức tạp giữa **P**và **PSPACE**, chẳng hạn như **RP**, **BPP**, **PP**, **BQP**, **MA**, **PH**, v.v., hoàn toàn có thể là tất cả các lớp này đều bằng nhau. Chứng minh bất kì hai lớp nào trong số đó là khác nhau sẽ là một bước tiến lớn trong lý thuyết độ phức tạp.
Tương tự như vậy,
** là lớp chứa các bài toán co-NP** [phần bù](/w/index.php?title=Ph%E1%BA%A7n_b%C3%B9_(%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p)&action=edit&redlink=1)(các bài toán với câu trả lời *có*/ *không*đảo ngược) của các bài toán trong **NP**. Người ta tin rằng [[7]](#cite_note-7) **NP**không bằng **co-NP**, nhưng điều này vẫn chưa được chứng minh. Nếu hai lớp này không bằng nhau thì **P**cũng không bằng **NP**.
Tương tự như vậy, vẫn chưa biết liệu
**L** (tập hợp các bài toán giải được trong bộ nhớ lôgarit) có bằng **P** hay không. Có nhiều lớp độ phức tạp nằm giữa hai lớp, chẳng hạn như **NL** và **NC**, và vẫn chưa biết liệu chúng bằng nhau hay khác nhau. **P** và **BPP** có nhiều khả năng là bằng nhau. Tuy nhiên hiện vẫn chưa biết liệu **BPP** có bằng **NEXP**.
## Lịch sử[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=20) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=20)]
Trước khi có các nghiên cứu chuyên về độ phức tạp tính toán của các thuật toán, nhiều vấn đề cơ sở đã được các nhà nghiên cứu tìm hiểu. Có ảnh hưởng lớn nhất là định nghĩa máy Turing của
[Alan Turing](/wiki/Alan_Turing) năm 1936, một định nghĩa rất vững chắc và linh hoạt cho máy tính.
Theo
[Fortnow & Homer (2003)](#CITEREFFortnowHomer2003), việc nghiên cứu có hệ thống độ phức tạp tính toán bắt đầu từ bài báo quan trọng mang tên "On the Computational Complexity of Algorithms" của Juris Hartmanis và Richard Stearns (1965). Bài báo này đã đưa ra định nghĩa của độ phức tạp thời gian và bộ nhớ và chứng minh các định lý cấp bậc.
Theo
[Fortnow & Homer (2003)](#CITEREFFortnowHomer2003), các bài báo đầu tiên nghiên cứu các bài toán giải được bằng máy Turing với giới hạn tài nguyên bao gồm định nghĩa của [John Myhill](/w/index.php?title=John_Myhill&action=edit&redlink=1) cho automat giới hạn tuyến tính (Myhill 1960), nghiên cứu của [Raymond Smullyan](/w/index.php?title=Raymond_Smullyan&action=edit&redlink=1) về các tập hợp thô sơ (1961), bài báo của [Hisao Yamada](/w/index.php?title=Hisao_Yamada&action=edit&redlink=1) về tính toán thời gian thực (1962). Trước đó, [8] [Boris Trakhtenbrot](/w/index.php?title=Boris_Trakhtenbrot&action=edit&redlink=1)(1956), một nhà nghiên cứu tiên phong trong ngành ở Liên Xô, cũng đã nghiên cứu một thông số độ phức tạp khác. [[9]](#cite_note-9)
Năm 1967,
[Manuel Blum](/w/index.php?title=Manuel_Blum&action=edit&redlink=1) đã xây dựng các [tiên đề](/w/index.php?title=Ti%C3%AAn_%C4%91%E1%BB%81_Blum&action=edit&redlink=1) cho lý thuyết độ phức tạp và chứng minh một kết quả quan trọng, nay gọi là [định lý tăng tốc](/w/index.php?title=%C4%90%E1%BB%8Bnh_l%C3%BD_t%C4%83ng_t%E1%BB%91c_Blum&action=edit&redlink=1). Lý thuyết độ phức tạp bắt đầu phát triển mạnh sau khi nhà nghiên cứu Mỹ [Stephen Cook](/w/index.php?title=Stephen_Cook&action=edit&redlink=1) và, một cách độc lập, nhà nghiên cứu Liên Xô [Leonid Levin](/w/index.php?title=Leonid_Levin&action=edit&redlink=1), chứng minh rằng tồn tại bài toán có liên hệ thực tế là [NP-đầy đủ](/wiki/NP-%C4%91%E1%BA%A7y_%C4%91%E1%BB%A7). Năm 1972, [Richard Karp](/w/index.php?title=Richard_Karp&action=edit&redlink=1) đã đưa ra một bước tiến lớn với bài báo "Reducibility Among Combinatorial Problems", trong đó ông chứng minh 21 bài toán rất khác nhau trong [tổ hợp](/wiki/T%E1%BB%95_h%E1%BB%A3p_(to%C3%A1n_h%E1%BB%8Dc)) và [lý thuyết đồ thị](/wiki/L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B), tất cả đều rất nổi bật về độ khó, là NP-đầy đủ. [[10]](#cite_note-10)
## Ghi chú[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=21) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=21)] **Xem** [^](#cite_ref-1) [Arora & Barak 2009](#CITEREFAroraBarak2009), Chương 1: The computational model and why it doesn't matter
- ^
**a** [Xem](#cite_ref-Sipser2006_2-1) **ă** [Sipser 2006](#CITEREFSipser2006), Chương 7: Time complexity **Berger, Bonnie A.; Leighton, T (1998), “Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete”,** [^](#cite_ref-3) *Journal of Computational Biology* **5**(1): p27–40, [doi](/wiki/DOI): [10.1089/cmb.1998.5.27](http://dx.doi.org/10.1089%2Fcmb.1998.5.27), [PMID](/wiki/%C4%90%E1%BB%8Bnh_danh_PubMed) [9541869](//www.ncbi.nlm.nih.gov/pubmed/9541869). Đã định rõ hơn một tham số trong
|number=và
|issue=(
[trợ giúp](//en.wikipedia.org/wiki/Help:CS1_errors#redundant_parameters)) [^](#cite_ref-4) [Cook, Stephen](/w/index.php?title=Stephen_Cook&action=edit&redlink=1)(April năm 2000), [,](http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf) *The P versus NP Problem* [Clay Mathematics Institute](/w/index.php?title=Clay_Mathematics_Institute&action=edit&redlink=1), truy cập ngày 18 tháng 10 năm 2006. [^](#cite_ref-5) [Jaffe, Arthur M.](/w/index.php?title=Arthur_Jaffe&action=edit&redlink=1)(2006), [“The Millennium Grand Challenge in Mathematics”](http://www.ams.org/notices/200606/fea-jaffe.pdf), *Notices of the AMS* **53**(6), truy cập ngày 18 tháng 10 năm 2006. **Ladner, Richard E. (1975),** [^](#cite_ref-Ladner75_6-0) [“On the structure of polynomial time reducibility”](http://delivery.acm.org/10.1145/330000/321877/p155-ladner.pdf?key1=321877&key2=7146531911&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618)(PDF), [Journal of the ACM](/w/index.php?title=Journal_of_the_ACM&action=edit&redlink=1)(JACM) **22**(1): 151–171, [doi](/wiki/DOI): [10.1145/321864.321877](http://dx.doi.org/10.1145%2F321864.321877). [^](#cite_ref-7) [Khóa học của Boaz Barak về lý thuyết độ phức tạp tính toán](http://www.cs.princeton.edu/courses/archive/spr06/cos522/) [Bài giảng thứ 2](http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf) **Yamada, H. (1962). “Real-Time Computation and Recursive Functions Not Real-Time Computable”.** [^](#cite_ref-8) *IEEE Transactions on Electronic Computers*. EC-11 (6): 753–760. [doi](/wiki/DOI): [10.1109/TEC.1962.5219459](http://dx.doi.org/10.1109%2FTEC.1962.5219459). **Trakhtenbrot, B.A.: Signalizing functions and tabular operators. Uchionnye Zapiski Penzenskogo Pedinstituta (Transactions of the Penza Pedagogoical Institute) 4, 75–87 (1956) (tiếng Nga)** [^](#cite_ref-9) **Richard M. Karp (1972), “** [^](#cite_ref-10) [Reducibility Among Combinatorial Problems](http://www.cs.berkeley.edu/~luca/cs172/karp.pdf)”, trong R. E. Miller and J. W. Thatcher (editors), *Complexity of Computer Computations*, New York: Plenum, tr. 85–103
### Sách tham khảo[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=22) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=22)] [Sanjeev Arora, Boaz Barak, Sanjeev](/w/index.php?title=Sanjeev_Arora&action=edit&redlink=1); Barak, Boaz (2009), [,](http://www.cs.princeton.edu/theory/complexity/) *Computational Complexity: A Modern Approach* [Cambridge](/w/index.php?title=Cambridge_University_Press&action=edit&redlink=1), [ISBN](/wiki/ISBN) [978-0-521-42426-4](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/978-0-521-42426-4)Đã định rõ hơn một tham số trong
|last1=và
|author=(
[trợ giúp](//en.wikipedia.org/wiki/Help:CS1_errors#redundant_parameters))
- Du, Ding-Zhu; Ko, Ker-I (2000),
*Theory of Computational Complexity*, [John Wiley & Sons](/w/index.php?title=John_Wiley_%26_Sons&action=edit&redlink=1), [ISBN](/wiki/ISBN) [978-0-471-34506-0](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/978-0-471-34506-0)Đã bỏ qua tham số không rõ
|country=(
[trợ giúp](//en.wikipedia.org/wiki/Help:CS1_errors#parameter_ignored)) [Goldreich, Oded](/w/index.php?title=Oded_Goldreich&action=edit&redlink=1)(2008), [, Cambridge University Press](http://www.wisdom.weizmann.ac.il/~oded/cc-book.html) *Computational Complexity: A Conceptual Perspective* [van Leeuwen, Jan](/w/index.php?title=Jan_van_Leeuwen&action=edit&redlink=1)biên tập (1990), *Handbook of theoretical computer science (vol. A): algorithms and complexity*, [MIT Press](/w/index.php?title=MIT_Press&action=edit&redlink=1), [ISBN](/wiki/ISBN) [978-0-444-88071-0](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/978-0-444-88071-0) [Papadimitriou, Christos](/w/index.php?title=Christos_Papadimitriou&action=edit&redlink=1)(1994), *Computational Complexity*(ấn bản 1), Addison Wesley, [ISBN](/wiki/ISBN) [0201530821](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0201530821) [Sipser, Michael](/w/index.php?title=Michael_Sipser&action=edit&redlink=1)(2006), *(ấn bản 2), USA:* [Introduction to the Theory of Computation](/w/index.php?title=Introduction_to_the_Theory_of_Computation&action=edit&redlink=1) [Thomson Course Technology](/w/index.php?title=Thomson_Learning&action=edit&redlink=1), [ISBN](/wiki/ISBN) [0534950973](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0534950973)
### Bài báo tổng quan[
[sửa](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&veaction=edit&vesection=23) | [sửa mã nguồn](/w/index.php?title=L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%99_ph%E1%BB%A9c_t%E1%BA%A1p_t%C3%ADnh_to%C3%A1n&action=edit§ion=23)]
- Khalil, Hatem;
[Ulery, Dana](/w/index.php?title=Dana_Ulery&action=edit&redlink=1)(1976), [, ACM '76 Proceedings of the 1976 Annual Conference, tr. 197,](http://portal.acm.org/citation.cfm?id=800191.805573) *A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations* [doi](/wiki/DOI): [10.1145/800191.805573](http://dx.doi.org/10.1145%2F800191.805573) [Cook, Stephen](/w/index.php?title=Stephen_Cook&action=edit&redlink=1)(1983), “An overview of computational complexity”, *Commun. ACM*(ACM) **26**(6): 400–408, [doi](/wiki/DOI): [10.1145/358141.358144](http://dx.doi.org/10.1145%2F358141.358144), [ISSN](/wiki/ISSN) [0001-0782](//www.worldcat.org/issn/0001-0782)
- Fortnow, Lance; Homer, Steven (2003),
[“A Short History of Computational Complexity”](http://people.cs.uchicago.edu/~fortnow/papers/history.pdf), *Bulletin of the EATCS* **80**: 95–133
- Mertens, Stephan (2002), “Computational Complexity for Physicists”,
*Computing in Science and Engg.*(Piscataway, NJ, USA: IEEE Educational Activities Department) **4**(3): 31–47, [arXiv](/wiki/ArXiv): [cond-mat/0012185](http://arxiv.org/abs/cond-mat/0012185), [doi](/wiki/DOI): [10.1109/5992.998639](http://dx.doi.org/10.1109%2F5992.998639), [ISSN](/wiki/ISSN) [1521-9615](//www.worldcat.org/issn/1521-9615)Đã bỏ qua tham số không rõ
|unused_data=(
[trợ giúp](//en.wikipedia.org/wiki/Help:CS1_errors#parameter_ignored))
|
|
|
|
Chú ý: khoa học máy tính còn có thể được chia thành nhiều chủ đề hay nhiều lĩnh vực khác dựa theo

WARC-Type: response

Content-Type: application/http; msgtype=response

Server: Apache

X-Content-Type-Options: nosniff

Content-language: vi

Content-Encoding: gzip

X-UA-Compatible: IE=Edge

Vary: Accept-Encoding,Cookie

Content-Type: text/html; charset=UTF-8

Via: 1.1 varnish, 1.1 varnish

Accept-Ranges: bytes

Connection: close

X-Cache: cp1055 hit (1), cp1054 frontend miss (0)

Cache-Control: private, s-maxage=0, max-age=0, must-revalidate


text:
Massa Marittima
Bách khoa toàn thư mở Wikipedia
Massa Marittima là một đô thị (comune) ở tỉnh Grosseto, vùng Toscana của Ý. Đô thị Massa Marittima có diện tích km2, dân số thời điểm 31 tháng 5 năm 2005 là 8798 người. Massa Marittima có các đơn vị dân cư sau: Massa Marittima giáp với các đô thị:

markdown:
# Massa Marittima
Bách khoa toàn thư mở Wikipedia
**Massa Marittima** là một đô thị ( *) ở comune* [tỉnh](/wiki/T%E1%BB%89nh_(%C3%9D)) [Grosseto](/wiki/Grosseto_(t%E1%BB%89nh)), [vùng](/wiki/V%C3%B9ng_h%C3%A0nh_ch%C3%ADnh_(%C3%9D)) [Toscana](/wiki/Toscana)của Ý. Đô thị Massa Marittima có diện tích km2, dân số thời điểm [31 tháng 5](/wiki/31_th%C3%A1ng_5)năm [2005](/wiki/2005)là 8798 người. Massa Marittima có các đơn vị dân cư sau: Massa Marittima giáp với các đô thị:
## Tham khảo[
[sửa](/w/index.php?title=Massa_Marittima&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=Massa_Marittima&action=edit§ion=1)]
## Liên kết ngoài[
[sửa](/w/index.php?title=Massa_Marittima&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=Massa_Marittima&action=edit§ion=2)]
|
|

X-Cache: cp1065 hit (1), cp1065 frontend miss (0)


text:
Xã Carlston, Quận Freeborn, Minnesota
Bách khoa toàn thư mở Wikipedia
Xã Carlston (tiếng Anh: Carlston Township) là một xã thuộc quận Freeborn, tiểu bang Minnesota, Hoa Kỳ. Năm 2010, dân số của xã này là 305 người.[1]
Tham khảo[sửa | sửa mã nguồn]
- ^ “2010 Census Gazetteer Files”. Cục Thống kê Dân số Hoa Kỳ. Truy cập ngày 11 tháng 10 năm 2012.

markdown:
# Xã Carlston, Quận Freeborn, Minnesota
Bách khoa toàn thư mở Wikipedia
|
|Xã Carlston Carlston Township
|—
| —
|Tọa độ:
|[Quốc gia](/wiki/Qu%E1%BB%91c_gia) [Hoa Kỳ](/wiki/Hoa_K%E1%BB%B3) [Tiểu bang](/wiki/Ti%E1%BB%83u_bang_Hoa_K%E1%BB%B3) [Minnesota](/wiki/Minnesota) [Quận](/w/index.php?title=Danh_d%C3%A1ch_c%C3%A1c_qu%E1%BA%ADn_%E1%BB%9F_Minnesota&action=edit&redlink=1) [Quận Freeborn](/wiki/Qu%E1%BA%ADn_Freeborn,_Minnesota) **Dân số**(2010) [Múi giờ](/wiki/M%C3%BAi_gi%E1%BB%9D) [CST](/wiki/M%C3%BAi_gi%E1%BB%9D_mi%E1%BB%81n_Trung_(B%E1%BA%AFc_M%E1%BB%B9))( [UTC-6](/wiki/UTC-6)) [DST](/wiki/Quy_%C6%B0%E1%BB%9Bc_gi%E1%BB%9D_m%C3%B9a_h%C3%A8)) **CDT**( [UTC-5](/wiki/UTC-5)) **Xã Carlston** ( [tiếng Anh](/wiki/Ti%E1%BA%BFng_Anh): *Carlston Township*) là một [xã](/wiki/X%C3%A3_c%E1%BB%A7a_Hoa_K%E1%BB%B3) thuộc [quận Freeborn](/wiki/Qu%E1%BA%ADn_Freeborn,_Minnesota), tiểu bang [Minnesota](/wiki/Minnesota), [Hoa Kỳ](/wiki/Hoa_K%E1%BB%B3). Năm 2010, dân số của xã này là 305 người. [[1]](#cite_note-1)
## Tham khảo[
[sửa](/w/index.php?title=X%C3%A3_Carlston,_Qu%E1%BA%ADn_Freeborn,_Minnesota&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=X%C3%A3_Carlston,_Qu%E1%BA%ADn_Freeborn,_Minnesota&action=edit§ion=1)] [^](#cite_ref-1) [“2010 Census Gazetteer Files”](http://www.census.gov/geo/www/gazetteer/gazetteer2010.html). [Cục Thống kê Dân số Hoa Kỳ](/wiki/C%E1%BB%A5c_Th%E1%BB%91ng_k%C3%AA_D%C3%A2n_s%E1%BB%91_Hoa_K%E1%BB%B3). Truy cập ngày 11 tháng 10 năm 2012.

X-Cache: cp1052 miss (0), cp1055 frontend miss (0)


text:
mond
Từ điển mở Wiktionary
Tiếng Hà Lan[sửa]
Danh từ[sửa]
mond gđ
)
Đồng nghĩa[sửa]
Tục ngữ[sửa]
- Waar het hart vol van is, loopt de mond van over.
- Cái gì đó mà đổ đầy trái tim, nó thì làm miệng thổ lộ. Ai nói về việc mà ai nghĩ về.
Động từ[sửa]
mond
- Động từ monden chia ở ngôi thứ nhất số ít. Hoặc với jij (je) đảo pha.
- Lối mệnh lệnh của monden.

markdown:
# mond
Từ điển mở Wiktionary
## Tiếng Hà Lan[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-nld-&action=edit§ion=T-1)]
|
|
|
|Dạng bình thường
|
|số ít |mond|
|
|số nhiều |monden|
|
|Dạng giảm nhẹ
|
|số ít |mondje|
|
|số nhiều |mondjes|
### Danh từ[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-noun-&action=edit§ion=T-1)] **mond** gđ
)
#### Đồng nghĩa[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-syn-&action=edit§ion=T-1)]
### Tục ngữ[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-proverb-&action=edit§ion=T-1)]
- Waar het hart vol van is, loopt de
**mond**van over. *Cái gì đó mà đổ đầy trái tim, nó thì làm miệng thổ lộ.*Ai nói về việc mà ai nghĩ về.
-
### Động từ[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-verb-&action=edit§ion=T-1)] **mond** [Động từ](/wiki/%C4%91%E1%BB%99ng_t%E1%BB%AB) *monden*chia ở [ngôi thứ nhất](/wiki/ng%C3%B4i_th%E1%BB%A9_nh%E1%BA%A5t) [số ít](/wiki/s%E1%BB%91_%C3%ADt). Hoặc với *jij*( *je*) đảo pha.
- Lối mệnh lệnh của monden.

X-Cache: cp1053 miss (0), cp1067 frontend miss (0)


text:
Bạn có thể gửi nhận xét, góp ý hay liên hệ về bài viết Lily Cole trong bộ sưu tập mới nhất của Christian Dior bằng cách gửi thư điện tử tới Lien He Bao Viet Nam. Xin bao gồm tên bài viết Lily Cole trong bo suu tap moi nhat cua Christian Dior ở dạng tiếng Việt không dấu. Hoặc Lily Cole trong bộ sưu tập mới nhất của Christian Dior ở dạng có dấu. Bài viết trong chuyên đề Làm Đẹp của chuyên mục Sống Đẹp.
Lily Cole in the latest collections of Christian Dior
Lily Cole, Christian Dior, HEW Hood, Mark Squire, gallery, latest photos, page
Here is a picture doll Lily Cole " ; the "map of Dior. Photographer: Mark Squire and makeup of the HEW Hood helped Lily Cole shows most clearly, "I" ..
Tăng lương hưu và trợ cấp thêm 8%; Bộ GTVT lên tiếng về vụ Cục trưởng Đường sắt chết tại trụ sở; Bắt ông chủ tạp chí cầm đầu đường dây đánh bạc ngàn tỷ; Hàng tấn mỹ phẩm không nguồn gốc "tràn" vào HN; Làm rõ vụ 12 con dê ‘lạc’ vào trang trại Bí thư huyện... là những thông tin thời sự nổi bật trong ngày 23/1.
Cục trưởng Đường sắt VN được phát hiện chết tại phòng làm việc, "Nữ quái" đất Cảng phẫu thuật mặt trốn nã 10 năm; Thưởng Tết thấp nhất là 30 ngàn đồng; Nữ du khách nước ngoài đến Hà Nội đã bị cướp; Bắt nghi phạm vụ hiếp dâm, giết bé gái bịt đầu mối; Giữ lại táo nhập từ Mỹ, cấm bán ra thị trường... là những thông tin thời sự nổi bật trong ngày.
Thiếu nữ bị kéo lê nửa cây số dưới gầm xe 7 chỗ; 3 công nhân tử vong tại công trường thủy điện; Vụ án tham ô hơn 10 năm chưa xử xong; Hoãn tăng thuế, xăng giảm tới 1.900 đồng/lít; Ô tô lao vun vút ngược chiều trên cầu Nhật Tân; Nữ giáo viên tống tiền giám đốc trường quốc tế... là những thông tin thời sự nổi bật trong ngày 21/1.
Lửa hàn bắn tung tóe tại dự án đường sắt trên cao; Trùm ma túy lĩnh án tử, tiến sĩ luật ốm nặng không phải ra tòa; Má mì xinh đẹp và 2 đại gia bị bắt quả tang mua dâm; Sự ma mãnh của Abbott khi ghi nhãn sữa kỳ thị; Đôi vợ chồng làm giả chữ ký nhiều vị lãnh đạo... là những thông tin thời sự nổi bật trong ngày 20/1.
Thêm một lý do khiến "dự án đất vàng" chậm tiến độ; Xử phạt VTV 40 triệu đồng vì sai phạm của Điều ước thứ 7; Công dân bị tù oan được bồi thường gần 300 triệu; Xe đưa đón học sinh phát cháy trên phố... là những thông tin thời sự nổi bật trong ngày 19/1.
Lần đầu tiên 13 bệnh viện trung ương ký cam kết chấm dứt tình trạng bệnh nhân nằm ghép, đảm bảo 1 bệnh nhân/giường bệnh. Tuy nhiên xung quanh cam kết này vẫn còn nhiều băn khoăn.
Loại vi khuẩn nguy hiểm nhiễm trong táo Mỹ có thể nhiễm trong nhiều loại thực phẩm quan trọng thường xuất hiện trong bữa ăn hàng ngày. ------------ Xem thêm: Táo Mỹ gây chết người đã về Việt Nam?, http://vietbao.vn/tp/Tao-My-gay-chet-nguoi-da-ve-Viet-Nam/7063625/ Tin nhanh Việt Nam ra thế giới vietbao.vn
Thời điểm gần Tết Nguyên đán hàng năm luôn là thời điểm nhạy cảm, cao điểm của nạn buôn lậu
Mấy ngày vừa qua, những trang nhật ký của danh hài Thúy Nga chia sẻ chuyện cô bị “chồng hờ” lừa lấy 350.000 USD rồi bỏ trốn và lấy danh nghĩa của cô để lừa đảo rất nhiều người đã làm dấy lên rất nhiều luồng ý kiến. Giới..
Tổng thống Mỹ nói về trang hoàng kim mới của lịch sử nước Mỹ nơi họ sẽ cùng đồng minh sống vững mạnh. Và Nga sẽ lụi tàn trong sự cô lập? ------------ Xem thêm: Thông điệp Liên bang Mỹ năm 2015, http://vietbao.vn/tp/Thong-diep-Lien-bang-My-nam-2015/7048259/ Tin nhanh Việt Nam ra thế giới vietbao.vn
Cùng dõi theo những hình ảnh ngày làm việc của các nữ chiến sĩ CSGT vừa được Giám đốc Công an TP Hà Nội tặng bằng khen vì có thành tích xuất sắc.
Những ngày qua, cộng đồng mạng liên tục chia sẻ câu chuyện về đôi vợ chồng già bán xăng chịu cho người qua đường khi khách chẳng may "cháy túi" khiến nhiều người cảm động.
Trong khi chúng ta đang có một mùa đông ấm áp cùng gia đình, bạn bè thì ở ngoài kia biết bao em thơ và cụ già đang phải chống chọi với cái lạnh cắt da cắt thịt của tiết trời miền Bắc.
Đừng bao giờ nói câu "Năm sau con sẽ về" vì biết đâu đó là cái Tết cuối cùng ta còn được ở bên cha mẹ.
Và còn rất nhiều những lá thư, những dòng cảm tưởng được viết với nhiều tâm trạng và tình cảm khác nhau gửi đến ông lang vườn, nhưng ẩn trong tất cả những dòng chữ đó là một sự biết ơn, trân trọng.
2014 là năm của tai nạn, hỏa hoạn với hàng trăm vụ cháy lớn trên phạm vi toàn quốc với những hậu quả thảm khốc về cả tài sản và tính mạng con người.
Sơn Tùng M-TP, FB Boiz “đạo nhạc” hay lùm xùm tiền bản quyền show diễn Khánh Ly… đều là những vấn đề nóng của làng nhạc trong năm 2014.
Giới chuyên gia cho rằng: “Năm qua kinh tế toàn cầu phục hồi phục chậm chạp và không vững chắc”.
Bộ Y tế mở đường dây nóng, 146 trẻ tử vong do sởi, nghi án quan chức nhận hối lộ, 3 trẻ chết sau phẫu thuật từ thiện… là những sự kiện đáng chú ý của ngành y năm 2014.
Nhìn lại năm 2014, chúng ta giật mình khi thấy bức tranh toàn cầu ảm đạm với những cuộc xung đột đẫm máu, tai nạn thảm khốc, dịch bệnh đáng sợ và sự nổi lên gây kinh khiếp của khủng bố.
Viết phản hồi

markdown:
|
|
Sau đây là hình ảnh cô búp bê Lily Cole "diện" đồ của Dior. Nhiếp ảnh gia: Mark Squire và trang điểm của Hew Hood giúp Lily Cole thể hiện rõ nét nhất "mình".
Thời trang ở Anh lâu lắm rồi người ta không chia thành các bộ sưu tập Xuân/hè hay Thu/Đông nữa. Thứ đồ hiệu cập nhật của các tên tuổi luôn "đổi mới" suốt cả năm.
Sơ mi chất bò, hàng linen sơn mài, xăng đan, túi xách, tất cả đều của nhãn hiệu Dior - nhà tạo mẫu John Galliano.
Váy có mũ trùm hàng lụa bóng, màu vàng.
Áo tắm hai mảnh, áo khoác chất liệu vải bóng sơn mài.
Áo hai dây màu xanh lá cây, xăng đan và cả nhẫn tay cũng "ăn giơ" với bộ sưu tập của Dior.
|
|
Việt Báo
|
|
TIN
![]()
Bạn có thể gửi nhận xét, góp ý hay liên hệ về bài viết
** bằng cách gửi thư điện tử tới Lily Cole trong bộ sưu tập mới nhất của Christian Dior**
Tăng lương hưu và trợ cấp thêm 8%; Bộ GTVT lên tiếng về vụ Cục trưởng Đường sắt chết tại trụ sở; Bắt ông chủ tạp chí cầm đầu đường dây đánh bạc ngàn tỷ; Hàng tấn mỹ phẩm không nguồn gốc "tràn" vào HN; Làm rõ vụ 12 con dê ‘lạc’ vào trang trại Bí thư huyện... là những thông tin thời sự nổi bật trong ngày 23/1.
Cục trưởng Đường sắt VN được phát hiện chết tại phòng làm việc, "Nữ quái" đất Cảng phẫu thuật mặt trốn nã 10 năm; Thưởng Tết thấp nhất là 30 ngàn đồng; Nữ du khách nước ngoài đến Hà Nội đã bị cướp; Bắt nghi phạm vụ hiếp dâm, giết bé gái bịt đầu mối; Giữ lại táo nhập từ Mỹ, cấm bán ra thị trường... là những thông tin thời sự nổi bật trong ngày.
Thiếu nữ bị kéo lê nửa cây số dưới gầm xe 7 chỗ; 3 công nhân tử vong tại công trường thủy điện; Vụ án tham ô hơn 10 năm chưa xử xong; Hoãn tăng thuế, xăng giảm tới 1.900 đồng/lít; Ô tô lao vun vút ngược chiều trên cầu Nhật Tân; Nữ giáo viên tống tiền giám đốc trường quốc tế... là những thông tin thời sự nổi bật trong ngày 21/1.
Lửa hàn bắn tung tóe tại dự án đường sắt trên cao; Trùm ma túy lĩnh án tử, tiến sĩ luật ốm nặng không phải ra tòa; Má mì xinh đẹp và 2 đại gia bị bắt quả tang mua dâm; Sự ma mãnh của Abbott khi ghi nhãn sữa kỳ thị; Đôi vợ chồng làm giả chữ ký nhiều vị lãnh đạo... là những thông tin thời sự nổi bật trong ngày 20/1.
Thêm một lý do khiến "dự án đất vàng" chậm tiến độ; Xử phạt VTV 40 triệu đồng vì sai phạm của Điều ước thứ 7; Công dân bị tù oan được bồi thường gần 300 triệu; Xe đưa đón học sinh phát cháy trên phố... là những thông tin thời sự nổi bật trong ngày 19/1.
Lần đầu tiên 13 bệnh viện trung ương ký cam kết chấm dứt tình trạng bệnh nhân nằm ghép, đảm bảo 1 bệnh nhân/giường bệnh. Tuy nhiên xung quanh cam kết này vẫn còn nhiều băn khoăn.
Loại vi khuẩn nguy hiểm nhiễm trong táo Mỹ có thể nhiễm trong nhiều loại thực phẩm quan trọng thường xuất hiện trong bữa ăn hàng ngày. ------------ Xem thêm: Táo Mỹ gây chết người đã về Việt Nam?, http://vietbao.vn/tp/Tao-My-gay-chet-nguoi-da-ve-Viet-Nam/7063625/ Tin nhanh Việt Nam ra thế giới vietbao.vn
Thời điểm gần Tết Nguyên đán hàng năm luôn là thời điểm nhạy cảm, cao điểm của nạn buôn lậu
Mấy ngày vừa qua, những trang nhật ký của danh hài Thúy Nga chia sẻ chuyện cô bị “chồng hờ” lừa lấy 350.000 USD rồi bỏ trốn và lấy danh nghĩa của cô để lừa đảo rất nhiều người đã làm dấy lên rất nhiều luồng ý kiến. Giới..
Tổng thống Mỹ nói về trang hoàng kim mới của lịch sử nước Mỹ nơi họ sẽ cùng đồng minh sống vững mạnh. Và Nga sẽ lụi tàn trong sự cô lập? ------------ Xem thêm: Thông điệp Liên bang Mỹ năm 2015, http://vietbao.vn/tp/Thong-diep-Lien-bang-My-nam-2015/7048259/ Tin nhanh Việt Nam ra thế giới vietbao.vn
Cùng dõi theo những hình ảnh ngày làm việc của các nữ chiến sĩ CSGT vừa được Giám đốc Công an TP Hà Nội tặng bằng khen vì có thành tích xuất sắc.
Những ngày qua, cộng đồng mạng liên tục chia sẻ câu chuyện về đôi vợ chồng già bán xăng chịu cho người qua đường khi khách chẳng may "cháy túi" khiến nhiều người cảm động.
Trong khi chúng ta đang có một mùa đông ấm áp cùng gia đình, bạn bè thì ở ngoài kia biết bao em thơ và cụ già đang phải chống chọi với cái lạnh cắt da cắt thịt của tiết trời miền Bắc.
Đừng bao giờ nói câu "Năm sau con sẽ về" vì biết đâu đó là cái Tết cuối cùng ta còn được ở bên cha mẹ.
Và còn rất nhiều những lá thư, những dòng cảm tưởng được viết với nhiều tâm trạng và tình cảm khác nhau gửi đến ông lang vườn, nhưng ẩn trong tất cả những dòng chữ đó là một sự biết ơn, trân trọng.
2014 là năm của tai nạn, hỏa hoạn với hàng trăm vụ cháy lớn trên phạm vi toàn quốc với những hậu quả thảm khốc về cả tài sản và tính mạng con người.
Sơn Tùng M-TP, FB Boiz “đạo nhạc” hay lùm xùm tiền bản quyền show diễn Khánh Ly… đều là những vấn đề nóng của làng nhạc trong năm 2014.
Giới chuyên gia cho rằng: “Năm qua kinh tế toàn cầu phục hồi phục chậm chạp và không vững chắc”.
Bộ Y tế mở đường dây nóng, 146 trẻ tử vong do sởi, nghi án quan chức nhận hối lộ, 3 trẻ chết sau phẫu thuật từ thiện… là những sự kiện đáng chú ý của ngành y năm 2014.
Nhìn lại năm 2014, chúng ta giật mình khi thấy bức tranh toàn cầu ảm đạm với những cuộc xung đột đẫm máu, tai nạn thảm khốc, dịch bệnh đáng sợ và sự nổi lên gây kinh khiếp của khủng bố.
Ý kiến bạn đọc
Viết phản hồi

WARC-Truncated: length

Content-Type: text/html; charset=utf-8

Cache-Control: max-age=280, public


text:
Người hùng Zorro không muốn con mình học gương xấu của cô nàng triệu phú ham thích tiệc tùng Paris Hilton. Trong cuộc..
Thời gian gần đây, Hollywood có vẻ như đang phát tín hiệu cho trào lưu quay lại màn bạc của những ngôi sao hành động một thời vang bóng. “Người hùng” Bruce..
Tôi gặp Đỗ Anh Tuấn, người vẫn được giới nhiếp ảnh gọi là “Tuấn cận” trên con đường ngút ngàn núi đá từ Đồng Văn đi Mèo Vạc, hai huyện vùng cao xa xôi nhất..
Điều gì thể hiện sự khác biệt giữa một người đàn ông và một người phụ nữ khi bày tỏ tình cảm? Đó là sự kín đáo!Với một người phụ nữ, khi họ thích một anh chàng..
Cách đây vài chục năm, khi tất cả mọi người chỉ chăm chăm lo sao cho đủ ngày hai bữa, lo nuôi con heo con gà trồng đám rau vun gốc mướp tìm mọi cách tự cải..
Chuẩn bị: (2 phần)- Khoai tây: 2 củ- Bắp hạt: 2 thìa cà phê- Mướp tây, cà rốt cắt hạt lựu: mỗi thứ 2 thìa cà phê
Gầm cầu thang thường là nơi tù đọng, ít lui tới nên nhiều bụi và ẩm. Nếu bạn chịu khó tìm tòi và sáng tạo một chút thì nơi này hoàn toàn có thể biến thành điểm..
Xã hội hay lên án nạn bạo hành giới và bạo lực gia đình mà ít khi đề cập tới một vấn nạn xuất hiện không ít ở môi trường làm việc, đó là “bạo hành công..
Cuối tuần rồi, hãy xả hơi đi nào... Điều gì thú vị sẽ đến với các bạn trong ngày hôm nay nhỉ? Khám phá đi thôi...
Một siêu căn hộ penthouse nằm ở trung tâm thành phố New York với tổng diện tích sử dụng hơn 1.000 m2. Nơi đây có thể đủ chỗ ở tiện nghi, hoành tráng cho cả một..
Tăng lương hưu và trợ cấp thêm 8%; Bộ GTVT lên tiếng về vụ Cục trưởng Đường sắt chết tại trụ sở; Bắt ông chủ tạp chí cầm đầu đường dây đánh bạc ngàn tỷ; Hàng tấn mỹ phẩm không nguồn gốc "tràn" vào HN; Làm rõ vụ 12 con dê ‘lạc’ vào trang trại Bí thư huyện... là những thông tin thời sự nổi bật trong ngày 23/1.
Cục trưởng Đường sắt VN được phát hiện chết tại phòng làm việc, "Nữ quái" đất Cảng phẫu thuật mặt trốn nã 10 năm; Thưởng Tết thấp nhất là 30 ngàn đồng; Nữ du khách nước ngoài đến Hà Nội đã bị cướp; Bắt nghi phạm vụ hiếp dâm, giết bé gái bịt đầu mối; Giữ lại táo nhập từ Mỹ, cấm bán ra thị trường... là những thông tin thời sự nổi bật trong ngày.
Thiếu nữ bị kéo lê nửa cây số dưới gầm xe 7 chỗ; 3 công nhân tử vong tại công trường thủy điện; Vụ án tham ô hơn 10 năm chưa xử xong; Hoãn tăng thuế, xăng giảm tới 1.900 đồng/lít; Ô tô lao vun vút ngược chiều trên cầu Nhật Tân; Nữ giáo viên tống tiền giám đốc trường quốc tế... là những thông tin thời sự nổi bật trong ngày 21/1.
Lửa hàn bắn tung tóe tại dự án đường sắt trên cao; Trùm ma túy lĩnh án tử, tiến sĩ luật ốm nặng không phải ra tòa; Má mì xinh đẹp và 2 đại gia bị bắt quả tang mua dâm; Sự ma mãnh của Abbott khi ghi nhãn sữa kỳ thị; Đôi vợ chồng làm giả chữ ký nhiều vị lãnh đạo... là những thông tin thời sự nổi bật trong ngày 20/1.
Thêm một lý do khiến "dự án đất vàng" chậm tiến độ; Xử phạt VTV 40 triệu đồng vì sai phạm của Điều ước thứ 7; Công dân bị tù oan được bồi thường gần 300 triệu; Xe đưa đón học sinh phát cháy trên phố... là những thông tin thời sự nổi bật trong ngày 19/1.
Lần đầu tiên 13 bệnh viện trung ương ký cam kết chấm dứt tình trạng bệnh nhân nằm ghép, đảm bảo 1 bệnh nhân/giường bệnh. Tuy nhiên xung quanh cam kết này vẫn còn nhiều băn khoăn.
Loại vi khuẩn nguy hiểm nhiễm trong táo Mỹ có thể nhiễm trong nhiều loại thực phẩm quan trọng thường xuất hiện trong bữa ăn hàng ngày. ------------ Xem thêm: Táo Mỹ gây chết người đã về Việt Nam?, http://vietbao.vn/tp/Tao-My-gay-chet-nguoi-da-ve-Viet-Nam/7063625/ Tin nhanh Việt Nam ra thế giới vietbao.vn
Thời điểm gần Tết Nguyên đán hàng năm luôn là thời điểm nhạy cảm, cao điểm của nạn buôn lậu
Mấy ngày vừa qua, những trang nhật ký của danh hài Thúy Nga chia sẻ chuyện cô bị “chồng hờ” lừa lấy 350.000 USD rồi bỏ trốn và lấy danh nghĩa của cô để lừa đảo rất nhiều người đã làm dấy lên rất nhiều luồng ý kiến. Giới..
Tổng thống Mỹ nói về trang hoàng kim mới của lịch sử nước Mỹ nơi họ sẽ cùng đồng minh sống vững mạnh. Và Nga sẽ lụi tàn trong sự cô lập? ------------ Xem thêm: Thông điệp Liên bang Mỹ năm 2015, http://vietbao.vn/tp/Thong-diep-Lien-bang-My-nam-2015/7048259/ Tin nhanh Việt Nam ra thế giới vietbao.vn
Cùng dõi theo những hình ảnh ngày làm việc của các nữ chiến sĩ CSGT vừa được Giám đốc Công an TP Hà Nội tặng bằng khen vì có thành tích xuất sắc.
Những ngày qua, cộng đồng mạng liên tục chia sẻ câu chuyện về đôi vợ chồng già bán xăng chịu cho người qua đường khi khách chẳng may "cháy túi" khiến nhiều người cảm động.
Trong khi chúng ta đang có một mùa đông ấm áp cùng gia đình, bạn bè thì ở ngoài kia biết bao em thơ và cụ già đang phải chống chọi với cái lạnh cắt da cắt thịt của tiết trời miền Bắc.
Đừng bao giờ nói câu "Năm sau con sẽ về" vì biết đâu đó là cái Tết cuối cùng ta còn được ở bên cha mẹ.
Và còn rất nhiều những lá thư, những dòng cảm tưởng được viết với nhiều tâm trạng và tình cảm khác nhau gửi đến ông lang vườn, nhưng ẩn trong tất cả những dòng chữ đó là một sự biết ơn, trân trọng.
2014 là năm của tai nạn, hỏa hoạn với hàng trăm vụ cháy lớn trên phạm vi toàn quốc với những hậu quả thảm khốc về cả tài sản và tính mạng con người.
Sơn Tùng M-TP, FB Boiz “đạo nhạc” hay lùm xùm tiền bản quyền show diễn Khánh Ly… đều là những vấn đề nóng của làng nhạc trong năm 2014.
Giới chuyên gia cho rằng: “Năm qua kinh tế toàn cầu phục hồi phục chậm chạp và không vững chắc”.
Bộ Y tế mở đường dây nóng, 146 trẻ tử vong do sởi, nghi án quan chức nhận hối lộ, 3 trẻ chết sau phẫu thuật từ thiện… là những sự kiện đáng chú ý của ngành y năm 2014.
Nhìn lại năm 2014, chúng ta giật mình khi thấy bức tranh toàn cầu ảm đạm với những cuộc xung đột đẫm máu, tai nạn thảm khốc, dịch bệnh đáng sợ và sự nổi lên gây kinh khiếp của khủng bố.

Cache-Control: max-age=200, public


text:
Đau bụng, sưng phù, đau lưng dưới, đau xương chậu, mau mất sức... đó là những hiện tượng sinh lý khá phổ biến ở đa số phụ nữ. Tuy nhiên tần xuất của những cơn đau này chính là dấu hiệu báo trước bệnh ung thư buồng trứng.
Các phụ nữ bị ung thư buồng trứng cho biết những cơn đau trên xảy ra liên tục. Những cơn đầy hơi, chứng khó tiêu, nôn mửa và những thay đổi khác trong quá trình tiêu hóa, đặc biệt là tại vùng bụng cũng là những dấu hiệu đáng quan tâm.
Các bác sĩ cũng khuyến cáo phụ nữ nên đến phòng khám chuyên khoa nếu họ thấy đau rát trong lúc quan hệ tình dục kèm theo những cơn mệt mỏi và xuất huyết liên tục ở cơ quan sinh dục.
ANH QUÝ (Theo Healthscout)
Bạn có thể gửi nhận xét, góp ý hay liên hệ về bài viết Những triệu chứng của bệnh ung thư buồng trứng bằng cách gửi thư điện tử tới Lien He Bao Viet Nam. Xin bao gồm tên bài viết Nhung trieu chung cua benh ung thu buong trung ở dạng tiếng Việt không dấu. Hoặc Những triệu chứng của bệnh ung thư buồng trứng ở dạng có dấu. Bài viết trong chuyên đề Tin Sức Khỏe của chuyên mục Sức Khỏe.
Symptoms of ovarian cancer
ovarian cancer, symptoms, women, however, the majority, physiological, phenomena, pain
Ovarian cancer symptoms manifest very early, but most women are often mistaken they are normal physiological phenomena of the world ..
Tăng lương hưu và trợ cấp thêm 8%; Bộ GTVT lên tiếng về vụ Cục trưởng Đường sắt chết tại trụ sở; Bắt ông chủ tạp chí cầm đầu đường dây đánh bạc ngàn tỷ; Hàng tấn mỹ phẩm không nguồn gốc "tràn" vào HN; Làm rõ vụ 12 con dê ‘lạc’ vào trang trại Bí thư huyện... là những thông tin thời sự nổi bật trong ngày 23/1.
Cục trưởng Đường sắt VN được phát hiện chết tại phòng làm việc, "Nữ quái" đất Cảng phẫu thuật mặt trốn nã 10 năm; Thưởng Tết thấp nhất là 30 ngàn đồng; Nữ du khách nước ngoài đến Hà Nội đã bị cướp; Bắt nghi phạm vụ hiếp dâm, giết bé gái bịt đầu mối; Giữ lại táo nhập từ Mỹ, cấm bán ra thị trường... là những thông tin thời sự nổi bật trong ngày.
Thiếu nữ bị kéo lê nửa cây số dưới gầm xe 7 chỗ; 3 công nhân tử vong tại công trường thủy điện; Vụ án tham ô hơn 10 năm chưa xử xong; Hoãn tăng thuế, xăng giảm tới 1.900 đồng/lít; Ô tô lao vun vút ngược chiều trên cầu Nhật Tân; Nữ giáo viên tống tiền giám đốc trường quốc tế... là những thông tin thời sự nổi bật trong ngày 21/1.
Lửa hàn bắn tung tóe tại dự án đường sắt trên cao; Trùm ma túy lĩnh án tử, tiến sĩ luật ốm nặng không phải ra tòa; Má mì xinh đẹp và 2 đại gia bị bắt quả tang mua dâm; Sự ma mãnh của Abbott khi ghi nhãn sữa kỳ thị; Đôi vợ chồng làm giả chữ ký nhiều vị lãnh đạo... là những thông tin thời sự nổi bật trong ngày 20/1.
Thêm một lý do khiến "dự án đất vàng" chậm tiến độ; Xử phạt VTV 40 triệu đồng vì sai phạm của Điều ước thứ 7; Công dân bị tù oan được bồi thường gần 300 triệu; Xe đưa đón học sinh phát cháy trên phố... là những thông tin thời sự nổi bật trong ngày 19/1.
Lần đầu tiên 13 bệnh viện trung ương ký cam kết chấm dứt tình trạng bệnh nhân nằm ghép, đảm bảo 1 bệnh nhân/giường bệnh. Tuy nhiên xung quanh cam kết này vẫn còn nhiều băn khoăn.
Loại vi khuẩn nguy hiểm nhiễm trong táo Mỹ có thể nhiễm trong nhiều loại thực phẩm quan trọng thường xuất hiện trong bữa ăn hàng ngày. ------------ Xem thêm: Táo Mỹ gây chết người đã về Việt Nam?, http://vietbao.vn/tp/Tao-My-gay-chet-nguoi-da-ve-Viet-Nam/7063625/ Tin nhanh Việt Nam ra thế giới vietbao.vn
Thời điểm gần Tết Nguyên đán hàng năm luôn là thời điểm nhạy cảm, cao điểm của nạn buôn lậu
Mấy ngày vừa qua, những trang nhật ký của danh hài Thúy Nga chia sẻ chuyện cô bị “chồng hờ” lừa lấy 350.000 USD rồi bỏ trốn và lấy danh nghĩa của cô để lừa đảo rất nhiều người đã làm dấy lên rất nhiều luồng ý kiến. Giới..
Tổng thống Mỹ nói về trang hoàng kim mới của lịch sử nước Mỹ nơi họ sẽ cùng đồng minh sống vững mạnh. Và Nga sẽ lụi tàn trong sự cô lập? ------------ Xem thêm: Thông điệp Liên bang Mỹ năm 2015, http://vietbao.vn/tp/Thong-diep-Lien-bang-My-nam-2015/7048259/ Tin nhanh Việt Nam ra thế giới vietbao.vn
Cùng dõi theo những hình ảnh ngày làm việc của các nữ chiến sĩ CSGT vừa được Giám đốc Công an TP Hà Nội tặng bằng khen vì có thành tích xuất sắc.
Những ngày qua, cộng đồng mạng liên tục chia sẻ câu chuyện về đôi vợ chồng già bán xăng chịu cho người qua đường khi khách chẳng may "cháy túi" khiến nhiều người cảm động.
Trong khi chúng ta đang có một mùa đông ấm áp cùng gia đình, bạn bè thì ở ngoài kia biết bao em thơ và cụ già đang phải chống chọi với cái lạnh cắt da cắt thịt của tiết trời miền Bắc.
Đừng bao giờ nói câu "Năm sau con sẽ về" vì biết đâu đó là cái Tết cuối cùng ta còn được ở bên cha mẹ.
Và còn rất nhiều những lá thư, những dòng cảm tưởng được viết với nhiều tâm trạng và tình cảm khác nhau gửi đến ông lang vườn, nhưng ẩn trong tất cả những dòng chữ đó là một sự biết ơn, trân trọng.
2014 là năm của tai nạn, hỏa hoạn với hàng trăm vụ cháy lớn trên phạm vi toàn quốc với những hậu quả thảm khốc về cả tài sản và tính mạng con người.
Sơn Tùng M-TP, FB Boiz “đạo nhạc” hay lùm xùm tiền bản quyền show diễn Khánh Ly… đều là những vấn đề nóng của làng nhạc trong năm 2014.
Giới chuyên gia cho rằng: “Năm qua kinh tế toàn cầu phục hồi phục chậm chạp và không vững chắc”.
Bộ Y tế mở đường dây nóng, 146 trẻ tử vong do sởi, nghi án quan chức nhận hối lộ, 3 trẻ chết sau phẫu thuật từ thiện… là những sự kiện đáng chú ý của ngành y năm 2014.
Nhìn lại năm 2014, chúng ta giật mình khi thấy bức tranh toàn cầu ảm đạm với những cuộc xung đột đẫm máu, tai nạn thảm khốc, dịch bệnh đáng sợ và sự nổi lên gây kinh khiếp của khủng bố.
Viết phản hồi

markdown:
|
|![]()
|Một ca ung thư buồng trứng|
Đau bụng, sưng phù, đau lưng dưới, đau xương chậu, mau mất sức... đó là những hiện tượng sinh lý khá phổ biến ở đa số phụ nữ. Tuy nhiên tần xuất của những cơn đau này chính là dấu hiệu báo trước bệnh ung thư buồng trứng.
Các phụ nữ bị ung thư buồng trứng cho biết những cơn đau trên xảy ra liên tục. Những cơn đầy hơi, chứng khó tiêu, nôn mửa và những thay đổi khác trong quá trình tiêu hóa, đặc biệt là tại vùng bụng cũng là những dấu hiệu đáng quan tâm.
Các bác sĩ cũng khuyến cáo phụ nữ nên đến phòng khám chuyên khoa nếu họ thấy đau rát trong lúc quan hệ tình dục kèm theo những cơn mệt mỏi và xuất huyết liên tục ở cơ quan sinh dục.
ANH QUÝ (Theo Healthscout)
|
|
TIN
![]()
Bạn có thể gửi nhận xét, góp ý hay liên hệ về bài viết
** bằng cách gửi thư điện tử tới Những triệu chứng của bệnh ung thư buồng trứng**
Tăng lương hưu và trợ cấp thêm 8%; Bộ GTVT lên tiếng về vụ Cục trưởng Đường sắt chết tại trụ sở; Bắt ông chủ tạp chí cầm đầu đường dây đánh bạc ngàn tỷ; Hàng tấn mỹ phẩm không nguồn gốc "tràn" vào HN; Làm rõ vụ 12 con dê ‘lạc’ vào trang trại Bí thư huyện... là những thông tin thời sự nổi bật trong ngày 23/1.
Cục trưởng Đường sắt VN được phát hiện chết tại phòng làm việc, "Nữ quái" đất Cảng phẫu thuật mặt trốn nã 10 năm; Thưởng Tết thấp nhất là 30 ngàn đồng; Nữ du khách nước ngoài đến Hà Nội đã bị cướp; Bắt nghi phạm vụ hiếp dâm, giết bé gái bịt đầu mối; Giữ lại táo nhập từ Mỹ, cấm bán ra thị trường... là những thông tin thời sự nổi bật trong ngày.
Thiếu nữ bị kéo lê nửa cây số dưới gầm xe 7 chỗ; 3 công nhân tử vong tại công trường thủy điện; Vụ án tham ô hơn 10 năm chưa xử xong; Hoãn tăng thuế, xăng giảm tới 1.900 đồng/lít; Ô tô lao vun vút ngược chiều trên cầu Nhật Tân; Nữ giáo viên tống tiền giám đốc trường quốc tế... là những thông tin thời sự nổi bật trong ngày 21/1.
Lửa hàn bắn tung tóe tại dự án đường sắt trên cao; Trùm ma túy lĩnh án tử, tiến sĩ luật ốm nặng không phải ra tòa; Má mì xinh đẹp và 2 đại gia bị bắt quả tang mua dâm; Sự ma mãnh của Abbott khi ghi nhãn sữa kỳ thị; Đôi vợ chồng làm giả chữ ký nhiều vị lãnh đạo... là những thông tin thời sự nổi bật trong ngày 20/1.
Thêm một lý do khiến "dự án đất vàng" chậm tiến độ; Xử phạt VTV 40 triệu đồng vì sai phạm của Điều ước thứ 7; Công dân bị tù oan được bồi thường gần 300 triệu; Xe đưa đón học sinh phát cháy trên phố... là những thông tin thời sự nổi bật trong ngày 19/1.
Lần đầu tiên 13 bệnh viện trung ương ký cam kết chấm dứt tình trạng bệnh nhân nằm ghép, đảm bảo 1 bệnh nhân/giường bệnh. Tuy nhiên xung quanh cam kết này vẫn còn nhiều băn khoăn.
Loại vi khuẩn nguy hiểm nhiễm trong táo Mỹ có thể nhiễm trong nhiều loại thực phẩm quan trọng thường xuất hiện trong bữa ăn hàng ngày. ------------ Xem thêm: Táo Mỹ gây chết người đã về Việt Nam?, http://vietbao.vn/tp/Tao-My-gay-chet-nguoi-da-ve-Viet-Nam/7063625/ Tin nhanh Việt Nam ra thế giới vietbao.vn
Thời điểm gần Tết Nguyên đán hàng năm luôn là thời điểm nhạy cảm, cao điểm của nạn buôn lậu
Mấy ngày vừa qua, những trang nhật ký của danh hài Thúy Nga chia sẻ chuyện cô bị “chồng hờ” lừa lấy 350.000 USD rồi bỏ trốn và lấy danh nghĩa của cô để lừa đảo rất nhiều người đã làm dấy lên rất nhiều luồng ý kiến. Giới..
Tổng thống Mỹ nói về trang hoàng kim mới của lịch sử nước Mỹ nơi họ sẽ cùng đồng minh sống vững mạnh. Và Nga sẽ lụi tàn trong sự cô lập? ------------ Xem thêm: Thông điệp Liên bang Mỹ năm 2015, http://vietbao.vn/tp/Thong-diep-Lien-bang-My-nam-2015/7048259/ Tin nhanh Việt Nam ra thế giới vietbao.vn
Cùng dõi theo những hình ảnh ngày làm việc của các nữ chiến sĩ CSGT vừa được Giám đốc Công an TP Hà Nội tặng bằng khen vì có thành tích xuất sắc.
Những ngày qua, cộng đồng mạng liên tục chia sẻ câu chuyện về đôi vợ chồng già bán xăng chịu cho người qua đường khi khách chẳng may "cháy túi" khiến nhiều người cảm động.
Trong khi chúng ta đang có một mùa đông ấm áp cùng gia đình, bạn bè thì ở ngoài kia biết bao em thơ và cụ già đang phải chống chọi với cái lạnh cắt da cắt thịt của tiết trời miền Bắc.
Đừng bao giờ nói câu "Năm sau con sẽ về" vì biết đâu đó là cái Tết cuối cùng ta còn được ở bên cha mẹ.
Và còn rất nhiều những lá thư, những dòng cảm tưởng được viết với nhiều tâm trạng và tình cảm khác nhau gửi đến ông lang vườn, nhưng ẩn trong tất cả những dòng chữ đó là một sự biết ơn, trân trọng.
2014 là năm của tai nạn, hỏa hoạn với hàng trăm vụ cháy lớn trên phạm vi toàn quốc với những hậu quả thảm khốc về cả tài sản và tính mạng con người.
Sơn Tùng M-TP, FB Boiz “đạo nhạc” hay lùm xùm tiền bản quyền show diễn Khánh Ly… đều là những vấn đề nóng của làng nhạc trong năm 2014.
Giới chuyên gia cho rằng: “Năm qua kinh tế toàn cầu phục hồi phục chậm chạp và không vững chắc”.
Bộ Y tế mở đường dây nóng, 146 trẻ tử vong do sởi, nghi án quan chức nhận hối lộ, 3 trẻ chết sau phẫu thuật từ thiện… là những sự kiện đáng chú ý của ngành y năm 2014.
Nhìn lại năm 2014, chúng ta giật mình khi thấy bức tranh toàn cầu ảm đạm với những cuộc xung đột đẫm máu, tai nạn thảm khốc, dịch bệnh đáng sợ và sự nổi lên gây kinh khiếp của khủng bố.
Ý kiến bạn đọc
Viết phản hồi