0
$\begingroup$

I know what P-hard means. Let's denote the P-hard problem as H. For any problem A in P, there exists a polynomial-time reduction from A to H. I think the answer is yes (I suppose that every "easy" problem can be reduced to a "harder" problem (in this case problems in P to an NP-complete problem), but I am not sure.

$\endgroup$
1
  • 1
    $\begingroup$ What is the question? Make sure to include the question in the body of the post. Please check the definition of P-complete and P-hard -- does it refer to polynomial-time reductions? I suggest you include the definition of P-hard that you are using. "I suspect the answer..." - what answer? answer to what question? I notice you've received similar feedback before: cs.stackexchange.com/questions/165166/… $\endgroup$
    – D.W.
    Jan 23 at 10:40

1 Answer 1

4
$\begingroup$

The Hamiltonian cycle problem is $\mathsf{NP}$-Hard (w.r.t. poly-time reductions), that means that there is a Karp reduction from any problem in $\mathsf{NP}$ to Hamiltonian cycle.

Since $\mathsf{P} \subseteq \mathsf{NP}$ the same holds true for any problem in $\mathsf{P}$. Therefore Hamiltonian cycle is $\mathsf{P}$-Hard (w.r.t. poly-time reductions).

Note however, that stronger notions of reductions are often used when talking about $\mathsf{P}$-completeness / $\mathsf{P}$-hardness. Using poly-time reduction yields some "rough" results like: All non-trivial problems in $\mathsf{P}$ are $\mathsf{P}$-Hard.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.