P vs NP Problem

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Verify a Hamiltonian Path certificate in an undirected graph.
5
// Graph is given by adjacency matrix for O(1) edge checks.
6
// Certificate is a permutation 'path' of all vertices.
7
8
bool verifyHamiltonianPath(const vector<vector<bool>>& adj, const vector<int>& path) {
9
    int n = adj.size();
10
    if ((int)path.size() != n) return false; // must list all vertices
11
12
    vector<bool> seen(n, false);
13
    for (int v : path) {
14
        if (v < 0 || v >= n) return false; // invalid vertex id
15
        if (seen[v]) return false;         // duplicate vertex
16
        seen[v] = true;
17
    }
18
    // Check consecutive edges exist
19
    for (int i = 0; i+1 < n; ++i) {
20
        int u = path[i], v = path[i+1];
21
        if (!adj[u][v]) return false; // missing edge -> not a valid Hamiltonian path
22
    }
23
    return true; // all checks passed
24
}
25
26
int main() {
27
    // Example: a path graph 0-1-2-3 has a Hamiltonian path [0,1,2,3]
28
    int n = 4;
29
    vector<vector<bool>> adj(n, vector<bool>(n, false));
30
    auto add_edge = [&](int u, int v){ adj[u][v] = adj[v][u] = true; };
31
    add_edge(0,1); add_edge(1,2); add_edge(2,3);
32
33
    vector<int> goodPath = {0,1,2,3};
34
    vector<int> badPath  = {0,2,1,3}; // 0-2 is not an edge in this graph
35
36
    cout << boolalpha;
37
    cout << "goodPath is Hamiltonian? " << verifyHamiltonianPath(adj, goodPath) << "\n";
38
    cout << "badPath is Hamiltonian?  " << verifyHamiltonianPath(adj, badPath)  << "\n";
39
    return 0;
40
}
41

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// CNF is represented as vector of clauses; each clause is a vector of literals.
5
// Literal encoding: +k means variable k is true; -k means variable k is false. Variables are 1..n.
6
7
// Evaluate a clause under a (possibly partial) assignment: -1 = unassigned, 0 = false, 1 = true
8
// Returns: 1 if clause is satisfied; 0 if not yet decided; -1 if clause is falsified under current assignment
9
int evalClausePartial(const vector<int>& clause, const vector<int>& assign) {
10
    bool undecided = false;
11
    for (int lit : clause) {
12
        int var = abs(lit);
13
        int val = assign[var]; // -1, 0, 1
14
        if (val == -1) {
15
            undecided = true; // literal could become true later
16
        } else {
17
            bool litTrue = (lit > 0 ? val == 1 : val == 0);
18
            if (litTrue) return 1; // clause already satisfied
19
        }
20
    }
21
    if (undecided) return 0; // could be satisfied later
22
    return -1; // all assigned and all false -> falsified
23
}
24
25
// Check full assignment satisfies all clauses (polynomial-time verifier)
26
bool verifyCNF(const vector<vector<int>>& cnf, const vector<int>& fullAssign) {
27
    for (const auto& clause : cnf) {
28
        bool ok = false;
29
        for (int lit : clause) {
30
            int var = abs(lit);
31
            bool litTrue = (lit > 0 ? fullAssign[var] == 1 : fullAssign[var] == 0);
32
            if (litTrue) { ok = true; break; }
33
        }
34
        if (!ok) return false;
35
    }
36
    return true;
37
}
38
39
bool backtrackSAT(const vector<vector<int>>& cnf, vector<int>& assign, int var, int n) {
40
    // Early pruning: check for any falsified clause
41
    for (const auto& clause : cnf) {
42
        if (evalClausePartial(clause, assign) == -1) return false;
43
    }
44
    if (var > n) {
45
        // All variables assigned; verify solution
46
        return verifyCNF(cnf, assign);
47
    }
48
    if (assign[var] != -1) {
49
        return backtrackSAT(cnf, assign, var+1, n);
50
    }
51
    // Try var = true
52
    assign[var] = 1;
53
    if (backtrackSAT(cnf, assign, var+1, n)) return true;
54
    // Try var = false
55
    assign[var] = 0;
56
    if (backtrackSAT(cnf, assign, var+1, n)) return true;
57
    // Undo
58
    assign[var] = -1;
59
    return false;
60
}
61
62
int main() {
63
    // Example CNF: (x1 OR x2) AND (!x1 OR x3) AND (x2 OR !x3)
64
    // Satisfying assignment exists: x1=1, x2=0, x3=1 for example
65
    int n = 3; // variables 1..n
66
    vector<vector<int>> cnf = {
67
        {+1, +2},
68
        {-1, +3},
69
        {+2, -3}
70
    };
71
72
    vector<int> assign(n+1, -1); // -1 = unassigned
73
    bool sat = backtrackSAT(cnf, assign, 1, n);
74
75
    cout << boolalpha;
76
    cout << "SAT? " << sat << "\n";
77
    if (sat) {
78
        cout << "Assignment:";
79
        for (int i = 1; i <= n; ++i) cout << " x" << i << "=" << assign[i];
80
        cout << "\nVerified? " << verifyCNF(cnf, assign) << "\n";
81
    }
82
    return 0;
83
}
84

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Find shortest path (fewest edges) using BFS and reconstruct the path.
5
vector<int> bfs_shortest_path(int n, const vector<vector<int>>& adj, int s, int t) {
6
    vector<int> dist(n, -1), parent(n, -1);
7
    queue<int> q; q.push(s); dist[s] = 0;
8
    while (!q.empty()) {
9
        int u = q.front(); q.pop();
10
        if (u == t) break;
11
        for (int v : adj[u]) if (dist[v] == -1) {
12
            dist[v] = dist[u] + 1;
13
            parent[v] = u;
14
            q.push(v);
15
        }
16
    }
17
    vector<int> path;
18
    if (dist[t] == -1) return path; // empty = no path
19
    for (int cur = t; cur != -1; cur = parent[cur]) path.push_back(cur);
20
    reverse(path.begin(), path.end());
21
    return path;
22
}
23
24
bool verify_path(const vector<vector<bool>>& mat, const vector<int>& path) {
25
    // Polynomial-time verifier for a proposed s-t path
26
    for (int i = 0; i+1 < (int)path.size(); ++i) {
27
        int u = path[i], v = path[i+1];
28
        if (!mat[u][v]) return false;
29
    }
30
    return true;
31
}
32
33
int main() {
34
    // Build a simple graph
35
    int n = 6; vector<vector<int>> adj(n);
36
    auto add = [&](int u, int v){ adj[u].push_back(v); adj[v].push_back(u); };
37
    add(0,1); add(1,2); add(2,3); add(0,4); add(4,5); add(5,3); // two routes 0->...->3
38
39
    int s = 0, t = 3;
40
    vector<int> path = bfs_shortest_path(n, adj, s, t);
41
42
    // Build adjacency matrix for fast verification
43
    vector<vector<bool>> mat(n, vector<bool>(n,false));
44
    for (int u = 0; u < n; ++u) for (int v : adj[u]) mat[u][v] = mat[v][u] = true;
45
46
    cout << "Shortest path: ";
47
    for (int v : path) cout << v << ' '; cout << '\n';
48
    cout << boolalpha << "Verified? " << verify_path(mat, path) << '\n';
49
    return 0;
50
}
51