Complexity Theory

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Verify a Hamiltonian cycle certificate in an undirected simple graph.
5
// Input representation:
6
//  - n: number of vertices labeled 0..n-1
7
//  - adj: n x n adjacency matrix (adj[i][j] = true if edge (i,j) exists)
8
//  - cert: a permutation of 0..n-1 representing the order of visiting vertices
9
// Returns true if cert is a Hamiltonian cycle.
10
bool verifyHamiltonianCycle(const vector<vector<bool>>& adj, const vector<int>& cert) {
11
    int n = (int)adj.size();
12
    if ((int)cert.size() != n) return false; // certificate must list all vertices
13
    // Check that cert is a permutation: each vertex appears exactly once
14
    vector<int> seen(n, 0);
15
    for (int v : cert) {
16
        if (v < 0 || v >= n) return false; // invalid label
17
        if (seen[v]) return false;         // duplicate vertex
18
        seen[v] = 1;
19
    }
20
    // Check edges along the cycle, including closing edge from last back to first
21
    for (int i = 0; i < n; ++i) {
22
        int u = cert[i];
23
        int v = cert[(i + 1) % n]; // wrap to form a cycle
24
        if (!adj[u][v]) return false;
25
    }
26
    return true;
27
}
28
29
int main() {
30
    // Example graph: a 5-cycle 0-1-2-3-4-0 (which is Hamiltonian)
31
    int n = 5;
32
    vector<vector<bool>> adj(n, vector<bool>(n, false));
33
    auto addEdge = [&](int u, int v){ adj[u][v] = adj[v][u] = true; };
34
    addEdge(0,1); addEdge(1,2); addEdge(2,3); addEdge(3,4); addEdge(4,0);
35
36
    vector<int> goodCert = {0,1,2,3,4};     // valid Hamiltonian cycle
37
    vector<int> badCert  = {0,2,1,3,4};     // not a cycle in this graph
38
39
    cout << boolalpha;
40
    cout << "Good certificate valid? " << verifyHamiltonianCycle(adj, goodCert) << "\n";
41
    cout << "Bad certificate valid?  " << verifyHamiltonianCycle(adj, badCert)  << "\n";
42
    return 0;
43
}
44

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Exponential-time backtracking solver for Subset Sum (decision version):
5
// Returns true if any subset of a[0..i] sums to target.
6
bool subsetSumBT(const vector<int>& a, int i, long long target) {
7
    if (target == 0) return true;           // found a subset
8
    if (i == (int)a.size() || target < 0) return false; // exhausted or overshot
9
    // Choice: include a[i] or skip it
10
    if (subsetSumBT(a, i + 1, target - a[i])) return true;
11
    return subsetSumBT(a, i + 1, target);
12
}
13
14
// Pseudo-polynomial dynamic programming solver for Subset Sum:
15
// dp[s] = whether some subset achieves sum s. Runs in O(n * S) where S = target.
16
bool subsetSumDP(const vector<int>& a, int target) {
17
    if (target < 0) return false;
18
    vector<char> dp(target + 1, 0);
19
    dp[0] = 1; // sum 0 is always achievable (empty subset)
20
    for (int x : a) {
21
        // iterate backwards to avoid reusing an item twice
22
        for (int s = target; s >= x; --s) {
23
            if (dp[s - x]) dp[s] = 1;
24
        }
25
    }
26
    return dp[target];
27
}
28
29
int main() {
30
    vector<int> a = {3, 34, 4, 12, 5, 2};
31
    int target1 = 9;   // yes: 4+3+2
32
    int target2 = 30;  // no for this set
33
34
    cout << boolalpha;
35
    cout << "Backtracking target " << target1 << ": " << subsetSumBT(a, 0, target1) << "\n";
36
    cout << "DP target          " << target1 << ": " << subsetSumDP(a, target1) << "\n\n";
37
38
    cout << "Backtracking target " << target2 << ": " << subsetSumBT(a, 0, target2) << "\n";
39
    cout << "DP target          " << target2 << ": " << subsetSumDP(a, target2) << "\n";
40
    return 0;
41
}
42

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given an undirected simple graph G (n vertices) and integer k,
5
// produce the complement graph Gc. Then (G, k) is a yes-instance of CLIQUE
6
// iff (Gc, k) is a yes-instance of INDEPENDENT SET.
7
8
using Graph = vector<vector<bool>>; // adjacency matrix for simplicity
9
10
Graph complementGraph(const Graph& G) {
11
    int n = (int)G.size();
12
    Graph C(n, vector<bool>(n, false));
13
    for (int i = 0; i < n; ++i) {
14
        for (int j = 0; j < n; ++j) {
15
            if (i == j) { C[i][j] = false; }
16
            else { C[i][j] = !G[i][j]; }
17
        }
18
    }
19
    return C;
20
}
21
22
// Naive checker for Independent Set of size k (for small n): try all subsets of size k
23
bool hasIndependentSetK(const Graph& G, int k) {
24
    int n = (int)G.size();
25
    vector<int> idx(n);
26
    iota(idx.begin(), idx.end(), 0);
27
    vector<int> choose;
28
    function<bool(int,int)> dfs = [&](int start, int need){
29
        if (need == 0) return true;
30
        if (start >= n) return false;
31
        for (int v = start; v < n; ++v) {
32
            // try to include v; check non-adjacency with chosen
33
            bool ok = true;
34
            for (int u : choose) if (G[u][v]) { ok = false; break; }
35
            if (!ok) continue;
36
            choose.push_back(v);
37
            if (dfs(v + 1, need - 1)) return true;
38
            choose.pop_back();
39
        }
40
        return false;
41
    };
42
    return dfs(0, k);
43
}
44
45
int main() {
46
    // Build a triangle graph (0-1-2-0). Clique size 3 exists.
47
    int n = 3;
48
    Graph G(n, vector<bool>(n,false));
49
    auto addEdge = [&](int u,int v){ G[u][v] = G[v][u] = true; };
50
    addEdge(0,1); addEdge(1,2); addEdge(2,0);
51
    int k = 3;
52
53
    // Reduction: (G, k) -> (Gc, k)
54
    Graph Gc = complementGraph(G);
55
56
    // Check equivalence on this small example by brute force IS on complement
57
    bool cliqueG  = true; // triangle obviously has a 3-clique
58
    bool indepGc  = hasIndependentSetK(Gc, k);
59
60
    cout << boolalpha;
61
    cout << "Clique in G of size " << k << "? " << cliqueG << "\n";
62
    cout << "Independent set in complement of size " << k << "? " << indepGc << "\n";
63
    cout << "Reduction preserves yes-instances: " << (cliqueG == indepGc) << "\n";
64
    return 0;
65
}
66