Thread: understanding p versus np

i obviously had help with this the others on the page but also x(x-y) and Quantime.NP is a verifiable list. Most questions will ask you to solve using the list. Once solved you can easily take the points you are looking for and backtrack to the polynomial time equation. Therefore for any solvable verifiable list there always exsists a poly time eqn.this is more than just pnp. Its an easy concept to start but then i asked well what is P? What does p contain awnser pretty much everything. So i went on to exponential time which was the worst way of solving for the list because most of the time the poly time eqn and verified list are not known. However converting from exponential to poly proved to be exceedingly difficult i was confused because i could see no reason for why it was changing. So i thought about heisenbergs uncertainty i could never convert one to the other accurately so something was in the way. Now if you want to solve from exponential to polynomial you can say hi to heisenbergs uncertainty principle. But if you solve for the third side of your triangle goodbye heisenbergs uncertainty principle because two sides are known. Asking sombody to solve np complete, np hard i have been shown maybe twenty at least I now know billions because its particle physics, waveforms, heisenberg etc.what i was thinking about was maybe using this to make custom particles at the atomic level. Machine learning is the process by which we can convert exponential time eqns into poly time eqns you cant just convert one enq to the other which makes sense to me. I cant look at a book and tell you everything about it without reading it. Similarly most computers, turing machines are limited in the same way therefore you cannot solve all p=np. The universe however can. Of course this doesnt make sense unless you can find the position of an electron in an atom obviously not easy. This was where x(x-y) and quantime were talking about waveformnormalisation which to be honest i didnt know much about but i got the basic idea that they were trying to integrate to find the 1d constant. Which was really similar to p=np. What i had was a list of numbers on a line. Then i have to find the polytime eqn which would have given the amplitude of the waveform and the exponential time eqn that would have tested all potential points on the line this with accuracy is a fractal. Now if you resolve between your two solved eqns you get the 3d area the electron passes through or the energy level but this isnt finished becauswe i am still missing the original electron eqn from when the atom was created. But you are still uncertain unless you can keep the room temperature constant and other magnetic fields away. this is really hard math and any changes to the system cause trouble. So i needed something a bit more constant and i was looking through the electronics on microphones and how supersonic aircraft break the sound barrier. I looked up on wikipedia and found that once aircraft break the sound barrier they are travelling faster than the sound waveform. So i wondered if it were possible for a particle to move in straight line and yeah it is. so no more heisenberg uncertainty principle. and the scary math im not that good at it ps i have copies of everything dated of course theres prob copyrights somewhere i dont know about.

In what context ? Are you talking about protons and neutrons in particle physics ?

The first couple of paragraphs of P versus NP problem - Wikipedia, the free encyclopedia provide a reasonable clear plain English description. I'm not really familiar enough to expand on it.

f

In short, P vs NP means the following: Suppose we have some problem, for which we can check whether its solution is correct fast. The question is: Does this imply that we can find this result fast?

I might have an awnser but i dont think you will like it.... P=NP however p is not equal to np on the basis of not just affordability but also practicality. Fact is that most problems can be solved in a fraction of a second and if you are only selecting certain variables you could possibly use minterms and such to reduce the circuit down to tiny proportions from possible hundreds of alu s. But how expesive would such circits be to build and how large? As it was said on the webpage one equation in np has more variables than the number of atoms in the universe do we make a circuit as big as a universe or not? or do we reuse circuit architecture at the expense of time?? Basically p=np is a theoretical circuit of infinite size. oh an the equation is (2^((2^n1)+(2^n2)+(2^n3)....))!*y where n is your numerical variable and y is your number of operators.

Originally Posted by fiveworlds

I might have an awnser but i dont think you will like it.... P=NP however p is not equal to np on the basis of not just affordability but also practicality.

You seem to have missed the central point about the question and its answer. If you can't find the answer as easily as you can verify that the answer is correct, then p does not equal np. If you want to put it into "practical" terms, then compare the number of logical operations a von Neumann computer would have to carry out to find vs. verify the answer.

more homework thanks tk. Oh and define easily. Do you mean time taken or circuitry required or easy of use for the user/programmer.

Originally Posted by fiveworlds

more homework thanks tk. Oh and define easily. Do you mean time taken or circuitry required or easy of use for the user/programmer.

A combination of all of these things. You have a computer. It verifies that a proposed solution is in fact a solution. It takes some amount of resources (let's just count operations). Now, on that same machine, same hardware, etc., discover the solution (without knowing it). Compare the resources taken to do that.

The absolute amount of time taken isn't quite the criterion, by the way. It's whether the solution can be found in "polynomial time." I recommend reading the wiki article (and the references it links to) that Strange has already suggested: http://en.wikipedia.org/wiki/P_versus_NP_problem

As an interesting side note, under the "lets just count operations" model you can prove that there exists a polynomial time factorization algorithm

W

I'm not exactly sure what you are trying to show with that diagram fiveworlds.

sorry i know the diagram is bad. just draw the possibilitites out and add them or something and youll see something like
9{9,8,7,6,5,4,3,2,1}
8{7,6,5,4,3,2,1}
7 etc
8{7654 etc}
etc
7 etc
etc
6 etc and so on
after that its just circuit design mine was really complicated it could probably be reduced in the future. Then i just said that the number of input bits should be limited to a constant just from circuit design ie 64 combinations of zeros and ones and so should the number of possible operations ie add subtract multiply. Finally you get your (constant)(constant)(variable)

if p=np then the world will be a different place entierly,from the way we now see it.the will be no massive difference between solving a problem and recognizing the answer once its solved.as a result of this;most philosophers and computer scientist expect p not=np. for this millennium prize question

Originally Posted by fiveworlds

sorry i know the diagram is bad. just draw the possibilitites out and add them or something and youll see something like
9{9,8,7,6,5,4,3,2,1}
8{7,6,5,4,3,2,1}
7 etc
8{7654 etc}
etc
7 etc
etc
6 etc and so on
after that its just circuit design mine was really complicated it could probably be reduced in the future. Then i just said that the number of input bits should be limited to a constant just from circuit design ie 64 combinations of zeros and ones and so should the number of possible operations ie add subtract multiply. Finally you get your (constant)(constant)(variable)

I still have no idea what you're trying to show. Did you read the wiki entries on p vs np, and what is being discussed? There are many, many problems where it is trivial to verify that something is a solution to a problem, but extremely difficult to come up with the solution in the first place. A classic example is prime factorization. If I give you a number, it will take you many steps to find the prime factors. But if I give you the factors, you can quickly multiply them out to find the number. Can you not see that there is a world of difference in the amount of logical effort/energy/etc. needed to verify, vs. the amount needed to discover?

Originally Posted by fiveworlds

just draw the possibilitites out and add them or something and youll see something like

If you are suggesting generating all possible solutions and then check each one ... that is exactly what make a problem "hard": the need to search the entire solution space.

na i was suggesting using a separate circuit for each and running all instances at the same time. Strictly speaking this is against the rules of the question. if one person can add two numbers in a minute 2000 people can add 4000 in a minute. i wanted to figure if i could do the same with one computer which i think you can but its wrong for this so back to the drawing board.

Originally Posted by fiveworlds

na i was suggesting using a separate circuit for each and running all instances at the same time. Strictly speaking this is against the rules of the question. if one person can add two numbers in a minute 2000 people can add 4000 in a minute. i wanted to figure if i could do the same with one computer

That's why I asked you to study what is meant by polynomial time. Your question, as I understood it, was originally about p vs. np (and that's still the thread title).

What you are doing is equivalent to saying "If I have an infinitely powerful computer, then I can solve anything." That's not what the p vs np question is about at all. Also, not all problems are solvable by launching a bunch of parallel processes. So merely having an infinite number of computing units may not do you any good, if you have to wait for an intermediate result produced by just one of them for the others to proceed.

P or NP is basically about the amount of time a person/a computer need to solve a problem.

ie:
When a person try to find a solution (ie: missing sock): it took alot of time. But when solution is found: the solution looks obvious compared to the effort.
When a computer search for optimal move (ie: chess): it took a supercomputer. But when solution is found: correct move is simply evident in its execution compared to the effort.

Which is easy to see the difference but not easy to definitiely prove either way. Its the equivalent of saying an electrons orbit is circular therefore all electrons orbits are circular. Just because something is observable as something doesnt mean that is proved to be something

Originally Posted by fiveworlds

Which is easy to see the difference but not easy to definitiely prove either way. Its the equivalent of saying an electrons orbit is circular therefore all electrons orbits are circular. Just because something is observable as something doesnt mean that is proved to be something

And again, you keep missing the point entirely. There are many problems for which we can quickly/easily verify whether a proposed solution is, in fact a solution, but for which finding a solution is much harder/more energy intensive/takes much longer. The central question that is the subject of the thread title is whether there exists a general proof that p = np. If so, then the asymmetry we observe is an artifact of insufficient creativity/ingenuity/etc. and there is therefore hope that we can uncover the magic algorithms that find solutions as easily as we can verify them. If p does not equal np, then that hope fades.

Nah my point was not to rule either possibility out without proof. So how do we go about proving this. I reckon links to all pages containing relevant equations should be found as being as start.

Originally Posted by fiveworlds

Nah my point was not to rule either possibility out without proof. So how do we go about proving this. I reckon links to all pages containing relevant equations should be found as being as start.

That's the whole point, fiveworlds. It is not yet known if p=np. There is no proof, either way. The one who does finally prove it (either way) gets a cookie and a million dollars (it's one of seven Millennium Prize problems for which this amount of money is offered as a prize).

But surely there is similar work like karmarkars theorem. Is it really worth a cookie but is it reasonable to assume we would have an awnser already if no prize was offered?

Originally Posted by fiveworlds

But surely there is similar work like karmarkars theorem. Is it really worth a cookie

Definitely worth a cookie.

Lots of folks have tried and failed to come up with a proof. Really smart folks. Really, really smart folks. Who love cookies. And still no proof.

the problem appear to be philosophical as well as mathematics and computer science.there has be no cumputer programming which could solve this.but to make it more easier on the look,will believe a philosophical approach will be much easy.once this is done it can be given mathematical expression.

Well what about the subset sum problem what operations can be done on the info while still remaining in poly time. What about separating into odd or even positive and negative ie 4arrays

Not sure once again what you are on about fiveworlds

Make a filter based on certain critereon if(p=odd then it must be the sum of two odds or an even etc

be it the sum of two odds or even we still won't end up with the answers easy,under polynomial time.maintain that a gud thought should be given to this problem,philosophically.what if we end up with the solution easily,how then can we explain the new world that has no major distinction between the problem solution and identifying this solution once its solved.(i will recognize an answer even if didn't work on the problem.)

but what if there is a small upper limit on p=np then hardly anything would change at all as it would only be useful for small problems i dont really see how it could work for massive numbers of variables.

The whole point is that these are measures of how resources (time, hardware) scales with problem size. If p=np only for small problems then p != np.

or what if they can be solved in polynomial time but it winds up taking longer than exponential time for anything under 1000 variables

Originally Posted by fiveworlds

or what if they can be solved in polynomial time but it winds up taking longer than exponential time for anything under 1000 variables

Then I would add enough dummy variables to get over the 1000 threshold and solve it in polynomial time.

Correct easy isnt it. But it is not what people expected they were expecting something to crack every password on the planet when in reality its just making an equation run more efficiently after a point ie instead of calculating pi to 25 digits you might now be able to count to 27 no huge difference really

Originally Posted by fiveworlds

Correct easy isnt it. But it is not what people expected they were expecting something to crack every password on the planet when in reality its just making an equation run more efficiently after a point ie instead of calculating pi to 25 digits you might now be able to count to 27 no huge difference really

I find it difficult to understand the relevance or point of your posts, fiveworlds, your most recent one included.

I'm confused...are we talking about a P-N junction...like in a diode or transistor...or something else?

g

Ok...that's WAY beyond my knowledge...I'll just lurk.

Originally Posted by fiveworlds

No its wether a question can be solved in poly time an^k given a set of varibles and an awnser ie can you solve {-2,-3,-7,2,5}=0 in poly time without verifying ie adding -2-3+5=0. classically there is a solution in a^n-1 tries which is exponential not poly you can take as many steps as you want to get there provided it winds up as an^constant. oh and tk P=np ethics remember?? and it is possible to sort in poly time. Since its possible to sort in poly time this particular equation can be solved in poly time and p=np.

The question for the Millennium Prize isn't "Show that there exists one case for which finding a solution and verifying the solution are both doable in polynomial time." Of course you can find specific instances where that is trivially true. That's not the challenge. The challenge is much, much grander: "Show that the ability to verify a solution in polynomial time also always implies that one can discover the solution in polynomial time." For all cases.

That's why your posts make no sense to me -- they seem to be fixated on some special case that is left incompletely articulated, and whose connection to the general problem is also unclear.

Yeah but the subset sum problem is np complete did you read it. if a solution exists for one then all are proven to be solvable potentially in this case i only need one.

I think you are not grasping what np-complete means fiveworlds. NP complete problems are such that if you have an algorithm that can solve one class of problem generally than you can use it and a polynomial reduction to solve any other NP problem.

So to say you have a solution to the subset-sum problem you need to have an algorithm that can solve any subset-sum problem in polynomial time, not just an easy case.

For example, how would your filtering idea handle a random set 1 million 100-digit integers?

It w

is it that you guyz are confusing yourself over the p=np problem,if p is the answer and p was easily gotten in polynomial time does this imply that np which is check;could be easily checked in polynomial time? if yes...does this now mean that thesame varibles that are in p are also in np?.......the question is is thesame problems in p also in np?

No just that it can possibly be solved in poly time which it can. There is a limit with how effective your filter is but thats all.

Originally Posted by fiveworlds

however in the worst case you would wind up using exponential

Which means you do not have a polynomial time algorithm

it would just be 1000000*test*n in best case.

I'm not sure what this equation means?

IMO, the way I convince myself that P is not equal NP is to understand search-algorithm/the-processes-of-searching (artificial intelligence domain).

"Searching" is the general definition for "intelligence" and it apply to both to human and non-human things (like evolution and computers).

What searching do is: to find a solution from a large set of data and possibility. The solution & the problem can appear in many form, but all will involve searching. For example: GPS navigation software will perform searching to find a way to destination, this is a form of artificial intelligence.

Imagine if you are a GPS software, how do you know a way to a destination without any prior (godly/omnipotence) knowledge of the destination? you do it by doing trial-and-error. You might end up doing millions of turns, fail, and re-do again, but you still don't know if you are right or wrong until you actually reach the destination.

So, when you reach the destination, is it too easy to prove it is right! of course... you trace you path back to your origin and you see that this way is the most direct to your destination and discard all other trial-and-error path, you don't need to check other road at all when you have found the correct path (you will see it is directly linked to your destination without needing to do any more searching to prove it is connected to your destination)...

This shows that: finding a solution is hard, but to understand that a solution is correct is easy!
---

P/S: Mathematical equation is not searching. The searching came from the human ability to find out the correct equation that can model/solve a real world problem. When an equation is found: the input & output of the equation is obvious...

wow come on this is really easy. Ill explain this simpler for you if you can solve ax^2+ax+c using (x+1)(x+1) which is two sorted sets then p=np

Originally Posted by fiveworlds

wow come on this is really easy. Ill explain this simpler for you if you can solve ax^2+ax+c using (x+1)(x+1) which is two sorted sets then p=np

Your confidence is a lot like that of the thousands of folks who submitted proofs of Fermat's Last Theorem. You continue to misunderstand fundamentally the nature of the task before you: It's not to find an instance or special case. It's to construct a general proof. All you have demonstrated is that, for a specific presumed approach, p does not equal np. That is not the same as proving that there exists no approach anywhere for which p equals np.

If you still do not understand the distinction, then there's probably no point in continuing.

that is general p=np go to school

Originally Posted by fiveworlds

wow come on this is really easy. Ill explain this simpler for you if you can solve ax^2+ax+c using (x+1)(x+1) which is two sorted sets then p=np

Imo, we can solve this quadratic equation either by the hard way (by factoring, testing different value that works, intuition) or simply by using a formula(!).

I remember that the formula for solving it is: (-b +- sqrt(b*b-4*a*c))/(2*a)
Methods to Solve a Quadratic Equation--by factoring, by the quadratic formula...

My point is: this formula prove that the hard work of mathematicians is proven to be fruitful such that they discover a formula that can solve quadratic equation really quickly rather than leaving us trying too hard with factoring ourselves. I also read somewhere that there were people claiming they had solution for power-of-3 equation (ie: ax^3 + ect), while for higher power equation (ie: ax^5 + ect) there were no known solution IMO.

well in this the only variable is c what you are looking for so 10 variables=
( )( )( )( )( )( )( )( )( )( )( )( )
all you need is the formula for writing the number so in quad eqn format dont really know how you could use formula since you need one for quadratic then cubic etc

Originally Posted by fiveworlds

that is general p=np go to school

Sorry to laugh at you, but that is absurd.

Submit your "proof" to the prize committee, collect your million. I'll supply the cookie.

im sorry if i was a bit mean its just that i was tired after school i didnt mean anything by it tk

Originally Posted by fiveworlds

im sorry if i was a bit mean its just that i was tired after school i didnt mean anything by it tk

Don't worry about it, fiveworlds. My hide is made out of neutronium and thick slabs of scar tissue.

this is th

all you need is the formula for writing the number so in quad eqn format dont really know how you could use formula since you need one for quadratic then cubic etc

I don't know how the quadratic formula work either... but we all use it, and it work.

this is the equation for the subset sum problem i outlined (not add x and multiply variables)
x^5+9x^4+120x^3-116x^2-306x+1680=0 where 0 is your variable.
step1:sort the changed variable (factorise bubble sort)
step2:sort the output in this case { −7, −3, −2, 5, 8}
...
step11:..

Okay, lets say we got the correct answer (from the computer). Isn't this answer easy to prove? we simply put back the answer into the equation and viola... it fits.

We can prove it by using pen, paper and calculator, but we find it using a computers...

you just need your eqn in poly time thats all

Erm...
Lets say a computer find answer by doing this:
x^5+9*x^4+120*x^3-116*x^2-306*x+1680=0
1^5+9*1^4+120*1^3-116*1^2-306*1+1680=0 --Check: FAIL
2^5+9*2^4+120*2^3-116*2^2-306*2+1680=0 --Check: FAIL
3^5+9*3^4+120*3^3-116*3^2-306*3+1680=0 --Check: FAIL
4^5+9*4^4+120*4^3-116*4^2-306*4+1680=0 --Check: FAIL
...ect,

That mean doing the same equation many many times.

-------
Now, if you got an answer:
lets say
x=2

then you try it on the equation:
x^5+9*x^4+120*x^3-116*x^2-306*x+1680=0 --Check: SUCCESS

is just done 1 time...
-------

So the answer took less time than finding the answer.

na look the equation is the product of the sum of your variables at zero so the base variables can be constructed once the base variables are found in 1 run then you solve on the second run and btw dont use x at all you dont need to. all you need to do is factorise and remember your rules.

how is finding factor is easier than putting answer into the equation???

my point is: this doesn't prove p=np at all. Finding solution always takes more time.

Well the question wasnt that you are misinterpreting its wether it is possible to solve for variables in poly time not wether p=np is faster. The question was write an equation that exists as an^k not ak^n-1 where n is your variable

Originally Posted by fiveworlds

stuff

None of this has anything to do with the p=np problem as far as I can see.

P=np asks wether problems that can be verified in polynomial time also be solved in polynomial time. Does an eqn exsist that could solve them if you are imaginative enough. Yes because you can solve in polytime using the equation.

Originally Posted by fiveworlds

P=np asks wether problems that can be verified in polynomial time also be solved in polynomial time. Does an eqn exsist that could solve them if you are imaginative enough. Yes because you can solve in polytime using the equation.

So you are claiming to have proved p=np? Congratulations. What are you going to do with the money?

I honestly have no idea. Its more than most people i know make in ten years. im not a genius i honestly didnt think id make it this far i was just trying to understand it because i was interested. i dont know if the proof is perfect im not god and that eqn can obviously be improved. i obviously wouldnt have done as much without the help of you tk and the others though.

I think, if you really really found a way to solve one hard problem in just polynomial time, it still won't prove "P=NP".

IMO its like using "heuristics" to solve something really quickly. Which mean you use a specific insider knowledge about the problematic subject to skip certain calculation for that specific problem (only for this problem!). Its like a professional chess player doing a Chess AI; he coded this AI to do things he would normally do, so the AI do not search for new solution as much as it suppose to, but rely on the coder's solution (a shortcut!). (ie: chess AI in desktop computer can run quickly but only make moves found in chess book, but chess AI in "Deep Blue" require a supercomputer but can genuinely make new move unseen before by human)

I read in wiki that Karkarmar algorithm is not the most efficient but yet still able to solve its hard problem in a polynomial time. The hint is in the word "its not most efficient", it might mean the algorithm is using alot of memory to remember preexisting solution IMO, and this is "heuristic". http://en.wikipedia.org/wiki/Karmarkar's_algorithm (example of an algorithm that can solve 1 hard problem in polynomial time)

Originally Posted by fiveworlds

step11:if sum=0 return result if not run as exponential

How can you say you have a polynomial time algo and yet write this?

Ok, here is a little exercise. Given a number we know we only have to check numbers to find a divisor. Does this mean that factorization is a sublinear problem? If not, why?

this simply aint it...if u think you have solved the p=np problem,well datz for you.am not sure thats the problem..............................like the example my fellow african gave above,you only need to look for the root of n numbers,does this mean factorizin to get the values of root n numbers is easy?NO.if it is,does it mean that same numbers that you used in factorizin are also in root n?

river rat the if not run as exponential is just that there is a limitation to how effective i know how to make the filter. The better the filter the more strictly polynomial it can run. And i think it can solve for new variables using the poly eqn method. it doesnt matter if it uses a huge amount of ram because i am allowed to "to run on a turing machine". I also thought what i wanted was np-complete not np-hard i havent even looked at np-hard. Oh and does anybody have a link to karamarkars real algorithm the one that solve in poly time not affine scaling method

Originally Posted by fiveworlds

river rat the if not run as exponential is just that there is a limitation to how effective i know how to make the filter. The better the filter the more strictly polynomial it can run. And i think it can solve for new variables using the poly eqn method. it doesnt matter if it uses a huge amount of ram because i am allowed to "to run on a turing machine". I also thought what i wanted was np-complete not np-hard i havent even looked at np-hard. Oh and does anybody have a link to karamarkars real algorithm the one that solve in poly time not affine scaling method

So prove to me you can always find a polynomially bounded set of filters for any subset-sum problem. Also, have a look at my quiz I gave you - it addresses another problem in this exercise I have been ignoring until now.

Finally, please explain to me what and where the difference terms in the bounding equation you gave stand for.

I he

try out this recently released amaziiiiiiiiiiiiiiiing proof for P=NP.

http://www.scienceforums.net/index.p...attach_id=4364

As far as I know,
the complexity of problems is calculated by counting the steps of a turing machine that is used to calculate the solution to the problem by running a programme that implements the best-known algorithm that can solve the problem.
This means, one has to know what a turing machine is.

A turing machine consists of different parts of hardware: an input slot where a stripe of paper is fed containing the input (mostly a long row of different signs), a reading head that will read one sign of the paper in every step (numbers or other signs), a memory that will store for every step the read number or sign and the position of that sign on the paper strip, and a memory that will contain the algorithm ('computer programme') that defines the commands of the programme and the programme running pattern, some kind of processor with accumulator to perform the actual work. Last not least, the turing machine has a writing head that will write the output to the paper piece. To simplify it, the reading head and the writing head is considered to stay close together, always pointing to the same position on the input paper strip.
To summarize the functionality of a turing machine in a simple way, one can say that the turing machine reads one sign of the paper strip and overwrites it with some other sign. Then it moves its reading/writing head one position forward or backwards the paper strip. The sign that is used to overwrite the sign on the paper strip is defined by the algorithm which could be written down by the programmer like this: C(s0){'y','z',f}, C(s1){'y','g',b},C(s3){'y','r',b},...
and so on. The code can be read like this: Turing machine, if your head stands on position 0, and the sign read by your reading head is 'y', then overwrite the sign on the paper on the current position by the sign 'z' and move your head forward. Turing machine, if your head stands on position 1, and the sign read by your reading head is 'y', overwrite the sign on the paper on the current position by the sign 'g' and move your head backwards.
..and so on.
So the algorithm contains the overwrite command and the move command for the head.
By just reading the input and performing the defined overwrite command and move command in each time step, the turing machine can perform calculations, for example addition of binary numbers. Of course, the actual thinking is done by the guy who wrote the algorithm.
Example:
if I have the binary number 0111 (which is represented by 7 in our more common decimal system), and I want to add 1 to this number using the turin machine, I would proceed like this:
My strip of paper would read like this: 0111.
My algorithm would be in pseudocode: if position 0 on paperstrip reads sign 0, overwrite it with sign 1, move forward. If position 0 on paperstrip reads sign 1, overwrite it with sign 0, move forward. If position 1 on paperstrip reads sign 0, overwrite it with sign 1, move forward. If position 1 on paperstrip reads sign 1, overwrite it with sign 0, move forward, ... and so on.
If you grasp the idea: I tell the turing machine to write a one where the paper strip contains a zero, and I tell the turing machine to write zero where the paper strip contains a one. I will get the binary number 1000 (which is represented by 8 in decimal) after the turing machine finished its work on my paper strip: I performed the addition of 1 to a binary number. Of course, there would be the problem of an overflow if the first sign read 1, but I think it is a very simple example that is good to understand the function of a turing machine.

The difference of a deterministic programme and a non deterministic programme is easy to grasp: a deterministic programme will have a well defined command for every sign read on the paper strip. If you read this, write that and move there. A non-deterministic programme will not have a well defined command for every sign read on the paper strip, which means the turing machine has to be capable of making some sort of decision by itself, for example by chosing randomly between two different commands that are defined for the same sign read on the same position of the paper strip.
The important thing about this is, that the behaviour of a deterministic programme can be predicted, which can not be said for the behaviour of a non-deterministic programme.

Now I finally come to the meaning of polynomial deterministic problems and non-polynomial deterministic problems:
If we take our turing machine and our input paper that contains our binary number, and we count the steps that our machine needs to overwrite our strip of paper with the result, we can calculate the complexity of our problem (which is adding a one to a number in binary format):
for the input number 0111 (number of input signs is 4), we need 4 steps to calculate the result. For the input number 011111 (number of input signs is 6), we need 6 steps to calculate our result. And here comes the polynomial thing into play: if I can represent the relation between needed steps and the length of input (=number of input signs on my paper strip) in this form: n^k, with n being the length of input and k being some natural number (maybe a whole number, I am not really sure about that), it is a problem that can be solved by the used algorithm in polynomial effort, it is called a problem of polynomial complexity. In our case, we can calculate our complexity like this: n^1, and with our number 8 in binary form, we have 4^1.
If we try this out with numbers of different length, we can see that the result of needed steps can be calculated by just counting the length of the input. Therefore, we can be absolutely sure to have a problem that can be solved with polynomial effort (I'd say it is a problem of linear complexity, which is an underclass of polynomial problems). An algorithm with non-polynomial complexity would be an algorithm that would need 4 steps to add the number 1 to our binary number 0111, but would need 14333450 steps to add the number 1 to the binary number 011111, using our turing machine. The relation between length of input and needed steps doesn't fit the polynomial form n^k for any k (k being some natural number). Nobody would use such an algorithm, of course, because the problem can be solved with our simple algorithm of linear complexity.
Some of you will yawn here, but I know from experience that very simple examples are often the best ones.

Further more, because our algorithm is pretty simple, we can see easily that for each sign on each position, only one command is defined, and that is: read the sign on the current position (for example 1), write down the inverse (0) and move forward. Like I explained above, such an algorithm is called 'deterministic', with each programme step well defined. If we had an algorithm that says: 'read the sign on the current position and overwrite it either with 1 or 0', we'd have a non-deterministic algorithm.

Now, to see the whole thing from a more practical way: there are many problems that can be solved by our little turing machine with known deterministic algorithms of polynomial complexity. But there's a LOT of problems that can not be solved so easily, because we do not know any deterministic algorithms that would be efficient enough to calculate the result of the problem with n input length in a number of time steps that could still be presented by the n^k term. The number of needed time steps is much bigger and rises with another function, maybe exponentially, related to the number of input signs. Those problems can be solved with algorithms of exponential complexity or non-deterministic algorithms of polynomial complexity: those are algorithms, where problems are approached in another way, reduce the complexity of the problem from exponential to polynomial for the price of predictability. You are no longer capable to tell how your programme will decide when it reaches certain situations where it can execute different commands, perhaps by random decision. I didn't understand how that works. I'd guess that such algorithms work on a problem will they find a solution, and do so in a shorter time if the right (random) decision is made by the turing machine in the right (random) moment. With some luck, such an algorithm would have the chance to calculate the solution to a problem more quickly than a deterministic algorithm. However, I'd expect that it would also work much slower or get stuck in a seemingly endless loop because it repeatedly made the wrong (random) decisions. I'd also expect such algorithm to calculate results that would differ from the exact solution, or couldn't be proved to be the exact solution (because the programme run pattern can not be predicted and so the performed operations can not be put in exact mathematical relations). I'd expect non-deterministic algorithms to be quite something like a heuristic (something like an algorithm calculating a result that is not always the optimal result). But I have only superficial knowledge of theoretical informatics, and I quit reading Dirk W.Hoffmann's book about theoretical informatics on page 90 with a terrible headache. BUT I'd like to gain that knowledge. However, my ressources seem so hopelessly limited.

Sorry for the off-topic.
To return to the topic:
There are the so-called np-total problems. I think they are called np-total or something like that. Those are problems that are well-defined and well known among computer scientists and mathematicians and other studied persons, and for sure among people with personal interest as well. Those are problems that, if solved with the help of a deterministic algorithm of polynomial complexity, would prove that any problem that is up to now considered to be a problem of np-compelxity (only solvable through non-deterministic algorithms with polynomial effort), would be a problem of p complexity. That means, we'd only have to go on looking for smart algorithms of polynomial complexity and we'd find it in the end.
Most people seem to be quite sure that no np-total problem will ever be solved with a deterministic algorithm of polynomial complexity. If they are right, any search of algorithms for np-problems that would solve them in a deterministic polynomial effort would be a waste of precious time.
BUT if somebody ever proved them wrong and solved one of those np-total problems with some genious deterministic polynomial algorithm, he or she would be something like a superhero among scientists and earn a LOT of money ( I think one million $ or even more).
I think there are around 7 np-total problems defined up to now, but I don't know exactly.
One of them is this one I think:
put a certain number of things with different weight and monetary value into a bag, so the weight of the bag doesn't exceed some defined limit and the value in the bag is the maximal possible value.
It might sound like a simple task given to pupils on first sight, but if I stated it right (I think my memory serves me right in this case), it is quite impossible to find a deterministic algorithm that solves the problem with polynomial effort.
I think I forgot some important facts in my post, at least I got the feeling that I forgot to mention quite a lot, but I'm quite tired now, maybe I should have used google for some background information. I don't even know if all this makes sense what I wrote here, so maybe you can give me some feedback or delete the post if it's too off topic or not understandable or even total nonsense.

With greetings
Yoona939

wow you must have taken a lot of time to write that ill have a real read of it another time

well, yes. Maybe I wrote too much and maybe it's not even understandable.
To say it with one phrase: if somebody is interested to prove that p = np, then he or she would want to get to know the np-complete problems.
The 'only' thing he or she has to do is find an algorithm in p to solve one of those probs.
Here's the wikipedia link:
NP-complete - Wikipedia, the free encyclopedia
I'm sorry for my upper post, it was just too long and full of side-facts and much too simplyfied maybe.

And you think eventually p=np? I do not suppose so.

Probably millions of very smart people are working on that problem, some for the money and some because of idealism. And nobody has found a solution yet, you would surely know if somebody did. Read a book about it or at least wikipedia. There's a summary of the whole issue and also the np-complete problems there.
If somebody found the solution to that problem, he wouldn't post it on the internet. Mainly because he'd most probably need some years of hard study before, and it probably wouldn't be possible to fit his solution into those 5000 signs that can be postet here...just my opinion no offence meant.

im tired of explaining myself

Originally Posted by Yoona939

Now I finally come to the meaning of polynomial deterministic problems and non-polynomial deterministic problems:............I don't even know if all this makes sense what I wrote here, so maybe you can give me some feedback or delete the post if it's too off topic or not understandable or even total nonsense.

With greetings
Yoona939

A Turing machine is a model of predicting the reaction of a given machine (call it a computer) based on predetermined steps (call them programs) of data manipulation (call it data accessibility, data regulation, and data coordination). Binary system is a form of data that can be represented and manipulation by a Turing machine and in computer programming it is conventionally known as machine codes or raw data system or the basic language system.
Although the reaction of a Turing machine is based on manipulation of data through binary system, but the prediction of this reaction is based on the predetermined step by step procedures of the algorithm used to program it. So, while predicting the reaction of a Turing machine is the central point in its programming, but the algorithm used in such a program is the central requirement of determining the predictability of a Turing machine.
There are two requirements of determining the predictability of a Turing machine;
1- Resource requirements
2- Procedural requirements.

There are only two known resources that are required to complete a given pre - programmed prediction of Turing machine.

1a- Time resource
1b- Space resource
Procedural requirements are the central point in computer complexity. And it is a measure of the complexity degree of completing the processing cycles required to solve a given problem by a Turing machine and it is measured in time.
There are two types of such complexities;
1- The one which when given the algorithmic step by step procedures of a given program; the Turing machine reaches a certain point and automatically halts. The algorithm used in such a program is called decidable.
2- And the other one which when given the algorithm step by step procedures of a given program, the machine will never halt automatically. The algorithm used in such a program is called un decidable.

In computer complexity; the requirements of deciding a given problem falls into two categories of procedural complexity; one is call polynomial time procedure or specifically polynomial time, and another one is called exponential time time procedure or specifically polynomial time(but this is not so strict because though there is a strong argument to believe that sub exponential time is just the extra mile of polynomial time, but researchers have not concluded on this, so it still stands as another time dimension In computer complexity).

In the context of this reply, we are dealing with problems that can be solved in a given polynomial time procedure (hoping that you know the advantages of polynomial time procedures and why it is of such great importance to the community of computer scientists and mathematicians). We need to reconcile the NP procedural problems to the P procedures and thus the question whether P=NP.
The mechanism of proving NP-complete problems in polynomial time plays an un doubtable fact for the proof that P=NP – you were right as well as the authors of this fact. Such that; if any problem from the NP-complete list can be solve in polynomial time, other NP- problems can be reduced to such procedures so as they can also be solved in polynomial time. Some of the most outstanding and popular problems in this category is the SUB SET SUM problem, the CLIQUE problem of which the travelling sales man problem can be reduced and the Boolean sat problem. For the clique problem and the subset sum problem I think if you read the pdf from the link we provided you can notice how such problems can be solved in polynomial time.

Illustrating the above mentioned scenario by use of a simple program; let us use the text of your whole post. And let us call this program a “post texting administration program” such that any change of text made in this post is self regulated. We would say that;


If;= 1,

Then ;[IMG]file:///D:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtmlclip1\01 \clip_image004.gif[/IMG],



Else; add 1,

Or; subtract 1,

End if.

As we can see from the above illustration it only takes a procedural polynomial time of 1+ or -1 to administer the changes and reactions of texts made to and from our post texting administration program if the texts in the program have been optimized with in an equilibrium framework of reciprocal unity of 1.
The binary numbers (0,1) in mathematical point of view; are just logical patterns of differentiating the degree of form of the real variable (1) from its imaginary variable(0) as a rational framework of a given graphical, physical and numerical computational problem, but they are strictly NOT a measure of the procedural time complexity of a given computation process. They are only subject to memory complexity in form of space requirements.

When I was reading your post, I realized that you were not confident of the idea you were claiming. On this note please I advise; never be the first to doubt the idea you claim to the extent thinking that it will be nonsense. In the forum of ideas, in as far as the idea you claim is not obscene, vulgar or offensive being nonsense to someone, it does not mean that it will be nonsense to every one and at all times. After all even the most outstanding ideas up on which the civilization of humanity is based; were once nonsensical to some people and still are. So; nonsensical is just one form of subjective ways through which sense can be achieved. So far as you have grounds from which you base to claim an idea; the only objective nonsense in the forum of ideas, is the deliberate choice of ignorance when “feasible” knowledge has come to your understanding.

Originally Posted by merumario

And you think eventually p=np? I do not suppose so.

when it comes to math or computer science; we do not claim out of thinking or supposing,but we claim through proving with a mathmatical proof or disproving a proposed mathmatical proof.