Tractable And Intractable Problems – Intro to Theoretical Computer Science

Tractable And Intractable Problems – Intro to Theoretical Computer Science


What both Alice and Bob have so far been able to find is–they have found exponential time algorithms for their problem and they haven’t been able to come up with anything better so far. The question of course is does the fact that Alice and Bob have not yet been able to come up with a polynomial time algorithm mean that the problems they are working on are only solvable in exponential time or could there be some sort of polynomial time algorithm that they haven’t found yet and there’s a special terminology for that. Problems or computer problems where you only have exponential time algorithms are called intractable problems, and those compute problems where you can’t find a polynomial time algorithm–those are called tractable problems. And this is going to be a rather obvious question to some of you I hope– does the fact that so far we only know exponential time algorithms for the problem that Alice was working on and the problem that Bob was working on. Does that mean that their problems are intractable or in other words, can we already say whether Alice’s or Bob’s problems are intractable or tractable, and I would like you to tell me if you think that is the case, so if we can already say that their problems are intractable or if there’s probably more information that we need.

1 thought on “Tractable And Intractable Problems – Intro to Theoretical Computer Science”

Leave a Reply

Your email address will not be published. Required fields are marked *