Sounds implausible… Number of computational steps to find the shortest sequence ... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		bjornsing 3 months ago \| parent \| context \| favorite \| on: The Halting Problem is a terrible example of NP-Ha... Sounds implausible… Number of computational steps to find the shortest sequence maybe grows with Ackermann function. But length of the shortest sequence?

trixthethird 3 months ago [–]

I think you are right. I just read this article linked in the OP: https://www.quantamagazine.org/an-easy-sounding-problem-yiel...

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact