suppose you have an oracle that given the relevant information can instantly return the optimal strategy to achieve your goal, how well does that oracle perform?
I guess CT experts (e.g. not me) would say it either depends on boring details or belong to one of three possibilities:
if you only care about « probably approximately correct » solutions, then it’s probably in BPP
if you care about « unrealistically powerfull but still mathematically checkable » solutions, then it’s as large as PSPACE (see interactive proofs)
if you only care about convincing yourself and don’t need formal proof, then it’s among Turing degrees, because one could show it’s better than you for compressing most strings without actually proving it’s performing hypercomputation.
My point is that there have to be straight up impossibilities in there. For example, if you had a constraint to only use 3 atoms to build a molecule, there are only so many stable combinations. When one considers for example nanomachines it is reasonable to imagine that there is a minimum physical size that can embed a given program, and that size also puts limitations on effectiveness, lifetime, and sensory abilities. Like e.g. you lose resolution on movement because the smaller you are the stronger the effect of Brownian forces, stuff like that, at the crossroads between complexity theory and thermodynamics.
I guess CT experts (e.g. not me) would say it either depends on boring details or belong to one of three possibilities:
if you only care about « probably approximately correct » solutions, then it’s probably in BPP
if you care about « unrealistically powerfull but still mathematically checkable » solutions, then it’s as large as PSPACE (see interactive proofs)
if you only care about convincing yourself and don’t need formal proof, then it’s among Turing degrees, because one could show it’s better than you for compressing most strings without actually proving it’s performing hypercomputation.
My point is that there have to be straight up impossibilities in there. For example, if you had a constraint to only use 3 atoms to build a molecule, there are only so many stable combinations. When one considers for example nanomachines it is reasonable to imagine that there is a minimum physical size that can embed a given program, and that size also puts limitations on effectiveness, lifetime, and sensory abilities. Like e.g. you lose resolution on movement because the smaller you are the stronger the effect of Brownian forces, stuff like that, at the crossroads between complexity theory and thermodynamics.
I see, thanks for clarifying.