Chương 556: Cái vấn đề này quả nhiên là Tú a

(chương này mọi người coi như học bá văn đến xem, nếu như xem không hiểu liền làm nhân vật chính giả vờ cool được rồi, một chương này là vì sau này sinh vật gien công trình làm cửa hàng, mọi người xem đi thì biết, phía sau đổi mới liền sẽ không xuất hiện loại này khuyên lui loại chương hồi rồi, định đô định xong ngậm lệ cũng phải viết xong o(? i? n? i)o)

——

Diệp Hoa nhìn mấy vị học sinh mỉm cười "Coi như năm thiên niên kỷ số học 7 vấn đề khó khăn không nhỏ đứng đầu "P=NP?" Vấn đề đến bây giờ cũng không có ai có thể chứng minh hoặc chứng ngụy, nếu như các ngươi có ai đem tới có thể giải quyết cái vấn đề này liền có thể lập tức đi Mỹ Quốc Clay số học sở nghiên cứu nhận 100 vạn đô la tiền thưởng, phần này treo giải thưởng tới năm thiên niên kỷ tuyên bố đến nay vẫn hữu hiệu."

"Nó đã là thế giới bảy đại số học vấn đề khó khăn đứng đầu, nhưng cùng lúc nó lại vừa là 7 cái vấn đề bên trong lớn nhất dễ hiểu một cái số học vấn đề, thật ra thì chính là một cái làm cân nhắc độc vấn đề, cái vấn đề này đản sinh vu 1971 năm, là lý luận máy tính lĩnh vực đản sinh một cái số học vấn đề."

Trường học là một môn thụ nghiệp giải thích nghi hoặc học vấn, mà Diệp Hoa có thể nói là một cái vô chứng giáo sư, bất quá cái này cũng không gây trở ngại hắn trở thành một tên gọi hợp cách giảng sư.

"Các bạn học, ở trong cuộc sống, các ngươi là làm sao đi cân nhắc một cái vấn đề? Nó là đơn giản hay là phức tạp? Hoặc có lẽ là dễ dàng hay lại là khó khăn?" Diệp Hoa ở trong lớp đi mà đi, khi thì liếc mắt quét nhìn vài tên học sinh có hay không ở nghiêm túc nghe giảng, cái gì động tác nhỏ cũng không chạy khỏi Diệp hiệu trưởng pháp nhãn, khi đi học mấy cái này học sinh coi như nhu thuận, bao gồm bình thường ái gây sự liễu Linh đôi.

Chốc lát liền tự hỏi tự trả lời "Khối này thật giống như không có một cụ thể định lượng tiêu chuẩn, hơn nữa vấn đề sẽ còn tùy theo từng người. Nhưng là máy tính không giống nhau, máy tính tính toán hiệu suất là một cái định giá trị, cũng không có trí lực thương số."

"Tỷ như hai vấn đề, một máy máy tính từ 1 biểu hiện đến 10, cùng từ 1 biểu hiện đến 1000, hiển nhiên vấn đề phía sau phải dùng đến 100 lần thời gian, tương đối trước mặt vấn đề liền khó khăn."

"Đối với một máy máy tính mà nói, cân nhắc một cái vấn đề đơn giản hoặc khó khăn, nhìn giải quyết vấn đề thời gian hoặc là bước bao nhiêu, bởi vì hiệu suất ở nhất định dưới tình huống, thời gian và bước cân nhắc là đồng giá, cho một định nghĩa liền kêu thời gian phức tạp độ, thời gian phức tạp hơn tiểu, càng ít vấn đề càng đơn giản. Nhưng tình huống thực tế còn phải cân nhắc cái gì?"

Nói xong Diệp Hoa nhìn về phía mấy người bọn hắn, chỉ chốc lát sau, liễu Linh đôi liền nói "Còn phải cân nhắc máy tính sở chiếm dụng không gian."

"Trả lời xong toàn bộ chính xác."

Hacker thiếu nữ được khen ngợi mừng thầm, máy tính nhưng là bản Nữ Hiệp sở trường trò hay.

Diệp Hoa đối với nàng ném một cái khen ngợi ánh mắt, coi như là thưởng cho, sau đó nói "Không gian vấn đề liền để một bên, chúng ta hôm nay nói vấn đề thời gian, lấy một thí dụ "

Lại cũng không có cái gì so với kiệt tác "Cử một hạt dẻ" dễ hiểu rồi.

"Một đạo đề, bây giờ ta cho ngươi ra n số lượng, yêu cầu chọn lựa trong đó lớn nhất một vài, cần bao nhiêu bước? Ai biết?"

Vừa dứt lời, nhỏ nhất Ninh Kiệt liền nhanh chóng trả lời "n- 1 bước."

"Trả lời chính xác!"

Diệp Hoa gật đầu một cái, số học tiểu thiên tài Ninh Kiệt nhanh như vậy đáp đi ra ngoài là ở trong dự liệu của hắn, điều tra Phù Không màn ảnh liệt kê 1 chuỗi chữ số "Phương pháp thật ra thì rất đơn giản, trước tương đối tiền hai cái, lấy trong đó lớn nhất cân nhắc cùng cái thứ 3 cân nhắc tiến hành so sánh, sau đó lấy trong đó lớn nhất cân nhắc sẽ cùng cái thứ 4 tương đối, cứ thế mà suy ra, lấy n số lượng liền tương đối n- 1 lần."

"Đề thi thứ hai, hay là cho ra n số lượng, nhưng đạo đề này là muốn yêu cầu nắm n số lượng từ lớn đến nhỏ theo thứ tự thứ tự sắp xếp, như vậy cần bao nhiêu bước đây?"

Ninh Kiệt lần nữa không chút nghĩ ngợi đạo "Yêu cầu n(n- 1)/ 2 bước."

Diệp Hoa lần nữa gật đầu "Trả lời chính xác. Ninh Kiệt đồng học ngươi có thể cùng những bạn học khác giới thiệu một chút tính toán quá trình sao?"

Ninh Kiệt lập tức trả lời "Dùng mới vừa rồi biện pháp trước chọn lựa lớn nhất cân nhắc cần dùng đến n- 1 bước, sau đó chọn lựa còn dư lại toàn bộ cân nhắc bên trong lớn nhất cân nhắc dùng n- 2 bước, loại đẩy xuống chính là (n- 1)+(n- 2)+(n- 3)+ một mực thêm đến đáp án cuối cùng chính là n(n- 1)/ 2."

Liễu Linh đôi nhìn một cái rất nhanh thì thấy rõ rồi, đây không phải là máy tính lập trình bên trong "Nổi bọt pháp" mà, Hacker thiếu nữ tự nhiên nhìn một cái liền biết, thật ra thì những thứ này đều là đơn giản vấn đề, tại chỗ 8 học sinh cũng có thể nhanh chóng hiểu.

Diệp Hoa tiếp lấy giảng đạo "Hiển nhiên, theo n gia tăng, thứ tự sắp xếp độ khó của vấn đề liền so với trước kia chọn lớn nhất đếm độ khó cao rồi. n- 1 khi này cái n rất lớn thời điểm, - 1 có thể tiết kiệm hơi, có hay không không ảnh hưởng, số lượng cấp chính là do n đến quyết định, vấn đề thứ hai thời gian số lượng cấp là do n^ 2 quyết định, khác cũng có thể tỉnh lược, bao gồm hệ số."

Nói tới chỗ này Diệp Hoa điều tra một khối bắt chước tấm bảng đen Phù Không màn ảnh lớn, dùng ngón tay thay thế phấn viết, ở sắc trên nền điểm một cái màu trắng, sau đó ở trên mặt bản liệt kê tư thế "Dùng tiến dần phù hiệu O biểu thị, vấn đề thứ nhất tính toán lượng biểu thị là O(n), vấn đề thứ hai biểu thị là O(n^ 2). Hai vấn đề một đôi so với liền phát hiện theo n gia tăng O(n^ 2) càng khó hơn một ít, khối này rất dễ hiểu, bởi vì n^ 2 so với n đại."

Diệp Hoa tiếp tục vừa viết vừa nói "n, n^ 2, n^ tam đẳng đẳng cấp hoặc là bọn họ tổ hợp liền kêu đa thức, loại vấn đề này chính là "P=NP? Vấn đề" trúng P loại vấn đề. Kia có hay không càng khó hơn vấn đề? Đương nhiên là có, tỷ như số nguyên tố vấn đề."

Vừa nói Diệp Hoa quay đầu nhìn về phía bọn học sinh "Một cái số tự nhiên a có phải hay không số nguyên tố? Giải quyết nó cần bao nhiêu bước? Đần phương pháp chính là ai cá trừ, từ 1 bắt đầu trừ đến √a, cho nên đa dụng nhất đến √a bước, hoàn chỉnh miêu tả chính là một cái n con số số tự nhiên a có phải hay không số nguyên tố?"

Hoàn toàn đại nhập giảng sư vai tuồng Diệp Hoa chợt xoay người ở Phù Không trên màn ảnh tiếp tục liệt kê tư thế "n con số thuật toán cân nhắc nhưng để bày tỏ 10^n- 10^(n- 1), vậy hiển nhiên số nguyên tố vấn đề chính là O(√ 10^ 2), coi như là Số nhị phân cân nhắc cũng là O(√ 2^n), các bạn học nhìn, theo con số n gia tăng số nguyên tố vấn đề là không phải là đã phơi bày chỉ số tăng lên? Đây là rất khủng bố lên cao khuynh hướng."

"Trở lên nói tất cả vấn đề đều có một điểm giống nhau, bất kể có khó không, chỉ cần cho một cái đáp án đi nghiệm chứng, liền sẽ có vẻ dễ dàng rất nhiều, nói thí dụ như một cái a không phải là số nguyên tố, bởi vì nó có thể bị số này b chia hết, kia thử lại phép tính nó là được, có thể ở đa thức trong thời gian tiến hành nghiệm chứng. Như vậy toàn bộ loại vấn đề này chính là NP loại vấn đề."

Diệp Hoa nhìn vòng quanh 8 học sinh, nhìn thấy trong ánh mắt của bọn họ không có bất kỳ nghi ngờ không hiểu, hiển nhiên đều hiểu, đối với bọn họ biểu hiện rất hài lòng.

"N đại biểu không phải là chắc chắn, P cùng NP tiêu chuẩn định nghĩa cùng Đồ Linh máy có liên quan, P có thể ở đa thức trong thời gian giải quyết vấn đề, mà NP bất kể có khó không nhưng có thể ở đa thức trong thời gian nghiệm chứng, đây là bọn hắn hai người khác nhau, phải chú ý. Vậy có phải hay không thuyết NP vấn đề nếu so với P loại vấn đề càng khó hơn? Câu trả lời hay không, bởi vì P loại vấn đề là thuộc về NP loại vấn đề, một điểm này cũng phải chú ý."

Diệp Hoa lại đang bọn học sinh trước mặt đi mà đi, đều đâu vào đấy giảng đạo "Ở số học lên cũng hoặc là máy tính lĩnh vực, đối với một cái vấn đề khó khăn hay không, rất lớn trình độ quyết định bởi với phương thức kế toán, máy tính chính là cách tính, cách tính là máy tính linh hồn. Cho dù làm số học đề mục cũng giống vậy, cùng đề có phương pháp đơn giản nhanh chóng, khả năng chính là chênh lệch một cái phụ trợ tuyến vấn đề."

"Trước mặt nói đều là chết phương pháp, đạt tới mục đích là được. Ở trong máy vi tính thuật ngữ kêu 'Nổi bọt pháp ". Họ phức tạp độ chính là O(n^ 2), mở mang ưu việt cách tính có thể đem phức tạp độ hạ xuống, tỷ như nhanh chóng thứ tự sắp xếp pháp phức tạp độ chính là O(n logn), hiển nhiên nếu so với n^ 2 tiểu, cho nên đang tính toán máy lĩnh vực đối với một cái vấn đề khó dễ nhìn tính toán của nó ưu việt hay không."

"Như vậy thì không khó hiểu rồi, mọi người nghiên cứu từng cái máy tính cách tính, mục đích đúng là nắm NP loại vấn đề xuống đến P loại vấn đề. Nhưng vấn đề nhiều như vậy, phải tìm được không biết năm tháng nào? Như vậy, nếu NP vấn đề là có một điểm giống nhau, tức, bọn họ đều có thể ở đa thức trong thời gian nghiệm chứng, sẽ có hay không có khác một điểm giống nhau?"

Diệp Hoa tự hỏi tự trả lời

"Sở bằng vào chúng ta giả thiết tồn tại một loại 'Vạn năng cách tính ". Nó có thể đem tất cả NP vấn đề xuống đến P loại vấn đề, đây chính là "P=NP?" Vấn đề. Thậm chí đều có thể không cần tính ra cái này 'Vạn năng cách tính' là cái gì, chỉ cần có thể chứng minh hoặc chứng ngụy, liền có thể nắm trăm vạn giải thưởng lớn."

Chợt nhìn về phía bọn học sinh "Đồng thời chúng ta sẽ phát hiện, ở NP vấn đề bên trong có như vậy một ít loại vấn đề, bọn họ rõ ràng nếu so với P loại vấn đề khó khăn rất nhiều rất nhiều, ở cảm giác những vấn đề này là khó nhất trở thành P loại vấn đề, hơn nữa những vấn đề này cũng có một điểm giống nhau, một khi chứng minh bất kỳ một cái nào trong đó vấn đề có một cái ưu việt cách tính có thể rơi xuống P loại vấn đề, kia những vấn đề khác cũng đều có thể rơi xuống P loại vấn đề, nói cách khác chỉ cần chứng minh một người trong đó thuộc về P, chính là P=NP. Như vậy khối này một ít loại vấn đề gọi tắt NP-C, cũng chính là NP hoàn toàn vấn đề."

Diệp Hoa giảng giải tới đây thời điểm tất cả mọi người có thể hiểu rất dễ, nhưng kế tiếp vấn đề đối với bọn hắn mà nói chính là không hữu hảo như vậy rồi.

"NPC rõ ràng liền so với P loại vấn đề khó khăn, hay lại là lấy một thí dụ, gần sát chúng ta sinh hoạt, tỷ như một cái mỹ đoàn bán bên ngoài Tiểu Ca, nhà của hắn ở tại A điểm, phải đi n địa phương đưa bán bên ngoài, n cái địa điểm hai hai khoảng cách đều là đã biết. Vậy xin hỏi cái này bán bên ngoài Tiểu Ca như thế nào đi khắp từng cái địa điểm cuối cùng về nhà, bảo đảm hắn sở đi lộ trình là ngắn nhất đây?"

Nói tới chỗ này, Diệp Hoa dừng lại, cầm lên ly nước uống một cái thấm giọng nói, 8 học sinh cau mày suy nghĩ, trong đó số học thiên phú tốt nhất Ninh Kiệt cũng hồ nghi không ngừng.

Qua một đoạn thời gian cũng không có nhân chủ động trả lời, trong dự liệu, Diệp Hoa đã nói đạo "Cái đề mục này ở chỗ, bán bên ngoài Tiểu Ca hắn đầu tiên là phải đối mặt có bao nhiêu loại đi lộ tuyến khả năng, dùng như thế nào số học miêu tả?"

Bọn học sinh đều nhìn về Diệp Hoa, người sau đạo "Vậy hiển nhiên, kết quả sau cùng chính là n cấp nhân O(n!). Cho nên liền sẽ thấy, khối này phức tạp độ so với trước kia giảng thuật đến vấn đề đại rất nhiều nhiều nữa..., bởi vì O(n!)≈√ 2π(n/e)^n, số này so với lấy hằng số là lại chỉ số lớn hơn nhiều lắm."

Diệp Hoa chợt xoay người ở Phù Không màn ảnh mô phỏng trên bảng đen hoạt động "Hàng như 19 cấp nhân, nhìn qua cảm giác số này không lớn, nhưng là, liệt kê một cái tư thế 19! ≈ 1. 21× 10^ 17, số này lớn đến coi như là dùng bây giờ trâu nhất kinh điển máy tính giả thiết hắn mỗi giây có thể xếp hàng 100 vạn lần cũng phải xếp hàng cái 3000 năm trái phải. Cho nên, bán bên ngoài Tiểu Ca mỗi ngày đưa nhiều như vậy hàng, trên lý thuyết hắn quang là muốn tìm được một cái cao nhất đường đi sợ là không thể nào."

"Nhưng là bạn học môn chú ý, nơi này khó khăn cùng đơn giản đại biểu là một loại khuynh hướng, làm n lúc còn rất nhỏ, não người tính toán lượng cũng có thể nhanh chóng tính toán ra đến, tỷ như cân nhắc độc đi, 3× 3 cân nhắc độc kia học sinh tiểu học đều biết tính, nhưng là bạn học môn ta cho một mình ngươi 100× 100 thử nhìn một chút? Tỷ như 100× 100 phương cách tử, cho ra mấy cái 1~ 100 con số làm giây thừng, sau đó yêu cầu nắm còn dư lại mỗi người toàn bộ lấp đầy cũng bảo đảm dù sao đều là 1~ 100, cái vấn đề này coi như dùng đương kim thế giới trâu nhất máy tính cũng không thể nhanh chóng yêu cầu đi ra."

"Như vậy hiển nhiên, đạo đề này cũng là NPC vấn đề, đều chơi qua trục lôi, Russia rô những thứ này trò chơi nhỏ không có? Bọn họ cũng là NPC vấn đề." Nói tới chỗ này, khối này 1 kiến thức điểm cũng giảng giải không sai biệt lắm, Diệp Hoa cuối cùng nói

"Cho nên nếu như có thể chứng minh P=NP, vậy đối với toàn bộ loài người cống hiến có thể to lắm, nói thí dụ như bên trong cơ thể prô-tê-in xếp phức tạp độ chính là NPC vấn đề, một khi nếu là chứng minh nó là cái P cười cái gì cười?"

Nhìn thấy liễu Linh đôi cười khúc khích, Diệp Hoa cố làm bản mặt trợn mắt nhìn nàng liếc mắt, cô gái nhỏ này, hắn coi như là đã nhìn ra, 8 học sinh bên trong là thuộc nàng lớn nhất da.

Ho nhẹ một cái, tiếp lấy trước mặt đề tài nói " cho nên chỉ cần chứng minh nó là P loại vấn đề, kia rất nhiều tật bệnh cũng có thể giải quyết dễ dàng, bệnh ung thư, bệnh AIDS những thứ này cũng đều không thành vấn đề. Nhưng là muốn chứng minh P=NP là tương đối không dễ dàng, bởi vì đầu tiên "Chứng minh P=NP" nó chính là một đạo đề đúng không? Hỏi như vậy đề tới, nó bản thân liền là một đạo NPC vấn đề "

Phảng phất cảm nhận được cái vấn đề này mang đến thật sâu ác ý cùng tràn đầy địch ý, cái vấn đề này quả nhiên là Tú, không hổ là đến nay cũng để cho toàn thế giới số học gia thúc thủ vô sách thế giới bảy đại số học vấn đề khó khăn đứng đầu.