I have never been very clear on this concept. Please help:

At the end of the day, we should want to identify useful problems for which we don't have polynomial solution so far and only have exponential solutions.We want to keep finding if we can find a polynomial solution to these problems and the use of reductions is only to be able to identify new only exponential solvable problems with help of existing known exponential problems.??

Why is concept of determinism and non determinism brought into this whole concept of exponential and polynomial solvable problems?? How is this notion useful?

What do we call the problems for which we have only exponential solution so far, but we haven't been able to find reduction to a known NP - hard/complete problems..??


  • 1
    I think this belongs in the Theoretical Computer Science Q&A, I noticed you already posted it there...cstheory.stackexchange.com/questions/6671/np-hard-complete edit: just noticed someone there believes it doesn't belong there. cross site mod duel.
    – ale
    May 20, 2011 at 15:23
  • @ale - It is a bit introductory so I am inclined to agree with them. The Theoretical site tends to be tailored more towards graduate level questions where as a basic understanding that the asker is asking for would be an undergraduate level question.
    – rjzii
    May 20, 2011 at 15:27
  • i'm fine keeping it here. just thought it might get better answers there. thanks.
    – ale
    May 20, 2011 at 15:36

3 Answers 3


There's nothing obvious about determinism and non-determinism that leads to this. It's a bit technical.

A deterministic automaton corresponds to what we can actually build, either in hardware or in software.

A non-deterministic automaton tries all possible solutions, but to be in polynomial time it has to be able to verify a possible solution in polynomial time. If you enough of the theory, you'll recognize that an NA is equivalent to a DA with an oracle that mysteriously gives a solution, so an NA can solve something in polynomial time if a DA can verify a proposed solution in polynomial time. A nondeterministic automaton is equivalent to a deterministic automaton that tries all possible combinations, and the set of all possible combinations has exponentially more members than the set of things being combined, so if a NA can do something in polynomial time a DA can certainly do it in exponential.

NP is the set of decision problems such that a DA (hence a real computer) can verify a solution in polynomial time. If we can't verify a proposed solution in polynomial time, we certainly aren't going to be able to generate one, so NP is essentially the set of decision problems that might have real-life polynomial-time solutions.

The Traveling Salesman Problem, as usually given, isn't in NP because it's not clear how to verify that a given route is the cheapest in polynomial time. However, a variant of the TSP in which the question is whether there's a solution with a cost under X is in NP, since it's easily verifiable, and if we can solve that problem we can determine the cheapest route easily. Therefore, the TSP as usually stated is NP-hard, meaning that it's as hard to solve as an NP-complete problem.

There are problems that don't have known polynomial solutions for an NA, and problems we know aren't in NP. Those problems are usually categorized by further complexity classes (PSpace problems, for example, can be solved in polynomial space, but possibly only exponential time), or listed as undecidable. I don't know of any terms for a problem, say, that is PSpace but is not known to be in NP.


NP takes it's name from the fact that it can be solved in polynomial time by non-deterministic Turing machine. The trick is that non-deterministic in that case means, as if it can magically evaluate all branches in parallel. It's a theoretical model, you should not attempt to compare it with real life computers. In fact it has much more to do with area of mathematics know as formal languages and computability theory.

NDTM can be "reduced" to deterministic Turing machine, but in exponential time. That's why there are no polynomial solutions for NP-complete problems on computers, which (as you correctly noted) are deterministic.

  • but why bring the concept of non-determinism at all in this whole concept, when our machines are deterministic..?
    – xyz
    May 20, 2011 at 14:58
  • 3
    because it doesn't really have anything to do with real computers. It's more like theoretical computational models.
    – vartec
    May 20, 2011 at 15:05
  • 1
    @p2pnode - As vartec said, it's theoretical computational models. Turing did a lot of early computer science work before the first computers were ever built. Maybe some day we'll be able to build non-deterministic Turing-machines, i.e. quantum computers or something else. May 20, 2011 at 15:51
  • @whatsisname: AFAIK, quantum processors aren't NDTMs :-(
    – vartec
    May 20, 2011 at 15:57
  • @p2pnode: Because it's a way of categorizing problems in a way convenient for computation theory, and has yielded important insights. In order to understand that fully, you'd probably need to learn more of the theory. If it helps, think of a non-deterministic automaton as one that just has to verify answers, not generate them. That may be more intuitive for you, and it's one perfectly correct way of looking at them. May 20, 2011 at 20:23

The concept of deterministic versus non-deterministic comes into play from the way these problems are being studied on Turing Machines.

Conceptually, a Turing Machine can solve any Turing complete problem through one of two methods:

  1. Each action is performed sequentially with no branching when a decision is made, i.e. deterministic in that you can follow the exact path of execution yourself.
  2. Each action is performed sequentially but a branch occurs when ever a decision is made so that each branch can be explored, i.e. a non-deterministic Turing machine.

Thus, on a non-deterministic machine, if the algorithm can find a solution, you know that a solution exists that was found in polynomial time, but you don know know which execution branch was used in order to find that solution. Things get interesting though because a Turing machine can simulate a non-deterministic Turing machine but in order to do so it must calculate each pathway through the code and this is where the exponential nature of NP problems.

Turing machines are used for this sort of study due to their simple nature which makes understanding them at a mathematical level much easier when you are concerned about the core mathematics of the problem without having to worry about the overhead that might be involved with using different types of machines.

In regards to a problem for which we have a a exponential solution on a deterministic Turing machine but no reduction to a known problem, it would to EXPTIME.

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.