Does P = NP?
Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.
You are currently reading a thread in /g/ - Technology
You are currently reading a thread in /g/ - Technology
>>51852301
Pretty much every computer scientist will say no.
epic /sci/ meme
>>51852301
probably not.
>>51852301
If P = 0 then yes
>>51852301
I wish it did. It would be hella cool if it did, but I just don't think our current understanding of computing will ever be able to achieve P = NP. Whether thats just the limitation of the current understanding of computing, or an actual impossibility, I doubt we'll know in our lifetimes.
Doesn't Shor's Algorithm demonstrate that NP can indeed be P?
>>51852326
But there's the POSSIBILITY that it's true.
>>51852810
Factoring primes isn't even NP-complete.
>>51852301
We don't have to a give a shit anymore.
http://www.iflscience.com/technology/googles-quantum-computer-appears-be-100-million-times-faster-conventional-one
>>51852372
Could be true if n = 0 also, or if n = p = 1
>>51852301
No.
Proof:
Consider the problem relating to P = NP.
Obviously, if one can solve the problem, it can be shown that the problem that the question P = NP is NP complete. However, we have not been able to show that P = NP is NP complete, so therefore P =/= NP. []
>>51853661
If N = 0, you can still have P ≠ 0 (e.g. P = 1) and then you won't have P = NP (e.g. P = 1 ≠ 0 = NP).
is that a dildo collection?
>>51853667
Good luck collecting the prize money with that proof, senpai.
>>51852301
No.
If P = NP, then problems that can be solved in polynomial time by a hypothetical non-deterministic computer can be solved in poly time by a deterministic computer.
Translation: there is some way, some how, for an actual physical computer to take random guesses and always get the correct one. That's idiotic.
We don't know. I'm scared if we find out it does.
>>51852414
>It would be hella cool if it did
No it wouldn't, say goodbye to any form of privacy and anything that relies on encryption at all.
>>51853412
P=/= NP. You can't make the formula for pi any easier to solve with any input... because it goes on 'forever' i tried writing a paper saying this to get the money but i could never find the words to accurately describe it.
>>51854294
Is the formula for pi np complete?
>>51852301
who cares, it's a meme problem we'll probably never figure out
>>51854314
It has to be lol could any computer (including quantum) reach the end of pi in polynomial time? Lol fat fuckin chance
>>51854294
I think you're misunderstanding the issue
>>51854341
Pi isn't an NP problem
>>51854344
What am i misunderstanding? Its asking if any problem can be solved within reasonable time given the amount of operations? No?
>>51854379
We're only asking if NP problems are also P problems. There's also other complexity classes.
>>51854379
Assuming the problem has an end.
>>51854341
Actually pi can be solved as 3.142857...
This basically states pi is 3.142857 followed by a bunch of shit no ones gives a fuck about.
>>51854413
But the real answer isn't assuming the rest is pointless? The real answer is the entirety of pi not just doing a fraction of the problem then tapping out and saying "close enough"
>>51854405
Exactly the np problem that is pi cant be reduced any simpler. Its a one operation problem.
>>51854456
pi isn't np complete and neither is infinity + infinity.
N=1->P=NP
>>51854486
Why wouldn't it be? Also pi is dealing with real numbers not anything arbitary like infinity
>>51854517
Checking all digits of pi is non-deterministic. It can't be in NP.
>>51854532
This. You cannot check the solution of pi in polynomial time basically.
>>51852334
Define P & NP
>>51854552
If it cant be done in polynomial time doesn't that mean its np?
>>51854588
NP: Given a solution, it takes polynomial time to check if it is correct
P: The solution can be found in polynomial time
This whole thing reminds me of the pixel debate.
Take a black and white pixel. When there is one it only has two possible states and you can't see much. Now say there are ten thousand of them. Suddenly they can make any possible picture. You could see anything. The future, the past, alternative history, etc.
So it depends op.
>>51854588
"Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known."
https://en.m.wikipedia.org/wiki/NP-completeness
The problem is there is no way to check the solution for the pi formula.
>>51854563
{
char p = "OP";
char np = "fagget";
p = np;
return = reddit;
}
>>51854683
That wouldn't compile
>>51854413
>3.142857...
I'll just assume that you pressed some wrong keys and you aren't really this stupid...
>>51854696
>implying you couldn't write a compiler for that language
>>51854413
But pi is 3.14159265...
Did you just make up random digits after the 4 to see if anyone would notice?
def pnp():
if (n == 1):
p == n * p
elif (p == 0):
p == n * p
else:
p != n * p
>>51854683
error of compilation, line 5 error syntaxis.....
I have an elegant proof to show P != NP that I would post but I need to go feed my cat; also, there is not enough characters allowed for it to fit in the text field.
>>51854720
We got bamboozled m80
>>51854654
10000 bitmaps can't make shit.
You literally would not be able to make out a photo of dung.
>>51852301
Letters cannot equal each other. Do stupid physicists honestly believe that everybody will understand their scribbles? Write whole words goddammit.
>>51854683
>char
Yes, but by process of computing every calculation permutable, you take up much more time than just calculating in polynomial time.
>>51854140
ez pz lemon squeezy
>>51852301
>polynomial time
>non-polynomial time
Obviously these aren't equal. Why not word it more sensibly, like "g exists for all f such that f(NP) = g(P)"?
>>51852810
BQP != P
>>51854683#include <assert.h>
#define p "OP"
#define np "fagget"
int main()
{
reddit:
assert(p == np);
goto reddit;
}
P ≠ NP
>>51857868
>>non-polynomial time
b8
it's nondeterministic polynomial time.
Civil engineer here.
Pi=22/7 you dumb fucks.
>>51853412
No.
Because otherwise a lot of problems that aren't "easy" to solve would be "easy" to solve. Which they are not (practically).
>>51860948
mathematician here. pi != 22/7. pi is bounded above by 22/7. fucking idiot engineers...
>>51852301
Pretty sure it was proven that P != NP. Saw a thread on /sci/ earlier.
>>51861263
kek. Pretty sure we would have heard about this somewhere other than /sci/.
>>51854810
Fermat was probably just bullshitting like you
>>51861662
There was a pdf linked in the thread. I have it downloaded. I can upload it somewhere and post it if you'd like
>>51853772
No shit moron. You knew what he meant
>>51861204
>Mathematician
C_uckold by definition senpai..
take f(x)
for any value x, a certain value of f(x) is generated.
so by calculating f(x) for every possible value of x, we can obtainf(x):
switch x
case x=a
return z
case x=b
return y
case x=c
return xbutnotx
case x=d
etc
etc
etc
So does p=np given that there is a limit of inputs we can give the function?
>>51861842
I would love to see that proof. Has it been peer reviewed yet?
>>51852326
Donald Knuth disagrees
>>51861139
The point is that we haven't discovered the easy solutions yet if P = NP
>>51863105
perhaps the alternative answer is that the easy solution does not necessarily exist, and that the answer P is in fact very long.
>>51861875
Yeah, but at least I know what pi is...
>>51854532
>non deterministic
>can't be in non-deterministic polynomial class
I think you might wanna rephrase, there, champ
>>51863459
Indeterminable would probably have been a better word.
>>51863504
Actually, I think that determining if a number is pi or not is a closed problem (solved in O(1)): the answer it's either yes or no, you just need infinite time and memory.
It's not dependant on the input size, which is also why that anon's proof is shit.
Every magnitude of polynomial is another nested loop.
O(0) is z,
O(1) is for x{z}
O(2) is for x{for y{z}}
etc
Hence at each loop, if we can calculate all the results possible from the set of values a the functional contents a loop will take, then we can rewrite the loop as a switch statement of each value the variable can take;
as pointed out in >>51862199
however, for a loop such as n{+1} -> +n, this can be expressed in O(1) time, as the inner function is O(0) anyway, and needs no conversion of for into switch; that is to say that when cancelling the loop out, we can use the O(0) function instead of a switch.
So takeg(x):
x = (byte)x
for 1->x:
n+=2
n +=3
this can be rewritten as functions and loops; beingg(x) = a(B(c(x)))
a(X) = X+3
B(X) = for 1->X b(N)
c(X) = (byte)X
b(X) = X+2
where a capital function is a loop, incrementing the polynomial time by 1.
Let's assume we can't multiply in O(0) time. Thus we must use a switch to expand B.
In this case the set of values B can take is in fact only 256, thanks to function c. Had c been something other, the size of the switch statement could have been much larger.
Following this, function a CAN be written in O(0) time (hence it's not capitalised), and so no effect is made on the time to run.
Hence beyond O(n), I can mark out a rough T(n) for the time it takes something to run in O(0) time- essentially the size of the switch statement. A function that reduces the set of values the loop goes across will reduce the T(n) time, saving an O(2) problem from becoming a switch statement of 2^32 cases if the problem takes an int.
Take note, however, that a function A(B(x)) with nested loops that cannot be reduced into O(0) time by other means, is still reliant on only 1 variable, and can be taken as simply C(x). In the case of any unsimplifiable loop, the function C(x) can be expanded to every case of x, ignorant of whether B(x) can be simplified or not.
