P=NP

[fiveworlds]

For P = NP I must prove that a Non-Deterministic algorithm can be the same as
a deterministic algorithm. A Non-Deterministic algorithm may use random variables to change the algorithm based on different inputs. For this I am using the current time which is just
a counter to generate a random variable in a deterministic manner. We will assume that
the non_deterministic is truly random yet the deterministic algorithm is pseudo
random. It equals the exact same thing though.

<script>
function deterministic(input){
var d = new Date();
var n = d.getTime();

var n =""+n+"";
var rand = n.slice(n.length-1,n.length);
document.write(input*rand);
}

function non_deterministic(input){
rand = Math.floor((Math.random() * 10) + 1);
document.write(input*rand);
}

deterministic(10);
non_deterministic(10);
</script>

[ydoaPs]

How do you propose getting truly random variables?

[fiveworlds]

How do you propose getting truly random variables?

 

Exactly you can't really. That's why there really are no non_deterministic algorithms. You could also say that every Non_Deterministic algorithm is actually just a Deterministic algorithm mislabeled because the randomness could be considered as an additional input.

[ydoaPs]

 

Exactly you can't really. That's why there really are no non_deterministic algorithms. You could also say that every Non_Deterministic algorithm is actually just a Deterministic algorithm mislabeled because the randomness could be considered as an additional input.

 

It's not as though it's impossible. You'd just need an extra bit of hardware. Use as your seed variable(s) the timestamp of a decay of an atom of a radioactive source. A detector picks up the decay, logs the time, sends it to the number generator. Boom, an encrypted truly random number generator.

[Strange]

It's not as though it's impossible. You'd just need an extra bit of hardware. Use as your seed variable(s) the timestamp of a decay of an atom of a radioactive source. A detector picks up the decay, logs the time, sends it to the number generator. Boom, an encrypted truly random number generator.

 

 

Available here: https://www.random.org

 

I'm not sure I see the relevance to P vs NP, though ...

[fiveworlds]

I'm not sure I see the relevance to P vs NP

 

NP is an extension of P which incorporates the use of true random numbers. So the question asks can I generate truly random numbers? Von Neumann suggested that it was impossible to generate true random https://en.wikiquote.org/wiki/John_von_Neumann

Edited July 24, 2016 by fiveworlds

[Strange]

 

NP is an extension of P which incorporates the use of true random numbers.

 

 

That sounds more like P = BPP

http://www.claymath.org/sites/default/files/pvsnp.pdf

[fiveworlds]

That sounds more like P = BPP

 

 

BPP is the set of all algorithms that can be recognized by a truly random polynomial time algorithm. For BPP to exist you must prove that true random is real.

[Strange]

 

 

BPP is the set of all algorithms that can be recognized by a truly random polynomial time algorithm. For BPP to exist you must prove that true random is real.

 

 

Which seemed to be your original point.

[fiveworlds]

Which seemed to be your original point.

 

Yeah. BPP is really a set of tests for your truly random number generator which it must be able to satisfy in order to be classed as truly random.

[Strange]

 

Yeah. BPP is really a set of tests for your truly random number generator which it must be able to satisfy in order to be classed as truly random.

 

 

Huh?

 

Anyway, as far as I am aware random numbers have nothing much to do with P vs NP.

[fiveworlds]

Anyway, as far as I am aware random numbers have nothing much to do with P vs NP.

 

Basically what I am saying is that I don't believe there are any non-deterministic algorithms. So since NP = non-deterministic algorithms + deterministic algorithms(P) AND non-deterministic algorithms = 0. Then NP = 0 + P = P

[Strange]

 

Basically what I am saying is that I don't believe there are any non-deterministic algorithms. So since NP = non-deterministic algorithms + deterministic algorithms(P) AND non-deterministic algorithms = 0. Then NP = 0 + P = P

 

I'm sure the cheque for 1 million dollars is on the way.

[fiveworlds]

I'm sure the cheque for 1 million dollars is on the way.

 

I wouldn't want it. https://msdn.microsoft.com/en-us/library/ms178091.aspx states what non-deterministic algorithms are and gives a few examples one of these is the GetTime function. They state this is non-deterministic because with the same input it gives a different output but this isn't true at all because the string it reads from memory is in itself an input to the function and therefore the function is deterministic.

[Strange]

 

I wouldn't want it.

 

Good. You won't be disappointed then.