0
$\begingroup$

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!

$\endgroup$
6
  • 2
    $\begingroup$ Three issues: One, a polynomial time algorithm is one which can be solived in POLYNOMIAL TIME for the input. These are not just the problems that can be solved. They can be solved "quickly" (or what we usually say is "tractably"). Second, the halting problem is not in NP-Hard. Third, keep in mind that P vs. NP only applies to a GENERAL problem - not to specific instances. In fact, for many specific instances of NP-Complete problems there are polynomial solutions, but for the general problem, it may take exponential complexity. $\endgroup$
    – Foo Barrigno
    Commented Apr 11, 2014 at 11:40
  • $\begingroup$ "There are decision problems that are NP-hard but not NP-complete, for example the halting problem" - Wikipedia, how is the halting problem not in NP-Hard? $\endgroup$
    – joker
    Commented Apr 11, 2014 at 12:06
  • $\begingroup$ My bad, I guess I assumed NP-Hard problems had to be decidable, but NP-Hard problems don't have to adhere to that constraint. $\endgroup$
    – Foo Barrigno
    Commented Apr 11, 2014 at 12:19
  • 1
    $\begingroup$ @joker It is, but that isn't a very interesting fact. Every other problem reduces to the halting problem, because you can always write an algorithm that attempts to solve it, and if there is no solution is simply loops forever. $\endgroup$
    – fgp
    Commented Apr 11, 2014 at 12:20
  • $\begingroup$ @fgp Not all problems reduce to the halting problem. If "reduce" refers to many-one reductions, then exactly the recursively enumerable problems reduce to the halting problem. If it refers to turing reductions, then exactly the $\Delta^0_2$ problems reduce to the halting problem. In any case, only countably many problems can reduce to any single one, because there are only countably many Turing machines to do the reducing. $\endgroup$
    – Andreas Blass
    Commented Apr 11, 2014 at 13:48

1 Answer 1

Reset to default
1
$\begingroup$

But why would a problem not be in polynomial time, when you cant solve for an input n?

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 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?

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .