Giải thuật -NP-Đầy Đủ

ª Ví dụ: bài toán SHORTEST-PATH là
– “không hình thức”: bài toán tìm đường đi ngắn nhất giữa hai đỉnh cho trước trong một đồ thị vô hướng, không có trọng số G = (V, E).
– “hình thức”:
° Một thực thể của bài toán là một cặp ba gồm một đồ thị cụ thể và hai đỉnh cụ thể.
° Một lời giải là một dãy các đỉnh của đồ thị .
° Bài toán SHORTEST-PATH là quan hệ kết hợp mỗi thực thể gồm một đồ thị và hai đỉnh với một đường đi ngắn nhất (nếu có) trong đồ thị nối hai đỉnh:
SHORTEST-PATH I x S