Why you anyone think P=NP

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > Why you anyone think P=NP

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

there's been a lot of discoveries that moved stuff close to P than they used to be. we think we know everything mathematically, but we're pretty drat far away

# ¿ May 14, 2017 19:10

Adbot: ADBOT LOVES YOU

# ¿ May 14, 2024 20:27

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

just think of problems that need to be guessed and checked until the solution is found vs ones we know the operation it takes to solve it right away

# ¿ May 14, 2017 21:30

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

Stymie posted:

there was an engineer at hp a few years ago who produced a proof that p=np but it was quickly hushed up because it basically would have destroyed the computer touching industry

there's been like a thousand proofs that p=np, and there's always errors found in their work

# ¿ May 15, 2017 01:45

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

JewKiller 3000 posted:

people "knew" that fermat's last theorem was true because it's a simple calculation that you can test for many numbers to see a pattern. if you run a program to do that for a long time and see that it's always true, you have pretty strong evidence to believe the conjecture. that's not a general proof, because really big numbers can and do change the result unexpectedly. but even if you're satisfied with the unproven belief, you don't really know why it's true, you just found a pattern and declared it a law, you haven't really understood the nature of the universe any better. the ultimate proof of fermat's last theorem linked different fields of math together in previously unseen ways, and those discoveries will have far more lasting value to mathematics than simply a definitive answer to fermat's conjecture

P vs. NP is a question about classes of problems, there's no way of just running it a bunch of times and convincing yourself that it's true. all you can do is look at the body of research work and conclude that because no one has been able to solve these problems efficiently, they must be fundamentally hard. but no one was able to solve relativity before einstein, so what if we just need the computing version of einstein to come along and revolutionize everything? don't you want to be that guy? it seems like we're gonna need him anyway even to prove that P != NP, because no one has the slightest idea of how to do that, which doesn't exactly inspire confidence in our current understanding of the hardness of these problems, does it?

this is excellent stuff. you should write a book

# ¿ May 20, 2017 22:58

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

qkkl posted:

For a given NP problem there are algorithms that are faster than others. One might wonder if the algorithms could be improved to the point that they run in polynomial time. It's like asking "Can a human run 100 meters in under 8 seconds?" One might think it could be possible if they look at the world record times and see that they are improving over the years.

it's not really how fast, more that the answer keeps on needing to be checked until correct, i.e. sorting needs to be checked. there's algorithms, but it's not as simple as applying an equation and having it spit out an answer immediately

# ¿ May 22, 2017 15:37

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

Silver Alicorn posted:

what if we made a computer so vast and efficient, it could simulate the entire universe faster than the universe itself existed?

i think you could if you hack elementary particles and make more efficient ones, way better than "god's" lovely implementation

# ¿ Jun 5, 2017 21:38

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

you could make a computer that simulates the universe on an extremely slow level compared with the current universe, but the observers inside the simulation would perceive as normal speed, just like we do in our simulated universe

# ¿ Jun 5, 2017 21:40

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

Sagebrush posted:

Speaking of this: what's the current best guess as to whether photosynthesis is (a) extremely optimized and pushing the limits of efficiency after billions of years of evolution, or (b) a stupid nature hack full of problems and dumb pathways and scientists will soon be able to make their own better version that lets us have bright green cars that run forever on sunlight and water

i can tell you this: photosynthesis REALLY hates the color green for some reason and throws that poo poo out the window back into our eyes for us to see

# ¿ Jun 6, 2017 03:35

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

Silver Alicorn posted:

I'll bet modern PVs are already more efficient than plant based photosynthesis

they aren't, but getting better

# ¿ Jun 6, 2017 03:36

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

Larry Parrish posted:

There are plants with leaves that aren't green, folks. Its just that the green-reflecting kind of clorphyll is apparently more competitive or at least just ended up more common

not many, and the leaves that aren't green are considered loving nerds

# ¿ Jun 6, 2017 15:12

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

i don't know if i like the video.. he mentions sorting. checking sorting can be done in polynomial time, but actually sorting - isn't that np?

# ¿ Jun 6, 2017 15:27

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

rapeface posted:

Cheat sheet here, generally n log n.
https://en.m.wikipedia.org/wiki/Sorting_algorithm

theoretically there's nothing that proves that there could be something faster depending on which you're using for the appropriate case, or was it proven in any use case?

LP0 ON FIRE fucked around with this message at 20:11 on Jun 7, 2017

# ¿ Jun 7, 2017 20:07

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

thanks that is good info

it just sounds like to me sorting (or for now) is sort of np because in any case, you need to keep checking to see if you have the correct answer

# ¿ Jun 7, 2017 21:40

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

drat it

okay then i guess i'll try to make an algorithm for finding new monohedral convex pentagonal tilings
https://en.wikipedia.org/wiki/Pentagonal_tiling

# ¿ Jun 7, 2017 22:27

Adbot: ADBOT LOVES YOU

# ¿ May 14, 2024 20:27

LP0 ON FIRE: Jan 25, 2006; _{beep boop}

Cybernetic Vermin posted:

ah, i think i see what your confusion is: what we certainly know is that p �� np. for sorting any sorting algorithm will indeed also in effect check whether the list is sorted (since it has little choice but to make repeated comparisons). it is the case in general as well, but it gets into slight technicalities at that point as these are "decision problems" (i.e. only yes/no answers, no actual output)

that is, in this informal sense, np is the set of problems where one can in polynomial time *recognize* that a given solution indeed is a solution, where p are the problems where one can in polynomial time *create* a solution (which *implies* being able to recognize it). so, if these are the same, p=np, then it is sufficient that solutions can be recognized, there exists some general way to (efficiently) rework the recognition of solutions into an algorithm for the construction of solutions (and, as this is in polynomial time this general way is more clever than just enumerating all possible solutions)

i think it has clicked for me and this helps thank you. for finding the best move in chess, depending on how the board is setup, you have to iterate through all the moves and somehow prove that one is the best, which are effected by future moves, etc. that is np. linear sorting is simple y/n to check if it's sorted, even if it needs to make repated comparisons

# ¿ Jun 8, 2017 14:50

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > Why you anyone think P=NP