• You are given the problem of finding whether 6-degrees of separation holds between a particular 2 people in the world. E.g. checking if you and your favorite celebrity are connected in at most 6 friendship edges (e.g. you-f1-f2-f3-f4-f5-celebrity).
• A solution is not just a Yes/No answer, but also the path and the ideal solution is one that indicates the shortest connection length.
• Let`s assume you have the list of all friends for all people in the world and that everyone has exactly b=100 friends and that there are 6 billionpeople in the world.

State whether the algorithms :

Breadth first search

Depth first search without repeated state checking

Depth first search with repeated state checking

Depth limited search DFS with a depth limit of L

Iterative deepening DFS

are complete and optimal for this problem (finding the connection path between given 2 people). Also, state and evaluate the space complexity of the algorithms considering this problem.