# 5. Yet another explanation of NP-problems

Các thuật toán khác nhau hoạt động chậm hoặc nhanh tùy thuộc vào kích thước của input

### 5.1 Constant time, O(1)

Thời gian không phụ thuộc vào kích thước của đầu vào. Điều này giống như `string.size()` trong C++ STL, với thực tế là việc triển khai lưu trữ kích thước của chuỗi hiện tại ở đâu đó.

Tốt `.size()` là phương thức nhanh, nhưng trong bất kỳ sửa đổi nào của chuỗi, một (nhiều) phương thức phải cập nhật trường size.

### 5.2 Linear time O(n)

Thời gian phụ thuộc vào kích thước của đầu vào, một cách tuyến tính (Linear functions alf các hàm ở dạng đường thẳng trên đồ thị). Đây là thuật toán tìm kiếm trên danh sách liên kết, chuỗi `.strlen()` in C.

### 5.3 Hash tables and binary trees

Chúng được sử dụng trong triển khai mảng kết hợp.

Sử dụng cây nhị phân (`std::map, std::set in C++ STL`) hơi lãng phí: bạn cần quá nhiều bộ nhớ cho mỗi nút cây.

Ngoài ra tốc độ tìm kiếm là logarit của cây: `O(log(n))` vì độ sâu của cây nhị phân là log cơ số 2 của `size_of_tree`.

### 5.4 EXPTIME

Thời gian phụ thuộc theo cấp số nhân vào kích thước của đầu vào, O(2^p(n)) or just O(2^n).

Ví dụ khi bạn cố gắng phá vỡ một thuật toán tiền điện tử bằng cách Bruteforce (là một phương pháp bẻ khóa cổ điển. Bằng cách thử tất cả các chuỗi mật khẩu có thể để tìm ra mật khẩu).

Đối với 8 bit đầu vào thì sẽ có 2^8 = 256 các giá trị... Bruteforce có thể bỏ khóa mọi thuật toán tiền điện tử và giải quyết hầu hết mọi vấn đề, nhưng điều này không thú vị lắm, bởi vì rất tốn thời gian và cực kỳ chậm.

### 5.5 NP-problems

NP-problems là việc tìm đầu vào chính xác cho công thức CNF.

### 5.6 P=NP

Là liệu có thể giải nhanh các bài toán NP hay không. Nói cách khác, một nhà khoa học sẽ tìm cách giải các bài toán NP trong thời gian dự đoán được (tất nhiên là nhanh hơn bruteforce/EXPTIME), sẽ tạo ra bước quan trọng hoặc mang tính cách mạng trong khoa học máy tính.

Theo ý kiến phổ biến thì điều này sẽ bẻ khóa tất cả các thuật toán tiền điện tử mà chúng ta hiện đang sử dụng.

### 5.7 What are SAT/SMT solvers?

Tất cả các bài toán NP có thể được rút gọn (hoặc chuyển đổi) thành các bài toán SAT hoặc được biểu diễn dưới dạng các bài toán SAT.

{% hint style="info" %}
Halting problem Judging by a source code of a function, can you say, will it terminate at some point, or will it spin into an infinite loop? Alan Turing famously proved that this is impossible (Halting Problem). But let’s see... Let’s say, you have a very basic 8-bit CPU, like 8080 or 6502. Say, there are only 5 8-bit registers, or 2 16-bit registers + one 8-bit register. Not uncommon for cheap CPUs of that era. And there is no RAM attached. So all memory you can use is 40 bits. This is not uncommon for geeks of the time, when RAM chips were expensive and bought after CPU. You can simulate such a basic CPU on any decent desktop computer. To track all states, you can use a dictionary. Key = values-from-all-registers-including-PC, value = boolean. The key has a size of 40 bits. The size of the whole dictionary is 2 40 bits or 2 32 bytes (just 4GB of RAM). Now you can simulate any code running on this toy CPU using your desktop computer and track all states. When the code stops, you stop. When you hit a state that already encountered (checked using the dictionary), you stop and report an infinite loop. Hence, to tell if the program will stop or not, you just need a computer with bigger RAM. To simulate a program running on your desktop computer with 4GB of RAM, you would need a computer with at least 2 2 64 bits of RAM. log10(22 64 ) ≈ 5.55 · 1018, but still theoretically possible. These toy CPUs and computers are in fact LBAs (Linear bounded automaton) – a Turing machine with limited tape (or memory). While Turing’s Halting Problem is about Turing machine with infinite tape (or RAM).
{% endhint %}

## P vs NP Problem <a href="#page-title" id="page-title"></a>

{% hint style="success" %} <mark style="color:blue;">Suppose</mark> (giả sử) that you are organizing <mark style="color:blue;">housing accommodations</mark> (nhà cho thuê, dạng nhà ở) for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the <mark style="color:blue;">dormitory</mark> (ký túc xá). <mark style="color:blue;">To complicate matters</mark> (làm phức tạp vấn đề), the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.
{% endhint %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://viettaliii.gitbook.io/home/education/reverse-engineering/symbolic-analysis/sat-smt-by-example/basics/5.-yet-another-explanation-of-np-problems.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.