• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Non-determinism, Polynomial time problems and NP-complete

J

jaydee

Diamond Member
I've been researching these for awhile for a high school physics project, but still don't have a clear idea what they mean. From what

I've learned thus far:

A P problem is classified as one where the number of steps are bounded by some power of the problems size. (Would this be like solving for 2^x, where the difficulty is bounded by how large x is?)

An NP problem is classified as one where the number of steps are bounded by some power of the problems size by a non-deterministic Turing machine. [What is a (or an example of) a non-deterministic Turing machine?]

NP-hard is classified as a problem that has an algorithmic solution that can be used to solve any other NP-problem. (I really have no idea what this is suppose to mean.)

NP-complete is both NP and NP-hard.

I've gathered that the Hamiltonian path (traveling salesmen) problem is NP-complete. (Because the difficulty increases exponentially with the number of cities?)

Theoretically, quantum and DNA computers would solve this type of problem in a vastly more efficient time frame then a convential one.

One final question, is how would a 64-bit computer (and OS) compare to a 32-bit system in solving these types of problems?
 
Damn, I have a final on this stuff on Thursday of this coming week. You pretty much know all I know about it. Try getting a book on Algorithms and Complexity.
 
Anything specific in mind? I have a rough draft due tomarrow, but I can leave some parts in outline form until the final draft in 3 weeks. Can you define (non)determinism for me at least?
 


<< A P problem is classified as one where the number of steps are bounded by some power of the problems size. (Would this be like solving for 2^x, where the difficulty is bounded by how large x is?)
 >>



It's been awhile so I might be stating some of this wrong but...

A P problem is a problem such that a polynomial time (in relation to the size of the problem) algorithm exists to solve it. For example, the problem of sorting N numbers can be solved by the Bubble Sort in N^2 time (there are algorithms that can sort faster -- NlogN time). By the way, 2^X for a problem of size X is an exponential time algorithm.



<< An NP problem is classified as one where the number of steps are bounded by some power of the problems size by a non-deterministic Turing machine. [What is a (or an example of) a non-deterministic Turing machine?] >>



An NP problem is one in which no known polynomial time problem exists. However, if we are given a solution to the problem, we can verify the solution in polynomial time. I forgot what the Non-deterministic Turing machine means but I think it has something to do with the verifying the solution in polynomial time -- it has something to do with the concept of having an "Oracle" -- an all-knowing object.



<< NP-complete is both NP and NP-hard.
 >>



NP-Complete problems are a set of problems that have been proven to be equivalent to one another. Basically, someone has shown a way to convert one of these problem instances to another (in polynomial time). These problems have no known polynomial time solution. But since you can convert one problem into another -- if there exists a polynomial algorithm to solve one problem then you can solve all of these problems in polynomial time.

Hence, a lot of people think there is no polynomial time algorithm to solve these problems. This is known as the P = NP problem.



<< NP-hard is classified as a problem that has an algorithmic solution that can be used to solve any other NP-problem. (I really have no idea what this is suppose to mean.)
 >>



I forgot what NP-Hard means but it is essentially problems that are at least as hard to solve as NP problems.

 
Thanks. I'm getting some help from HT as well (I'm counting on more thorough answers, but it will take awhile longer).


<< A P problem is a problem such that a polynomial time (in relation to the size of the problem) algorithm exists to solve it. For example, the problem of sorting N numbers can be solved by the Bubble Sort in N^2 time (there are algorithms that can sort faster -- NlogN time). By the way, 2^X for a problem of size X is an exponential time algorithm. >>


I understand, that helps.


<< An NP problem is one in which no known polynomial time problem exists. However, if we are given a solution to the problem, we can verify the solution in polynomial time. I forgot what the Non-deterministic Turing machine means but I think it has something to do with the verifying the solution in polynomial time -- it has something to do with the concept of having an "Oracle" -- an all-knowing object. >>


In HT it's been said that an N-DT machine would be like a quantum or DNA computer.


<< NP-Complete problems are a set of problems that have been proven to be equivalent to one another. Basically, someone has shown a way to convert one of these problem instances to another (in polynomial time). These problems have no known polynomial time solution. But since you can convert one problem into another -- if there exists a polynomial algorithm to solve one problem then you can solve all of these problems in polynomial time. >>


How can you convert one NP problem to another and solve the rest in polynomial time? I'm missing something here.

BTW what course (and major) did you learn this stuff?
 
I can't believe you're doing this in high school! I'm a Junior at UC Davis and we studied this for my Algorithms class (ECS 122a). Oh, by the way, if you solve the P vs. NP problem, that is, find a way to solve an NP Complete problem, you win a million bucks!

Text
 


<< I can't believe you're doing this in high school! I'm a Junior at UC Davis and we studied this for my Algorithms class (ECS 122a). Oh, by the way, if you solve the P vs. NP problem, that is, find a way to solve an NP Complete problem, you win a million bucks!Text >>


Yeah, I'm not exactly going by the book in this project. My classmates are doing theirs on the likes of 'the physics of bowling', and 'how RADAR works', I figured I could handle something a little more challenging, so I started thinking about computers and came to quantum computing, and I ended up here. Thing is, the high school library is not the place to be looking for this type of material, and I'm placed on the same timeline as the bowling project, so it's a bit more work on my part, but I'm enjoying it thus far.

More input anyone?
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top