Consider the language CLIQUE G k G V E is an undirected gr

Consider the language CLIQUE = (G, k) G = (V, E) is an undirected graph, k > 0 is a natural number, and there exist k distinct vertices v_1, ..., v_k so that (v_i, v_j) E for each 1 lessthanorequalto i notequalto j lessthanorequalto k Prove that CLIQUE is decidable.

Solution

Assume that a problem (language) is decidable. Does that mean we can realistically solve it?
NO, not always. It can require to much of time or memory resources.
Complexity Theory aims to make general conclusions of the resource
requirements of decidable problems (languages).

First we show that CLIQUE NP, which we accomplish by giving a polynomial-time
verifier for CLIQUE. The following verifier for CLIQUE uses the k-clique as the certificate c.
V = “On input {{G, k}, c}:
1. Test whether c is a set of k different nodes in G.
2. Test whether G contains all edges connecting nodes in c.
3. If both tests pass, accept; otherwise, reject.

If graph G has m nodes, then Stage 1 takes O(k)O(m) = O(km) time, and Stage 2 takes O(k2)O(m2) =O(k2m2) time. Thus, the verifier V runs in (deterministic) polynomial time.

An instance of CLIQUE is a pair {G, k} of a graph G
and an integer k, and {G, k} is a YES instance for CLIQUE if G has a clique of size k, and {G, k} is
a NO instance for CLIQUE if G doesn’t have a clique of size k
Hence decidable.