2
$\begingroup$

I have been doing some research into the limits of computation and I have come across the terms intractable and undecidable. Are these two terms the same thing?

What does intractable mean and what is an example of an intractable and undecidable problem?

$\endgroup$

1 Answer 1

4
$\begingroup$

Tractable usually means decidable in polynomial time. Under that definition, NP-complete problems appear to be intractable, but they're still decidable.

$\endgroup$
2
  • $\begingroup$ are all NP problems intractable or is it just NP-complete? $\endgroup$
    – Namster
    Sep 13, 2015 at 21:35
  • $\begingroup$ P $\subseteq$ NP. $\endgroup$ Sep 13, 2015 at 21:50

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.