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 read that the definition of NP-complete is : These are the hardest problems in NP. Such a problem is NP-hard and in NP

How do we know if a problem is hardest in NP, and no harder problem exists. I understand that let's assume that somehow magically we know that a problem L is hardest in NP and then we can find out more hardest problems H if we can reduce H to L and vice versa.But my question is how does it all begin? How do we know 1 hardest problem to begin with?

Also, to be able to say that something is hardest (or any extreme), we need to know all possible problems in NP and then argue about the hardest.. How do we know all possible NP problems? Is this where turing machine comes useful and by using representation of output string in form of 1 and 0 in output tape, we can theoretically talk about all possible NP problems.

I understand that I may not have been able to articulate my question well - due to confusion.

Thanks,

share|improve this question
1  
I don't think you understand what "hard" means in this context. –  Rein Henrichs May 21 '11 at 4:57
    
@Rein Henrichs: I think that @p2pnode does understand what "hard" means. Usually NP-complete problems are shown to be show by showing they are equivalent to another NP-complete problem. But somewhere there has to be a first known NP-complete problem, and the question that I think was being asked is how on Earth that original one could have been proven to be NP-complete. –  btilly May 21 '11 at 6:02
    
Good question, wrong stack exchange site. –  Job May 21 '11 at 16:30

2 Answers 2

up vote 1 down vote accepted

You can read about the original "1 hardest problem" at http://en.wikipedia.org/wiki/Cook-Levin_theorem. That includes a sketch of a proof that the problem is, in fact, NP-complete.

The problem is Boolean satisfiability. Given a complicated Boolean expression, can we find a set of inputs that will make it true? It is easy to see that the problem is in NP (given a possible answer, you just plug it in and evaluate it).

Going the other way is harder. Here is the basic idea. Given any problem in NP, you can design a non-deterministic machine that would solve that problem in polynomial time and output a yes or no. (That is what it means to be in NP. Note that we can't actually build non-deterministic machines, but we can still theoretically design them.) Given that machine design we can then design a Boolean expression that is only a polynomial factor larger that will output true/false depending on what the non-deterministic machine would have output. Therefore if we had a polynomial time algorithm for answering the Boolean satisfiability problem, we could solve any NP problem in polynomial time.

Of course once you have one NP-complete problem, we then can go about showing that other NP-problems could be used to solve that one and daisy chain to find other NP-complete problems. But you have to find one first, and Boolean satisfiability was that first one.

share|improve this answer
    
"non-deterministic" here means magically choosing the right answer always. –  user1249 May 21 '11 at 23:22

EDIT: This seems to be a similar question (assuming the question is about the history, not the "hardness"): Stack Overflow - First NP complete problems

Turing machines are important because they are considered a model of computation that applies to essentially any computer (except perhaps quantum computers) http://en.wikipedia.org/wiki/Church Turing_thesis so they help us study computation.

It's been a while since I studied complexity theory but I'll try explaining in more detail:

NP is non-deterministic polynomial time. That is the problem can be solved in polynomial time using a non-deterministic Turing machine. Non-determinism in this statement implies the turing machine can explore different solutions concurrently.

The concept of "time" is the number of computation steps as a function of the length of the input. (as the input length goes to infinity and ignoring any constant factors).

You'll need to look at the model of a Turing machine to get a better idea of what is meant by the length of input and steps.

And so, there are many problems in complexity class NP, some of them really easy. Some of them "hard". They're hard because there is no known deterministic Turing machine, polynomial time, algorithm for solving them. They're also very interesting because if one of them can be solved in polynomial time on a determinisitic Turing machine then all of them can be.

When you do a formal proof for NP-completeness you need to show:

  1. That the problem is in NP. That is you show some non-determinsitic Turing machine that solved the problem.
  2. That if you can solve it in polynomial time on a determinstic Turing machine then you can solve some other NP-complete problem in polynomial time on a determinstic Turing machine. You do this via reduction - transforming one problem into another in a number of steps that's a polynomial function of the input. This shows that it's at least as hard to solve as the other problem.

I think I got that right :-) I hope it makes sense.

share|improve this answer

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.