I'm trying to improve my understanding of complexity classes by reading the complexity zoo here, https://complexityzoo.net/Complexity_Zoo, and a number of other resources. I'm having an argument with a friend about a certain problem which I am hoping to resolve.
Suppose you have a machine, call it a 'mystery box'. Inside is a random integer. You can query the machine with an integer, and it will respond "yes" or "no" as to whether you have guessed the integer correctly.
Or, if you like, extend the idea to a 'mystery boolean circuit' inside the box. You don't know the configuration of the circuit, but you have access to the inputs and output, so you can query the circuit and see if you have satisfied the circuit by checking the output. If the circuit is not satisfiable, then call that equivalent to an empty box in the paragraph above.
The question is, if this is a decision problem, what complexity class does it belong to? Is it meaningful to assign a complexity class to this problem? Is the problem well defined enough?
Very interested to hear other thoughts on this!