August 1st, 2017, 06:02 AM

Complexity classes of discrete math problems
I am having trouble understanding how to determine the class complexities (NP complete, NP hard, P,...)
of a discrete math problem.
Could someone show the detailed procedure with explanations on these three problems?
Assume that P≠NP. Please give math strict explanations.
Is it in electric circuit that connects each of n
cities, the shortest length of a transmission line that passes only once through each city and connects all cities in a closed network is less than k?
Given a sequence of n points of two dimensional coordinate system and indices of two points from that sequence. Is the shortest closed path that passes through all points shorter from the shortest path between given two points?
In a social network of n people, does the largest set of people that knows each other contains more than k people?
Does someone know how to formulate and determine the complexity classes of the problem of "n people and relations between each pair of them"?