A community for students.
Here's the question you clicked on:
 0 viewing
UnkleRhaukus
 one year ago
Explain what is meant by an NPcomplete problem.
UnkleRhaukus
 one year ago
Explain what is meant by an NPcomplete problem.

This Question is Closed

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1i still don't understand it

Kainui
 one year ago
Best ResponseYou've already chosen the best response.0I've been curious about this too, I have only a vague idea of what the whole P vs NP thing is about. I think this is more of a computer science thing. @wio Know anything about this?

Kainui
 one year ago
Best ResponseYou've already chosen the best response.0http://openstudy.com/study#/updates/53efabb2e4b0f30a87d81459

Mimi_x3
 one year ago
Best ResponseYou've already chosen the best response.0NP  complete  hamilton path  sudoku cannot be solved in polynomial time but then u can find the answer to it

Mimi_x3
 one year ago
Best ResponseYou've already chosen the best response.0I had to do this for my one assignments http://en.wikipedia.org/wiki/Travelling_salesman_problem

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0P and NP isn't too hard to understand.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0P just means that a deterministic Turing machine can solve it in a \(\bf P\)olynomial number of steps. NP means a \(\bf N\)ondeterministic Turing machine can solve it in a \(\bf P\)olynomial number of steps. A Turing machine is an infinitely long band of tape and a cursor with a counter. The tape consists of frames and each frame has a symbol. The symbol gives the cursor an instruction, such as move left or right, change the counter value, and write a symbol down on another frame. A deterministic Turing machine has at most one instruction in each frame, while a nondeterministic Turing machine can have multiple instructions in each frame. When the cursor hits a frame with \(n\) instructions, then it splits into \(n\) different cursors and they run each instruction independently of each other. You can think of a deterministic Turing machine as our current computers if they were to have infinite memory. When we're talking about these things, generally we're ignoring any limitations in RAM or drive. The main difference between deterministic and nondeterministic is that deterministic must commit to a single choice, while a nondeterministic execute all choices simultaneously to solve a problem. The both machines have the same computing power, which is to say that if either one of them can solve a computing problem, both of them can. The issue is how many steps it would take to solve the problem. If we try to emulate a nondeterministic Turing machine, we have to keep a collection to hold the positions and counters of each cursor, and we would still have to execute their operations sequentially. It would be exponential increase in the number of steps. In general, implementing problems on the theoretical Turing machines is a bit difficult, so instead what we tend to do is to use an algorithm to solve another algorithm and vise versa. For example, the `min` operation gets the smallest element in a collection. The `sort` operation puts all elements in a collection in order. We can utilize `min` to solve `sort` by finding the `min` element, removing it, and putting it into a new sorted collection. We could repeat this until the collection was sorted. We would only need to repeat this process \(n\) times (the size of the collection), which is a polynomial. Since the composition of a polynomial with a polynomial is still a polynomial, then we know that if `min` is a P problem, then `sort`, which can be solved using `min` a polynomial number of times, must also be a P problem. In fact we would say that `sort` is no harder than `min` in terms of polynomial steps. We say a problem is NP Hard if it can be used a polynomial number of times to solve any NP problem . Thus we can say that every NP problem is no harder than every NP Hard problem. The 'no harder than' designation can be shown the same way I showed that `sort` is no harder than `min`. Also since it is a transitive relation, we really only have to solve the "hardest" NP problems using the NP Hard problem to show it is NP hard. The "hardest" NP problems are what we would call NP Complete problems. They are problems which are both NP Hard and NP. Suppose problem \(A\) is NP, and you're not sure about problem \(B\). If you can show that \(A\) is no harder than \(B\), then you know \(B\) is NP Hard. If you can show that \(B\) is no harder than \(A\) as well, then you've known that \(B\) is NP. Showing both would mean \(B\) would be NP Complete. We know NP problems can be used to solve P problems in a polynomial number of steps, which means that P problems are also NP problems. So far, no one has ever been able to solve an NP Complete problem using any P problem a polynomial number of times. Therefore we don't know if NP Complete is no harder than P or not. If it were true, then that would mean P = NP = NP Complete. All of our current methods for solving NP Complete problems require an exponential number of steps, but if someone showed P = NP they could all be solved in a polynomial number of steps. Breaking encryption is an NP Complete problem. Just to keep some things in mind: P is no harder than NP, and P is a subset of NP. NP is no harder than NP Hard, and NP Complete is a subset of NP and NP Hard. So far, it seems that NP Complete is harder than P which means P \(\neq\) NP, but it has yet to be proven whether or not P and NP Complete are equivalent (neither is harder than the other).

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0It seems that @Lyrae was saying that NP are the problems that can be verified in polynomial time. That is definitely an interesting way of looking at it, but not quite what the definition says. I'm not sure what formal definition of verifying a problem would entail, so I don't know if verification and solving with a nondeterministic machine are interchangeable criterion in the definition. The one way to understand a deterministic versus nondeterministic machine is to look at a tree. dw:1433108516731:dw Suppose we want to find \(x\) in the tree. A deterministic algorithm must traverse one branch at a time, and in the worse case it makes \(3 + 9 = 12\) traversals in \(12\) steps. A nondeterministic algorithm can take all branches simultaneously, and so it makes \(12\) traversals in \(1+1=2\) steps. To relate this to P and NP, we could make the depth of the tree be the polynomial \(f(n)\) with highest degree \(d\). We can suppose that no node has more than \(k\) children. For a deterministic machine, in the worst case it will take us:\[ \sum_{i=1}^{f(n)}k^i = \frac{k(1k^{f(n)})}{1k} = O(k^{n^d}) \]The nondeterministic machine in the worst case will take us: \[ f(n) = O(n^d) \]

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1Thank y'all for these excellent responses! I've written the below: ___ A decision problem is one in which there is a definite boolean answer; true (1), or false (0). A decision problem is said to be in P, if it is know that a solution can be found deterministically in the order of polynomial time. Such a solution can be obviously also be checked in a such order of time. A superset of P problems, is NP problems. These are decision problems that for which there also exists a polynomially ordered verification procedure for a potential solution, but that a method for finding such a solution is not know to be findable (deterministically) within polynomial time. If a solution to any particular NP problem becomes know to be findable in polynomial time, then that problem becomes know to be also in P. An NPcomplete problem is the set of problems, including NP (and thus P), of which again a polynomially ordered verification procedure exists, but to the extent that which it is as difficult as a problem can be, and still have such a verification process. Thus an NPcomplete problem, can be shown to be at least as difficult, as all other NP problems. Thus, if a polynomially ordered general solution to any NPcomplete problem was found, then all NP problems would become solvable by a reduction; the sets would collapse to simply P. ___ Have I got this all right? have I missed anything important? is it clear?

Lyrae
 one year ago
Best ResponseYou've already chosen the best response.0There are actually several definitions of NP. Formally NP is defined as \[NP = \bigcup_{k \in \mathbb{N}} NTIME(n^k)\]Which approximately reads as the union of problems solvable in \(O(n^k)\) for any natural number k given input size n (ie. all problems solvable in polynomial time) by a nondeterministic TM. The other equivalent definition uses verifiers instead. Wikipedia provides a fairly good explanation on this http://en.wikipedia.org/wiki/NP_%28complexity%29#Verifierbased_definition To solve a problem in NP you can hence nondeterministicly select input (certificates) and run them through its verifier in P. This is equal to the first definition.

Kainui
 one year ago
Best ResponseYou've already chosen the best response.0\(\color{blue}{\text{Originally Posted by}}\) @wio For example, the `min` operation gets the smallest element in a collection. The `sort` operation puts all elements in a collection in order. We can utilize `min` to solve `sort` by finding the `min` element, removing it, and putting it into a new sorted collection. We could repeat this until the collection was sorted. We would only need to repeat this process \(n\) times (the size of the collection), which is a polynomial. \(\color{blue}{\text{End of Quote}}\) For some reason I really enjoyed reading this paragraph most of all. It sort of opens my eyes to the concept that we can literally build different algorithms out of others or something which I guess I wasn't explicitly in the frame of mind before. It makes me realize the "mix and match" nature of specifying things a lot better I suppose.

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1Thank you everyone, you have all helped me.
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.