|
we are imbeciles
|
#
¿
May 14, 2017 19:17
|
|
|
|
| # ¿ May 14, 2024 14:04 |
|
|
a canonical easy to check hard to solve is any cryptographic hash
|
|
#
¿
May 15, 2017 07:24
|
|
|
the traveling salesman equivalent would be what is the shortest input that gives the correct hash or, the other way around, traveling salesman is asking two questions: what's the shortest possible path, and what is one of those paths. checking that one of those paths is that length is easy but checking if it's the shortest possible is hard in the different kinda way I think
|
|
#
¿
May 15, 2017 07:30
|
|
|
A Pinball Wizard posted:how is polynomial time defined? im guessing "in one lifetime" isn't an actual si unit. broadly it's the category of O(n^K) where k is basically just the number of nested loops your algorithm needs
|
|
#
¿
May 15, 2017 15:57
|
|
|
brute forcing traveling salesman, on the other hand, is O(n!) aka get hosed
|
|
#
¿
May 15, 2017 15:58
|
|
|
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? information theory would show up and say "no" and then it wouldn't work
|
|
#
¿
Jun 5, 2017 17:05
|
|
|
LP0 ON FIRE posted: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 lol yeah whats up w/ that
|
|
#
¿
Jun 6, 2017 04:07
|
|
|
|
| # ¿ May 14, 2024 14:04 |
|
|
LP0 ON FIRE posted: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? didnt watch the video, but sorting is n log n which is better than most polynomials
|
|
#
¿
Jun 6, 2017 16:42
|
|