Complexity theory question:
NP-Hard is the set of all problems “at least as hard as the hardest problems in NP”
Is there an analogous “at least as hard as the hardest *decideable* problems”?
Like is there a class “Decideable-Hard”?
[ boosts appreciated :) ]
Triple congrats !!!
#CHM #computerhistorymuseum
2023 Fellows Awards
Thomas E. Kurtz — #basic
Barbara Liskov — #LSP
MOUNTAIN VIEW, Calif. — June 28, 2023 — The Computer History Museum (CHM), the leading institution decoding technology—its computing past, digital present, and future impact on humanity—today proudly announced its 2023 Fellow Award honorees: Rodney Brooks: For the advancement of robotics and consideration of its implications for humanity. Thomas E. Kurtz: For the co-invention of the …
A question that came to mind, possibly interesting or trivial: for TV (ℓ₁) there is no dependence on n in the entropy loss. For ℓ∞ a logarithmic dependence pops up.
Does it suddenly appear? Or does it gradually appear when one looks at ℓp guarantees for increasing p? #hashing #computationalcomplexity #theoreticalcomputerscience #theoreticalCompSci #randomness
Residual Entropy (I'VE MOVED!)
Teixi
Clément Canonne