Does the way a graph $G$ is encoded affect the proof that $CLIQUE$ is in $NP$?

Question

For a proof that $CLIQUE = \{ \langle G, k \rangle | G$ is an undirected graph with a $k$-clique. $\}$ is in $NP$ by constructing a nondeterministic Turing machine $N$, where

$N$ = $``$On input $\langle G, k \rangle$:

1. Nondeterministically select a subset $c$ of $k$ nodes of $G$.

2. Test whether $G$ contains all edges connecting nodes in $c$.

3. If yes, $accept$; otherwise, $reject."$

Does the way we encode $G$ affect this proof?

Are encoding $G$ with adjacency matrix and encoding $G$ by first listing the number of vertices (in binary) and listing all edges (in binary), for example, ($11_2; (01_2, 10_2), (01_2, 11_2), (10_2, 11_2)$) represents a triangle, all valid for this proof?

Does this proof make any implicit assumption on encoding $G$?

Answer 1

How $G$ is encoded makes a big difference. Consider these two (fairly extreme) cases:

• We encode $G$ as the union of max-cliques. Then even a deterministic Turing machine can solve the CLIQUE problem in polynomial time with this encoding.

• We encode $G$ as an adjacency matrix, but instead of writing the bit in cell $(i,j)$ once, we write it $2^{i+j}$ times. It would take exponential time just to read the input. So a non-deterministic Turing machine cannot solve CLIQUE in (worst case) polynomial time with this encoding.

By default, we assume a "useful" encoding e.g.: (a) edge list, (b) adjacency matrix, or (c) list of neighbours. There will be a polynomial-time algorithm to convert between any two of these, so which one of these encodings we choose will not affect membership in NP.