I have confusion over P, NP-Complete and NP-Hard problems.
I understand a polynomial time algorithm is one which can be solved for a an input string of length n. But why would a problem not be in polynomial time, when you cant solve for an input n? I.e the halting problem (NP-Hard) or for an input of length n where you will never know if you will solve for example very big graphs in real networks (NP-Complete)?
Let me use the seating problem as another example (where people can be arranged on a table and people are happy to be seated with their neighbour). Why would we argue that the seating problem is in polynomial and can be converted to a hamiltonian circuit? I could argue that if there is a fixed number of people around a table, then yes it could be solved in polynomial time. But what if you want to covert a hamiltonian circuit to a seating problem. Say, the hamiltonian circuit is massive and continuous. This is NP-Complete. Not polynomial, or should I assume, you can only make the conversion (say its polynomial) if you have a full computed circuit? I understand the hamiltonian circuit problem can be NP-Complete.
I hope I have made sense,
Thanks in advance!
Note as well that if a problem is NP-Complete and we assume no polynomial time algorithm to solve it, we are assuming $P \neq NP$. While no proof showing $P \neq NP$, that tends to be what people believe.
I think it's also important to put out some definitions of P and NP. The class NP has languages (read- problems) in it such that there exists a Non-Deterministic Turing Machine such that given a solution to the problem, it can be verified in polynomial time. The class NP deals with decision problems. That is, we ask if a string is a member of the language, and we can verify this in polynomial time. The intuition is that we simply run the TM on the input string. If the string is in the language, the Turing Machine will halt and accept it.
Now, a language (problem) $L_{0}$ is NP-Complete if for every language (problem) $L \in NP$ is reducible to $L_{0}$ in polynomial time. So NP-Complete problems are the hardest problems in the set.
Now let's consider $P$. A language (problem) is in $P$ if there exists a deterministic Turing Machine that can decide if an arbitrary string is in the language in log-space (which implies polynomial time). So we get a "yes" if the answer is correct, and a "no" if it isn't correct.
Let people be the vertices, and let each person be connected by an edge to every other person. These edges will be weighted. Lower values denoted higher satisfaction. So to determine how to maximize the happiness in the system, we minimize the cost of the Hamiltonian Circuit on the person graph I constructed. This is your reduction.