Hậu quả của việc nói một Máy Turing không xác định có thể giải quyết NP trong thời gian đa thức là gì?

Question

những ngày này tôi đã nghiên cứu về vấn đề NP, tính phức tạp và lý thuyết tính toán. Tôi tin rằng cuối cùng tôi đã nắm được các khái niệm về Máy Turing, nhưng tôi có một vài nghi ngờ.

tôi có thể chấp nhận rằng một máy Turing không xác định có một số tùy chọn về những gì để làm cho một nhà nước nhất định và biểu tượng được đọc và rằng nó sẽ luôn luôn chọn lựa chọn tốt nhất, như đã nói bởi wikipedia

thế nào NTM có biết "hành động nào trong số những hành động này cần thực hiện không? Có hai cách cách để xem. Một là để nói rằng máy là "may mắn nhất có thể đoán"; nó luôn chọn chuyển tiếp mà cuối cùng dẫn đến trạng thái chấp nhận, nếu có quá trình chuyển đổi . Cách khác là tưởng tượng rằng máy "chi nhánh" thành nhiều bản sao , mỗi bản theo sau một trong các chuyển đổi có thể là . Trong khi đó, DTM có một "đường dẫn tính toán" duy nhất mà nó theo sau, NTM có một cây tính toán ". Nếu bất kỳ chi nhánh nào của thì cây bị tạm dừng với điều kiện "chấp nhận" , chúng tôi nói rằng NTM chấp nhận đầu vào .

Điều tôi không thể hiểu được, vì đây là một máy ảo, chúng ta có được gì khi nói rằng nó có thể giải quyết các vấn đề NP trong thời gian đa thức? Ý tôi là, tôi cũng có thể giả thuyết về một cỗ máy phép thuật giải quyết các vấn đề NP trong O (1), tôi có thể đạt được điều gì từ nó nếu nó không bao giờ tồn tại?

Xin cảm ơn trước.

Answer 1

Máy Turing không xác định là một khái niệm khó nắm bắt. Hãy thử một số quan điểm khác:

1. Thay vì chạy một máy Turing huyền diệu đó là guesser may mắn nhất có thể, chạy một thậm chí huyền diệu hơn meta-máy mà thiết lập vô số đoán ngẫu nhiên máy Turing độc lập trong vũ trụ song song. Mỗi chuỗi dự đoán có thể được thực hiện trong một số vũ trụ. Nếu trong ít nhất một trong các vũ trụ, máy dừng lại và chấp nhận đầu vào, điều đó là đủ: trường hợp vấn đề được chấp nhận bởi máy meta đã thiết lập các vũ trụ song song này. Nếu trong tất cả các vũ trụ máy từ chối hoặc không dừng lại, thì máy meta sẽ loại bỏ cá thể đó.

2. Thay vì bất kỳ loại phỏng đoán hay phân nhánh nào, hãy nghĩ đến một người cố gắng thuyết phục người khác rằng cá thể đó phải được chấp nhận. Người đầu tiên cung cấp tập các lựa chọn được thực hiện bởi máy Turing không xác định, và người thứ hai kiểm tra xem máy có chấp nhận đầu vào với các lựa chọn đó hay không. Nếu có, người thứ hai bị thuyết phục; nếu không, người đầu tiên đã thất bại (có thể là do cá thể không thể được chấp nhận với bất kỳ chuỗi các lựa chọn nào, hoặc vì người đầu tiên chọn một chuỗi các lựa chọn kém).

3. Quên máy Turing. Một vấn đề là trong NP nếu nó có thể được mô tả bởi một công thức trong tồn tại second-order logic. Tức là, bạn có logic mệnh đề đơn giản vani, cho phép bất kỳ số lượng định lượng nào trên các biến mệnh đề, và cho phép tacking ở các số lượng tồn tại đầu tiên trên các tập hợp, các quan hệ và các hàm.Ví dụ, graph three-colorability có thể được mô tả bằng một công thức mà bắt đầu với định lượng hiện sinh qua màu sắc (bộ nút):

   ∃ R ∃ G ∃ B

   Mỗi nút phải được tô màu:

   ∃ R ∃ G ∃ B (& forall; x (R (x) ∨ G (x) ∨ B (x)))

   và không có hai nút liền kề có thể có cùng một màu sắc – gọi mối quan hệ cạnh E:

   ∃ R ∃ G ∃ B (& forall; x (R (x) ∨ G (x) ∨ B (x))) ∧ (& forall; x, y ¬ (E (x, y) ∧ ((R (x) ∧ R (y)) ∨ (G (x) ∧ G (y)) ∨ (B (x) ∧ B (y)))))

   Các định lượng hiện sinh qua các biến thứ hai-thứ tự giống như một máy Turing không xác định làm cho dự đoán hoàn hảo. Nếu bạn muốn thuyết phục ai đó rằng công thức ∃ X (...) là đúng, bạn có thể bắt đầu bằng cách cho giá trị X. Đó là NTM đa thức và các công thức này không chỉ giống "nhưng" thực sự tương đương với định lý Fagin, bắt đầu lĩnh vực descriptive complexity: các lớp phức tạp được đặc trưng không phải bởi các máy Turing mà bởi các lớp công thức logic.

Bạn cũng nói

tôi cũng có thể đưa ra giả thuyết của một máy huyền diệu mà giải quyết vấn đề NP trong thời gian O (1)

Vâng, bạn có thể. Chúng được gọi là oracle machines (không liên quan đến DBMS) và chúng mang lại kết quả thú vị trong lý thuyết phức tạp. Ví dụ, định lý Solovay của Baker – Gill – Solovay cho biết có các oracles A và B sao cho các máy Turing có quyền truy cập A, P = NP, nhưng đối với các máy Turing có quyền truy cập vào B, P ≠ NP. (A là một oracle rất mạnh mà làm cho không xác định không liên quan, định nghĩa của B là một chút phức tạp và liên quan đến một trick chéo.) Đây là một loại một kết quả meta: bất kỳ bằng chứng giải quyết P vs NP câu hỏi phải nhạy cảm đủ để định nghĩa một máy Turing mà nó không thành công khi bạn thêm một số loại oracles.

---

Giá trị của máy Turing không xác định là họ đưa ra một tương đối đơn giản, đặc tính của lớp phức tạp NP (và những người khác): thay vì cây tính toán hay bậc hai công thức hợp lý, bạn có thể nghĩ một máy tính gần như bình thường đã được (tương đối) hơi sửa đổi để nó có thể thực hiện các dự đoán hoàn hảo.

Answer 2

Những gì bạn đạt được từ đó là bạn có thể chứng minh rằng một vấn đề nằm trong NP bằng cách chứng minh rằng nó có thể được giải quyết bằng NTM trong thời gian đa thức.

Nói cách khác, bạn có thể sử dụng NTM để tìm hiểu xem một vấn đề cụ thể có trong NP hay không.

Answer 3

Từ Wikipedia tiếng Hebrew - "NTM chủ yếu là công cụ để suy nghĩ và không thể triển khai thực hiện máy như vậy". Bạn có thể thay thế thuật ngữ "NTM" bằng "Thuật toán ở mọi bước cố gắng tất cả các bước có thể" hoặc "Thuật toán ở mỗi bước chọn bước tiếp theo tốt nhất có thể" .. Và tôi nghĩ bạn hiểu phần còn lại. NTM chỉ ở đây để giúp chúng ta hình dung thuật toán như vậy. Bạn có thể xem here cách thức nó được cho là giúp bạn hình dung (tại câu trả lời của Pascal Cuoq).

Answer 4

Theo định nghĩa, NP là viết tắt của thời gian đa thức không xác định có thể được tra cứu trong Wikipedia.

Một hiện thân của máy Turing không xác định ngẫu nhiên chọn và kiểm tra (hoặc lắp ráp) giải pháp tiềm năng tiếp theo sẽ giải quyết vấn đề NP trong thời gian đa thức với một số xác suất (nó sẽ giải quyết được vấn đề trong thời gian nhiều lần) "người đoán có thể may mắn nhất").

Do đó, nói rằng NTM có thể giải quyết sự cố trong thời gian đa thức có hiệu quả có nghĩa là vấn đề đó nằm trong NP. Điều này một lần nữa tương đương với định nghĩa của lớp NP của các vấn đề.

Answer 5

Những gì chúng tôi đạt được là nếu chúng tôi có sức mạnh kỳ diệu để đoán bước chính xác, sẽ luôn luôn chính xác, chúng tôi có thể giải quyết vấn đề NPC trong POLYTIME.Tất nhiên, chúng ta không thể luôn luôn "đoán" bước chính xác. Vì vậy, đó là tưởng tượng. Nhưng cũng giống như số ảo được áp dụng cho các vấn đề thực tế, hậu quả có thể hữu ích về mặt lý thuyết.

Một khía cạnh tích cực của việc biến đổi các vấn đề ban đầu theo cách này là chúng ta có thể giải quyết chúng từ các góc độ khác nhau. Trong một lĩnh vực lý thuyết, nó là một điều tốt bởi vì chúng ta có (1) phương pháp tiếp cận chúng ta có thể thực hiện (và nhiều hơn nữa) và (2) công cụ chúng ta có thể sử dụng nếu chúng có thể được diễn đạt trong các lĩnh vực khác.

Answer 6

Tôi nghĩ câu trả lời của bạn nằm trong câu hỏi của bạn. Nói cách khác, đưa ra một vấn đề bạn có thể chứng minh rằng nó là một vấn đề NP nếu bạn có thể tìm thấy một NTM giải quyết nó.

Vấn đề NP là một vấn đề đặc biệt, và NTM chỉ là một công cụ để kiểm tra xem vấn đề có thuộc về lớp hay không.

Lưu ý rằng NTM không phải là một máy cụ thể - đó là toàn bộ các loại máy có quy tắc được xác định rõ ràng về những gì chúng có thể và không thể thực hiện được. Để sử dụng các máy "huyền diệu", bạn cần phải xác định chúng và hiển thị lớp sự cố phức tạp nào của chúng.

Xem http://en.wikipedia.org/wiki/Computational_complexity_theory#Complexity_classes để biết thêm thông tin.