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!