Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

Thanks,

share|improve this question
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 '11 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. –  rob May 20 '11 at 15:27
    
i'm fine keeping it here. just thought it might get better answers there. thanks. –  ale May 20 '11 at 15:36
add comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
but why bring the concept of non-determinism at all in this whole concept, when our machines are deterministic..? –  xyz May 20 '11 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 '11 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. –  whatsisname May 20 '11 at 15:51
    
@whatsisname: AFAIK, quantum processors aren't NDTMs :-( –  vartec May 20 '11 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. –  David Thornley May 20 '11 at 20:23
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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