Using nondeterminism to detect cliques?

Question

I am trying to understand non-determinism with the clique-problem.

In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected.

Say I have a graph with nodes A, B, C, D, E, F and i want to decide if a clique of 4 exists.

My understanding of non-determinism is to make a guess by taking four nodes (B, C, D, F) and check if a connection exists between all 4 nodes. If it exists, I conclude that a clique exists and if doesn't, I conclude a clique does not exist.

What I am not sure of however is how this helps solve the problem as I just might have made the wrong choice.

I guess I am trying to understand the application of non-determinism in general.

Answer 1

Nondeterministic choices are different from random or arbitrary choices. When using nondeterminism, if any possible choice that can be made will lead to the algorithm outputting YES, then one of those choices will be selected. If no choice exists that does this, then an arbitrary choice will be made.

If this seems like cheating, in a sense it is. It's unknown how to implement nondeterminism efficiently using a deterministic computer, a randomized algorithm, or parallel computers that have lots of processors but which can only do a small amount of work on each core. These are the P = NP, BPP = NP, and NC = NP questions, respectively. Accordingly, nondeterminism is primarily a theoretical approach to problem solving.

Hope this helps!