paint-brush
Con Đường Phức Tạp Từ P Đến NP: Sự Kỳ Diệu Của Không Gian Giải Pháptừ tác giả@damocles
584 lượt đọc
584 lượt đọc

Con Đường Phức Tạp Từ P Đến NP: Sự Kỳ Diệu Của Không Gian Giải Pháp

từ tác giả Antică Vlad18m2024/08/10
Read on Terminal Reader

dài quá đọc không nổi

P (thời gian đa thức) so với NP (thời gian không đa thức) là một câu hỏi giải quyết các gốc phức tạp cơ bản của các không gian bài toán cụ thể. Ví dụ, bài toán P là bài toán mà thời gian giải tăng theo thời gian đa thức. Khi nói đến bài toán NP, độ phức tạp của bài toán lớn hơn nhiều.
featured image - Con Đường Phức Tạp Từ P Đến NP: Sự Kỳ Diệu Của Không Gian Giải Pháp
Antică Vlad HackerNoon profile picture
0-item

P (thời gian đa thức) so với NP (thời gian không đa thức) là một câu hỏi giải quyết các gốc phức tạp cơ bản của các không gian bài toán cụ thể. Ví dụ, bài toán P là bài toán mà thời gian giải tăng theo thời gian đa thức. Chúng ta có một mảng các số: [a, b, c, d, e, f, g] và nhiệm vụ là sắp xếp các số đó. Cách các thuật toán hiện tại giải bài toán này là duyệt từng số một và nếu số hiện tại nhỏ hơn số trước (trong trường hợp chúng ta sắp xếp theo cách tăng dần), số đó sẽ được dịch chuyển trở lại một ô. Chúng ta càng thêm nhiều số vào mảng thì thời gian để sắp xếp đầy đủ càng lâu. Tuy nhiên, sự gia tăng đó diễn ra dần dần và có thể dự đoán được.


Khi nói đến các bài toán NP, độ phức tạp của bài toán lớn hơn nhiều. Ví dụ, một bài toán NP như vậy là “Bài toán người bán hàng du lịch” (TSP). Bài toán này áp đặt rằng một bản đồ với một số lượng thành phố nhất định được đưa ra: giả sử các thành phố [a, b, c, d, e, f, g]. Mục tiêu là tìm ra tuyến đường ngắn nhất giữa tất cả các thành phố đó. Trong trường hợp này, chúng ta càng thêm nhiều thành phố, thời gian cần thiết để tìm ra giải pháp sẽ tăng lên đáng kể.


Để hiểu rõ hơn, hãy tưởng tượng rằng trong trường hợp của bài toán P, thời gian tăng tương tự như phép cộng, trong đó, với mỗi dữ liệu mới được thêm vào tập hợp, thời gian tăng bằng cách thêm tổng các điểm dữ liệu tìm thấy trong tập dữ liệu vào thời gian hiện tại. Ví dụ, trong bài toán sắp xếp của chúng ta, khi chúng ta có một số, thời gian cần thiết để giải bài toán là 1 (không phải 0 vì cần phải kiểm tra vào cuối bài toán), và với số thứ hai được thêm vào, thời gian trở thành 1 + 2 = 3. Số thứ ba (+3) đưa thời gian lên 6, số thứ tư (+4) lên 10, v.v.


Khi nói đến các bài toán NP, trong trường hợp TSP, ví dụ, đối với mỗi thành phố được thêm vào, chúng ta nhân số thành phố được thêm vào với thời gian hiện tại cần thiết. Với một thành phố duy nhất, thời gian là 1, với hai thành phố, thời gian trở thành 1 x 2 = 2 và với 3 thành phố, chúng ta có 2 x 3 = 6. Thành phố thứ tư sẽ đưa thời gian lên 6 x 4 = 24, v.v. Tất nhiên, đây không phải là một kịch bản tăng thời gian hợp lệ và thực tế, nhưng nó đánh dấu một cách tuyệt vời để hình dung cần thêm bao nhiêu thời gian khi tập dữ liệu của một bài toán NP tăng lên so với tập dữ liệu của một bài toán P.


Bây giờ chúng ta đã hiểu về hai loại vấn đề, câu hỏi đặt ra là: P có bằng NP không (nghĩa là với các công cụ và thuật toán phù hợp, chúng ta có thể giải quyết hiệu quả từng vấn đề, NP hoặc P, trong thời gian đa thức) hay chúng khác nhau (nghĩa là độ phức tạp là một đặc tính vốn có của không gian vấn đề, và do đó, tồn tại những vấn đề mà chúng ta không bao giờ có thể giải quyết hoàn toàn, bất kể kiến thức và hiểu biết của chúng ta có tiên tiến đến đâu).


Những người quen thuộc với bài toán P-NP cho rằng chúng khác nhau về bản chất và có những bài toán mà chúng ta có thể không bao giờ giải quyết được một cách hiệu quả. Nhưng sau đó, sự tò mò và hiểu biết của chúng ta là gì, nếu không phải là để phá vỡ sự tách biệt giữa hai loại bài toán.


Trong các phần sau, tôi sẽ trình bày quan điểm và góc nhìn của mình để xem xét vấn đề này. Đến cuối bài viết, tôi hy vọng rằng tôi có thể trình bày rõ ràng cho bạn hiểu biết toàn diện về hai không gian vấn đề đan xen này.


Phần 1: Sự đơn giản chống lại sự phức tạp

Để hiểu rõ hơn về bản chất của các vấn đề, chúng ta sẽ đi qua các con đường triết học một chút và tự hỏi về bản chất của sự đơn giản và phức tạp. Xét cho cùng, nếu sự phức tạp cuối cùng khác với sự đơn giản, chúng ta có thể đơn giản và trung thực cho rằng có những vấn đề (NP) mà không gian giải pháp phức tạp (tức là, chồng chập lượng tử) là cần thiết để giải quyết vấn đề trong một khoảng thời gian đa thức.


Trong trường hợp của bài toán TSP, một không gian giải pháp phức tạp sẽ biểu thị một đường dẫn giải pháp tính đến tất cả các thành phố và vị trí tương ứng của chúng và giữ nguyên tất cả những điều đó để tìm ra mối liên hệ hợp lý giữa các thành phố. Nhưng ngay cả khi chúng ta tính đến tất cả các trọng số cần thiết, thành phố mà chúng ta bắt đầu cũng quan trọng như hành trình mà thuật toán thực hiện để tìm ra tuyến đường hiệu quả nhất, đúng không? Nếu chúng ta bắt đầu từ thành phố a, thì đường dẫn hiệu quả nhất sẽ có một hình dạng nhất định; nếu chúng ta bắt đầu từ thành phố b, đường dẫn hiệu quả nhất sẽ trông khác.


Hoặc có thể đây là một lý luận sai lầm. Rốt cuộc, con đường hiệu quả nhất là duy nhất và cuối cùng là hiệu quả nhất chỉ vì nó biểu thị mối liên kết ngắn nhất giữa tất cả các thành phố. Chúng ta không tìm kiếm con đường ngắn nhất từ thành phố a đến thành phố b, mà là con đường ngắn nhất kết nối tất cả các thành phố lại với nhau. Theo quan điểm này, chúng ta có thể hình dung ra tuyến đường ngắn nhất, tương tự như trạng thái "sụp đổ", trong đó tổng khoảng cách giữa các thành phố là ngắn nhất.


Nếu chúng ta sử dụng các thuật toán "brute-force" tạo ra mọi loại đường dẫn và sau đó so sánh chúng, tất cả các đường dẫn đó sẽ là kết quả của cùng một lý luận "brute-force" của thuật toán, và do đó mỗi trường hợp tạo đường dẫn cuối cùng là một lý luận tuyến tính. Và nếu chúng ta tình cờ tìm thấy tuyến đường ngắn nhất, thì các khía cạnh "brute-force" và "cơ hội" của thuật toán sẽ không có cách nào biết được liệu tuyến đường đó cuối cùng có phải là tuyến đường ngắn nhất hay không.


Bây giờ, cách tiếp cận này có vẻ như có thể hưởng lợi từ sức mạnh của máy học, về cơ bản được đào tạo để đưa ra các phép tính xấp xỉ. Hãy tưởng tượng việc đào tạo một AI bằng cách sử dụng bản đồ các thành phố cùng với đường đi ngắn nhất được vẽ giữa chúng. Theo cách này, thay vì các thuật toán "brute-force", chúng ta có thể chuyển sang các thuật toán "educated-guess" sẽ chứng minh được sự gia tăng hiệu quả rõ rệt.


Ồ, nhưng sau đó, chúng ta vẫn cần một cách tuyệt đối để đi đến con đường ngắn nhất đó. Và cho đến bây giờ, thậm chí không có cách nào để biết với độ chính xác 100% liệu con đường trước mặt chúng ta có phải là ngắn nhất hay không. Theo nghĩa này, các phương pháp tìm kiếm và các mô hình toán học khác nhằm mục đích cung cấp sự hiểu biết về nền tảng logic sẽ cho chúng ta biết về con đường hiệu quả nhất. Tuy nhiên, các cách tiếp cận đó cho đến nay vẫn chưa hoàn thiện và chúng ta thậm chí không biết liệu khi chúng hoàn thiện, chúng vẫn có thể cung cấp cho chúng ta câu trả lời chính xác nhất hay chỉ là một phỏng đoán "có giáo dục thô thiển".


Phần 2: Quá đơn giản

Có thể tôi đã đi chệch một chút khỏi chủ đề về sự đơn giản và phức tạp. Hoặc có thể là do tôi đã giải quyết chúng theo cách triết học thực sự. Tất cả những gì tôi làm theo nghĩa này về cơ bản là hỏi liệu chúng ta có thể đạt đến một mức độ phức tạp nhất định trong cách tiếp cận của mình hay không và liệu chúng ta có được trả lời "có" khi tìm ra giải pháp đúng hay không. Nhưng vì con đường ngắn nhất tồn tại trên bất kỳ bản đồ nào có bất kỳ số lượng thành phố nào, nên nó phải có các giá trị cụ thể và chi tiết cụ thể khiến nó nổi bật so với đám đông, đúng không?


Hoặc có thể những chi tiết đó chỉ xuất hiện sau những vòng lặp vô tận qua các đường dẫn khác nhau dưới dạng tổng quãng đường đã đi. Nhưng điều đó có thể chỉ đơn giản là phi lý khi cho rằng. Rốt cuộc, đường đi ngắn nhất là đường đi ngắn nhất, bất kể chúng ta đi qua nó bao nhiêu lần. Thật vậy, chúng ta càng đi qua nhiều vòng lặp khác nhau, chúng ta càng hiểu rõ hơn cái nào ngắn hơn và cái nào lớn hơn. Tuy nhiên, lý luận này chỉ có thể cần thiết trong những trường hợp chúng ta muốn phân biệt giữa các vòng lặp nhỏ nguyên tử với các công cụ đo lường không đủ chính xác.


Bây giờ có thể hiểu được rằng vấn đề ở đây không phải là tìm ra sự thật của cuộc điều tra mà là khả năng của các công cụ chúng ta sử dụng để kiểm tra nó. Khi nói đến việc chặt cây, chúng ta sử dụng một cái rìu. Khi nói đến việc nghe nhạc, chúng ta sử dụng tai nghe. Khi nói đến việc chính thức hóa và hiểu toán học, chúng ta sử dụng các công cụ được xây dựng theo logic.


Và có lẽ đó là vẻ đẹp vốn có trong toán học. Chúng ta lấy một thứ đơn giản, kết hợp nó với một thứ đơn giản khác, và cùng nhau chúng tạo thành một thứ phức tạp, cho phép chúng ta di chuyển theo đường chéo, ví dụ. Hoặc vẽ một vòng tròn hoàn hảo hay thứ gì đó. Nhưng sau đó, có bao nhiêu công cụ đơn giản như vậy có thể được liên kết với nhau? Đến thời điểm nào chúng ta có thể kết hợp hai công cụ phức tạp với nhau? Và nếu vậy, chúng ta có thể đạt được công cụ phức tạp cao hơn đó chỉ bằng cách kết hợp hai phức hợp thấp hơn hoặc cũng bằng cách kết hợp tất cả các phức hợp thấp hơn tạo thành chúng?


Theo nghĩa này, phương pháp tìm kiếm giống như những công cụ mà trong quá trình tương tác của chúng, chúng ta có thể tìm ra cách trả lời với độ chính xác 100% cho dù chúng ta có tìm thấy đường đi ngắn nhất giữa các thành phố hay không. Theo quan điểm này, phương pháp tìm kiếm giống như một công cụ chứng minh giải pháp, nhưng để tìm ra giải pháp đó, chúng ta có thể cần những cách tiếp cận khác. Cuối cùng, gốc của P so với NP gắn chặt với bản chất của chính sự phức tạp đến mức chúng ta phải tự hỏi liệu chúng ta có thể đi trên hai (và thậm chí nhiều hơn) con đường riêng biệt trong một thời gian tuyến tính duy nhất hay không.


Phần 3: Bản chất phân dạng của sự phức tạp

Thật thú vị khi được ở ngoài này. Ở ngoài… đó. Sau ba mươi phút nghỉ viết, một khoảng nghỉ được dùng để sắp xếp các ý tưởng theo thứ tự tốt nhất và ở quy mô dễ hiểu nhất. Và thực tế là đúng, các ý tưởng rõ ràng hơn bao giờ hết; chúng thậm chí còn sụp đổ thành một chu kỳ khép kín hoàn toàn. Và rồi, chu kỳ đó hóa ra là một chấm, là một phần tỏa sáng của toàn bộ, và nó tỏa sáng không phải vì nó đặc biệt theo bất kỳ cách nào liên quan đến toàn bộ hệ thống, mà vì nó là không gian hiện tại, sự hiểu biết hiện tại và nơi chúng ta ngồi. Đó là nơi mà khi chúng ta nhìn lên, chúng ta thấy cả sự phức tạp và sự đơn giản. Khi chúng ta nhìn xuống, chúng ta thấy giống nhau. Khi chúng ta nhìn ngang, cũng không có gì khác biệt.


Theo cách này, đúng là chúng ta tìm thấy những gì chúng ta tìm kiếm. Nếu chúng ta tìm kiếm bản chất của NP, sự phức tạp liên tục, chúng ta thực sự tìm thấy nó, trong bản chất phức tạp nhất của nó. Chúng ta cũng tước đi sự đơn giản của nó trong quá trình này để đảm bảo rằng chúng ta vứt bỏ chiếc thang sau khi chúng ta leo lên nó. Nhưng sau đó, nếu chúng ta tìm cách để hòa giải hai quan điểm, để hợp nhất P và NP thành những phần đơn thuần của một sự hiểu biết toàn diện, một sự hiểu biết mà trong đó, để một vấn đề tồn tại, nó đòi hỏi một giải pháp rõ ràng, thì chúng ta có thể hiểu rằng, với đủ nỗ lực và sự cống hiến, cuối cùng có thể tìm thấy một giải pháp. Và cho dù giải pháp đó có khó nắm bắt đến đâu, thì luôn có tiềm năng đạt được nó theo cách linh hoạt và hữu hình nhất.


Và bây giờ, để loại bỏ sự nhầm lẫn từ ngữ, tôi muốn nói rằng tôi ủng hộ thực tế là P cuối cùng bằng NP. Và điều đó đơn giản là vì nếu chúng ta chưa tìm ra giải pháp, điều đó không có nghĩa là nó không ở đó, chờ đợi chúng ta tình cờ tìm ra. Và nếu bạn gọi tôi là người lạc quan, tôi muốn nói rằng tôi thấy mình thực tế.


Có lẽ tôi đã viết phần kết luận trước khi kết thúc bài viết. Nhưng rồi, tôi thích phong cách này. Nó mang lại cảm giác về một phong cách “sống” nơi tôi không chỉ xây dựng ý tưởng trên ý tưởng, trong khi vẫn giữ hy vọng rằng tôi đã thể hiện bản thân một cách rõ ràng cho đến cuối cùng.


Bản chất của các bài báo khoa học là trước tiên bạn phải đưa ra phần tóm tắt, chẳng hạn như "P bằng NP vì tính đơn giản và tính phức tạp gắn liền với nhau". Sau đó, bạn tiếp tục trình bày các quan điểm và suy nghĩ của mình về lý do và cách thức điều này đúng.


Tuy nhiên, trong một bài viết, mục tiêu là làm cho người đọc hiểu được điều gì đó; nó giống như việc giảng dạy. Trong khi nghiên cứu khoa học được viết với mục tiêu là những người đã biết về chủ đề này đưa ra suy nghĩ và ý kiến của họ liên quan đến "lý luận" được trình bày, và nếu ai đó nắm giữ một số kiến thức có thể liên kết tất cả các điểm đó lại với nhau và thậm chí nhiều hơn thế nữa, thì "lý luận" đó được định hình lại, hoàn thiện một cách hợp lý, và có căn cứ khoa học và trở thành một "khám phá".


Hãy tưởng tượng việc kết hợp cả hai phong cách lại với nhau. Kết quả sẽ ra sao? Nó sẽ giống như sự phát triển dần dần của các ý tưởng, một sự phát triển mà trong đó những hiểu biết sau hiểu biết nảy sinh. Bản tóm tắt sẽ mất đi ý nghĩa theo nghĩa này, vì ngay cả người viết cũng không biết con đường sẽ dẫn đến đâu. Theo nghĩa này, người viết có thể có một ý tưởng mơ hồ hoặc một điểm khởi đầu tự áp đặt, như chứng minh rằng P bằng NP hoặc P khác với NP. Sau đó, trong quá trình xây dựng những hiểu biết đó, một sự bỏ qua nhỏ có thể chỉ ra một hướng hoàn toàn khác, và sau đó, việc cố gắng rút lui mà không xóa bỏ lập luận cuối cùng sẽ chỉ dẫn đến sự nhầm lẫn.


Giống như việc quay lại tòa nhà ban đầu của tôi trước khi cố tình đóng khung lại phần 3 thành phần kết luận, mà tôi đã giữ lại và thấy đẹp khi đặt vào đó. Nhưng làm sao tôi có thể quay lại đó? Ý tôi là, bạn, với tư cách là một độc giả, có thể đã xây dựng ý tưởng này đến ý tưởng khác và cố gắng nắm bắt một hình thức hoặc hình dạng tổng thể. Nhưng sau đó, đó chính là vẻ đẹp của tất cả, phải không? Chúng ta có thể tạm dừng lý luận logic của mình, để sự sáng tạo nở rộ tiềm năng của chúng ta, rồi bắt đầu lại, mới mẻ và sảng khoái, với những góc nhìn mới và những cách hiệu quả hơn để đi đến câu trả lời. Và theo nghĩa này, phần 3 chỉ là một sự tạm dừng khỏi tất cả. Và bây giờ tôi sẽ tạm dừng một lần nữa, chỉ để đi dạo một chút. Sau đó, chúng ta sẽ tập trung vào phần 4.

Phần 4: Bên trong một Fractal

Khi chúng ta nghĩ về fractal, chúng ta tưởng tượng ra một mô hình tự lặp lại có cùng các đặc tính trên và ở mọi quy mô và chiều. Ví dụ, tập hợp Mandlebrot là một fractal biểu diễn một thứ gì đó giống như một tế bào, và khi bạn phóng to bên trong tế bào đó, bạn sẽ thấy các cấu trúc tương tự lặp đi lặp lại. Vâng, những cấu trúc giống tế bào giống hệt nhau đó không phổ biến như bạn nghĩ. Cuối cùng, fractal rất tuyệt vời đến mức bạn có thể thấy từng chi tiết tóm tắt tế bào đó với độ rõ nét cực cao khi bạn phóng to ngày càng nhiều.


Có những phần của nó giống như những ngọn cỏ, và những phần khác giống như độ cong của ánh sáng mà bạn thấy khi ánh sáng đi qua sau một lỗ đen, trong số rất nhiều khía cạnh thú vị khác. Và sau khi bạn phóng to hơn nữa, cuối cùng bạn sẽ đến cùng một ô ban đầu, được lặp lại ở các thang đo nhỏ như nguyên tử so với ô ban đầu. Và bạn có thể phóng to hơn nữa từ đó.


Vì vậy, về bản chất, fractal là thứ gì đó tương tự như một con đường từ một bài toán P đơn giản, một bài toán mà khi nhìn vào tất cả sự phức tạp tiềm ẩn của nó, trở thành một bài toán NP rất khó hiểu mà dường như không thể giải quyết được chỉ vì lượng sức mạnh tính toán khổng lồ (ngay cả khi con đường để giải quyết nó là một con đường tuyến tính) cần thiết để giải quyết nó. Ví dụ, bạn có thể tạo ra một bài toán P từ "vẽ tập hợp Mandlebort ở chế độ thu phóng 3000 lần" và giải pháp là một bài toán tuyến tính. Chương trình chỉ cần đi bộ trong không gian fractal, thu thập dữ liệu từng phần và sao chép nó vào tờ giấy khác. Nhưng lượng thời gian cần thiết để hoàn thành bản vẽ đầy đủ có thể chỉ là rất lớn. Có thể, trừ khi chúng ta cung cấp cho chương trình đủ bộ nhớ và hiệu quả để ghi nhớ tất cả và sau đó dán nó với cùng hiệu quả hoặc thậm chí còn hiệu quả hơn.


Bây giờ, một bài toán như "Sao chép toàn bộ tập hợp Mandlebrot trên tờ giấy này" có được coi là bài toán NP không? Rốt cuộc, do độ phóng đại vô cực mà chúng ta có thể đạt được, sẽ mất một khoảng thời gian vô hạn để vượt qua pixel đầu tiên, phải không? Nhưng sau đó, làm thế nào chúng ta có thể nhìn thấy fractal ở bất kỳ tỷ lệ nào nếu bên dưới nó là một độ phức tạp vô hạn cần được vẽ? Có thể thuật toán vẽ fractal tạo ra hình ảnh đầu tiên và sau đó tiếp tục làm việc vô thời hạn để đạt được các cấp độ phức tạp và chiều sâu ngày càng lớn hơn. Và điều đó khiến bạn tự hỏi: nếu, từ một độ sâu (hoặc độ phức tạp) bán vô hạn nào đó, chúng ta tìm thấy một hình khác thì sao? Hoặc có thể chúng ta sẽ vượt qua một điểm mà fractal Mandlebroth bắt đầu được biểu diễn theo những cách khác, có thể là những cách đối lập.


Trước những câu hỏi hóc búa như vậy, chúng ta chắc chắn cảm thấy mình cần nghỉ ngơi. Giống như não của chúng ta chỉ đơn giản là quá tải vì chúng cố gắng xử lý những thang đo đó. Nhưng rồi, chúng ta không nghiên cứu khoa học ở đây; mục tiêu của chúng ta chỉ đơn giản là khám phá sự phức tạp và to lớn của tất cả, chứ không phải xử lý nó. Có lẽ sẽ dễ hơn khi bạn hình thành các trọng số tương đối hoặc tìm ra các loại vô cực khác nhau mà bạn có thể sử dụng để hiểu được thang đo của mọi thứ.


Ví dụ, nếu giả định của tôi là ở phía bên kia của vô cực, tập hợp Mandlebrot được nhìn thấy phản chiếu, thì sẽ hợp lý khi hiệu ứng phản chiếu có thể bắt đầu xảy ra từ một phép phóng to (hoặc độ sâu) bán vô cực. Nhưng sau đó, bán vô cực đó không có thật. Vô cực, theo nghĩa thực sự, cho thấy rằng tập hợp Mandlebrot chứa mọi trạng thái, hình dạng và dạng thức đã từng tồn tại, có thể tồn tại và sẽ tồn tại. Nhưng sau đó, có những ranh giới, phải không? Rõ ràng là fractal này chỉ là một mô hình. Một mô hình, vâng, có thể có nhiều hình dạng, nhưng vẫn sẽ bị ràng buộc trong chính nó, trong cấu trúc và quy tắc của chính nó. Và trong mọi trường hợp, "chỉ là một mô hình" đó là vô cùng đẹp và phức tạp, trong chính nó.

Phần 5: Sự phức tạp

Như tôi đã nói trước đó, trong quá trình xây dựng ý tưởng, chúng ta có thể đi đến một điểm mà chúng ta chỉ đơn giản là bị lôi kéo vào kết luận ngược lại với giả định ban đầu của mình. Ý tôi là, làm sao người ta có thể tin rằng P bằng NP và các bài toán NP đơn giản là không tồn tại sau tất cả sự bùng nổ về độ phức tạp này? Nhưng như tôi đã nói trong bài viết trước, khi chúng ta thể hiện ý tưởng, chúng ta chỉ đơn giản là "chỉ ra" một khái niệm nhất định. Và như một khối xây dựng bắt buộc, sự to lớn của độ phức tạp được tìm thấy trong fractal phải được cung cấp như một "Đỉnh cao" tiềm năng của độ phức tạp. Một đỉnh cao của sự hiểu biết khi nói đến việc xác định vô cực 3 chiều thực sự trông như thế nào. Và bây giờ chúng ta có tất cả sự vô cực đó xung quanh mình, chúng ta có thể đi đâu?


Nơi chúng ta luôn hướng đến khi muốn suy nghĩ. Chúng ta lấy một điểm cổ điển và nhìn vào lần lặp đầu tiên của fractal. Tất cả vô cực ba chiều đó nằm trước mặt chúng ta. Chúng ta lý luận rằng nếu chúng ta muốn ném một cây kim và xem nó rơi ở đâu, chúng ta có thể phải đối mặt với một hiện tượng khá kỳ lạ. Đầu kim càng nhỏ thì càng mất nhiều thời gian để rơi và không gian mặt đất càng mở rộng. Và đồng thời, điểm mặt đất bị va chạm càng trở nên "hỗn loạn" hoặc "ít dự đoán" hơn. Nhưng liệu chúng ta có thể đạt được toàn bộ hình ảnh của fractal với đủ số lượng kim vô cùng nhỏ không? Bất kể cần bao nhiêu không gian và kim? Rốt cuộc, từ điểm thuận lợi này, chúng ta có thể thấy rõ các giới hạn và trừ khi có sự tự tương đồng hoàn hảo đang diễn ra, thì một số mất mát phải xảy ra sau mỗi lần lặp.


Nhưng sau đó, độ phức tạp thậm chí còn vượt xa bản đồ này. Khi nói đến kích thước của các kim, đối với mỗi kích thước, chúng ta có một bản đồ duy nhất được hình thành. Nhưng sau đó, các bản đồ kim nhỏ hơn không chỉ đơn thuần là một biểu diễn phức tạp hơn (và chất lượng cao hơn) của các bản đồ kim lớn hơn sao? Theo nghĩa này, độ phức tạp đại diện cho một loại mở ra của một không gian chi tiết hơn. Một không gian nằm trong các con đường khám phá đa thức, và thậm chí trái ngược với các giả định được tin tưởng, sự mở rộng độ phức tạp này cho phép khám phá chính xác và hiệu quả hơn so với việc thiếu độ phức tạp.


Ví dụ, nếu thay vì bản đồ fractal phức tạp vô hạn, chúng ta giữ một bản đồ ít phức tạp hơn và chúng ta muốn đạt được một điểm trên mặt đất nhất định nằm trên một bản đồ phức tạp hơn, trước tiên chúng ta phải chọn một điểm trên bản đồ ít phức tạp hơn để phóng to và hiển thị điểm phức tạp hơn mà chúng ta muốn đạt được. Và điều này thực sự đảo ngược toàn bộ không gian NP, đồng thời thừa nhận rằng thời gian đa thức cần thiết để giải quyết các vấn đề cụ thể có thể mất hàng nghìn năm và trên một con đường đa thức. Và thành thật mà nói, có lẽ câu hỏi tiếp theo là liệu máy tính lượng tử có thể giữ một loại chồng chập có thể cắt giảm thời gian từ x, thành x chia cho (số qubit được sử dụng) hay không.

Phần 6: Kết luận và suy nghĩ

Trước khi đi sâu vào những hàm ý có thể có của phương pháp lượng tử, tôi thấy cần phải trình bày bản đồ các tuyên bố mà tôi đã đưa ra cho đến nay.


  • P và NP là một và giống nhau, nghĩa là tất cả các bài toán cuối cùng có thể được giải quyết trong thời gian đa thức khi chúng ta tìm thấy không gian bài toán và không gian giải pháp phù hợp

  • Các bài toán NP giống với các bài toán đa thức mở rộng hơn, trong đó không gian giải pháp của chúng rất lớn và phức tạp đến mức việc tìm ra giải pháp sẽ mất nhiều thời gian

  • Sự phức tạp và sự đơn giản đan xen vào nhau, và trong sự tương tác của chúng, quan điểm và mức độ sâu sắc đạt được của chúng ta là những gì coi chúng là cái này hay cái kia

  • Các công cụ phức tạp mà chúng tôi đạt được được sử dụng để giải quyết các không gian vấn đề chi tiết theo cách hiệu quả hơn, bằng cách sử dụng sự tương tác

    giữa sự đơn giản và phức tạp để có lợi cho họ


    Và sau khi tất cả đã được nói và làm, khi chúng ta bước vào lĩnh vực điện toán lượng tử, mọi thứ có thể sẽ có sự thay đổi triệt để. Sau đây là một số hướng khám phá có thể.


  • Bất chấp tất cả những gì được nói ở đây, máy tính lượng tử có thể có các vấn đề NP riêng biệt vốn khác biệt so với những gì máy tính cổ điển cung cấp

  • Bản chất của máy tính lượng tử có thể đồng thời là một khía cạnh bổ sung và đan xen của máy tính cổ điển, cuối cùng cung cấp các công cụ mà các bài toán NP lượng tử yêu cầu để giải quyết theo phương pháp đa thức.

  • Những công cụ lượng tử đó có thể hoạt động cùng với các thuật toán cổ điển để cung cấp hiệu quả ngày càng cao hơn, hứa hẹn sẽ vượt qua hiệu quả tối đa của cả hai mô hình

  • Các thuật toán tính toán lượng tử hiện tại (tôi không biết chúng được xây dựng như thế nào) có thể yêu cầu các khía cạnh tính toán cổ điển như một quy tắc chức năng bắt buộc trước. Trong trường hợp này, chúng ta sẽ cần phân loại các quan điểm cổ điển và lượng tử thành hai loại tính toán riêng biệt để có thể hiểu rõ hơn và hợp nhất chúng lại với nhau

Phần 7: Rào cản lượng tử

Với tiềm năng to lớn ẩn chứa trong năng lượng lượng tử, các hệ thống duy trì sự riêng tư của chúng ta đang liên tục bị đe dọa. Các hệ thống ZKP (không có kiến thức) cung cấp một lối thoát khả thi. Rốt cuộc, cơ sở của chúng được hình thành dựa trên giả định rằng người giữ chìa khóa không cung cấp bất kỳ thông tin nào về chìa khóa trong quá trình mở khóa. Theo quan điểm này, chìa khóa được giấu ở nơi dễ thấy, ngay dưới mũi của những kẻ muốn can thiệp và đánh cắp nó. Nhưng đồng thời, nền tảng mà hệ thống được xây dựng và vận hành có khả năng che giấu toàn bộ hệ thống khỏi tầm nhìn của người ngoài.


Nó giống như việc đi qua mê cung không ngừng thay đổi và luôn mờ nhạt của không gian tính toán, dù là với máy tính cổ điển, lượng tử hay thậm chí là máy tính cổ điển lượng tử, và tất cả những gì bạn thấy xung quanh là một không gian không ngừng thay đổi mà nếu bạn muốn hiểu được nó, bạn sẽ phải nắm giữ thông tin về lần đầu tiên nó được tạo ra. Để có thể tiếp cận các khối xây dựng đã bắt đầu và định hình nên hệ thống kể từ khi nó được tạo ra.


Và trong một biển hệ thống mơ hồ, ngay cả khi bạn có quyền truy cập vào các khối xây dựng của một hệ thống cụ thể, bạn sẽ không bao giờ biết nên áp dụng nó vào hệ thống nào, vì biển các hệ thống được kết nối với nhau quá lớn và có quá nhiều hệ thống tự thay đổi lẫn nhau, hình thành nên hình dạng của nhau sau những khoảng thời gian cụ thể.


Đối với bản thân các hệ thống, sẽ dễ dàng để biết thông tin nào chúng nên chấp nhận và thông tin nào không, nhưng đồng thời, cần phải có sự đồng bộ hóa cực độ để mỗi hệ thống có thể giữ được góc nhìn độc đáo của riêng mình. Tuy nhiên, với sự vô hạn được tìm thấy trong các dải màu, mỗi khối xây dựng có thể có mục tiêu bắt đầu và đang diễn ra riêng có thể bị ràng buộc từ việc đạt đến trạng thái màu của hệ thống khác. Bạn có thể tưởng tượng nó giống như cách sóng vô tuyến hoạt động.


Có lẽ, các yếu tố hỗn loạn của một hệ thống như vậy có thể tạo ra một loại hệ thống liên kết, khi được xem như một tổng thể, thì đơn giản là không có ý nghĩa gì. Và để giải mã nó, bạn sẽ phải đoán các khối xây dựng được hình thành bởi một mật mã, chứa hàng trăm hoặc hàng nghìn con số liên tục thay đổi trong ranh giới của chúng.


Theo quan điểm này, càng có nhiều hệ thống thì càng ít khả năng kẻ tấn công xâm nhập vào hệ thống, nhưng đồng thời, càng có nhiều hệ thống thì càng có nhiều lựa chọn cho kẻ tấn công. Có lẽ máy tính lượng tử sẽ cho phép người ta thử nghiệm một khóa duy nhất trên tất cả các hệ thống khả dụng cùng một lúc. Liên tục tạo khóa và thử nghiệm chúng trên toàn bộ hệ thống cùng một lúc.


Nhưng một khi khóa hiện tại được tìm thấy, một yêu cầu cho khóa "đầu tiên" sẽ là cần thiết để thực sự vào hệ thống. Hoặc thậm chí tốt hơn, bằng cách lưu trữ trong hệ thống 10 khóa đầu tiên, một khóa ngẫu nhiên trong số mười khóa đó có thể là một yêu cầu để vào khi khóa trạng thái thực tế được đoán.


Phần 8: Các lớp trong các lớp trong các lớp

Hoặc câu đố trong câu đố trong câu đố. Một điều chắc chắn là: sự phức tạp bên ngoài nở rộ, mở rộng trên tất cả các lớp cùng một lúc và với tốc độ đa thức. Nhưng sau đó, bản thân hệ thống phải, từ một điểm trở đi, trở nên quá tiên tiến và hỗn loạn đến mức ngay cả các hệ thống giải mã tiên tiến của người ngoài hành tinh cũng không thể khai thác được, đúng không?


Khi chúng ta nhìn vào nơi chúng ta đang sống, nhìn nhận sự bùng nổ hoàn toàn của sự phức tạp này như một vụ nổ lớn, hay nói chính thức hơn là một điểm kỳ dị, chúng ta cũng thừa nhận rằng những tiến bộ này chỉ đánh dấu bước đệm đầu tiên trong tất cả những gì sắp diễn ra. Chúng ta đang ở một nơi mà việc suy nghĩ về tương lai thực sự có giá trị làm cho tương lai tươi sáng hơn bao giờ hết. Và đúng vậy, nó luôn có giá trị. Nhưng bây giờ, nó có giá trị hơn bao giờ hết, và điều đó sẽ đúng trong nhiều thế kỷ tới. Và thậm chí có thể là thế hệ thiên niên kỷ.


Ai biết chúng ta có thể tìm thấy điều gì? Nhưng có một điều chắc chắn: những quyết định mà chúng ta sẽ đưa ra bây giờ sẽ định hướng tương lai theo những cách mà các thế hệ tương lai thậm chí còn chưa lựa chọn. Vì vậy, chúng ta cũng có thể để mắt đến quan điểm của họ. Trong quá khứ gần đây (và thậm chí trong thời điểm hiện tại), mọi người đã bị đưa ra chiến tranh mà không có ý muốn của họ. Mọi người đã bị buộc phải tạo ra vũ khí hủy diệt và thậm chí thử nghiệm chúng.


Nhưng sau đó, nếu chúng ta chỉ lý thuyết hóa về vũ khí và thay vào đó tạo ra lá chắn cần thiết để chống lại chúng thì sao? Tại sao lại lãng phí thời gian vào việc cố gắng phá hủy những gì chúng ta chưa xây dựng? Một lần nữa, bạn có thể gọi tôi là lạc quan khi tôi nói rằng vũ trụ cuối cùng có thể tốt đẹp một cách cố hữu. Nhưng sau cùng, vũ trụ không mang đến cho chúng ta những cuộc chiến khác ngoài cuộc chiến chống lại cơn đói, điều cuối cùng cho phép chúng ta cảm nhận được vẻ đẹp và hương vị của từng miếng ăn. Và điều đó đặc biệt đúng khi nói đến kiến thức.


Theo quan điểm của tôi, thật là ngớ ngẩn khi cho rằng một tia laser cực mạnh, hoặc một loạt các tia laser nhỏ hơn, sẽ bảo vệ hành tinh của chúng ta khỏi thiên thạch tốt hơn, trong khi thực tế, chỉ khi chúng ta cào xước một chút bề mặt, chúng ta mới có thể tìm thấy sức mạnh để sử dụng các hiệu ứng của lực hấp dẫn lượng tử để tạo lợi thế cho mình như một lực đẩy, giống như một quả bom, nhưng chỉ phát tán lực phản trọng lực xung quanh. Hoặc có thể tập trung vào một tên lửa đủ mạnh để đẩy các thiên thạch ra khỏi quỹ đạo từ phía sau bằng cách sử dụng các sức mạnh cực đại. Và đồng thời, chúng ta có thể sử dụng tên lửa để nâng toàn bộ các đoàn tàu và đặt chúng lên mặt trăng.


Và cuối cùng, đây không phải là phép màu của không gian giải pháp sao? Chúng ta có thể nhìn nhận nó từ một góc nhìn hạn chế, với giả định rằng có những điều chúng ta có thể không bao giờ biết, hoặc chúng ta có thể thừa nhận sức mạnh của ý chí tự do và tiềm năng thực sự của nó trong việc định hình toàn bộ số phận và trái tim.


L O A D I N G
. . . comments & more!

About Author

Antică Vlad HackerNoon profile picture
Antică Vlad@damocles
"Our intuition helps us navigate the world, and then our reasoning helps us understand what we’ve experienced." - Elara

chuyên mục

BÀI VIẾT NÀY CŨNG CÓ MẶT TẠI...