Computational Depth Oracle Questions (ChatGPT prompted w Fortnow depth publication and P = NC literature

oracle.md

Oracle 1: Perfect Retrieval Suppose an oracle answers every factual question instantly. The model never forgets anything. Question: Does theorem proving become easy? If not, then factual knowledge wasn't the issue. This separates memory from reasoning. Oracle 2: Perfect Search Suppose an oracle instantly returns the best next action among all possibilities. Question: Can the system now solve difficult planning tasks? If yes, search was the bottleneck. If no, representation or evaluation may be the bottleneck. Oracle 3: Perfect Verifier Suppose an oracle instantly tells you whether a candidate proof is correct. Question: How much of mathematics remains hard? This distinguishes: generating ideas checking ideas The latter is often much easier. Oracle 4: Perfect Heuristic Suppose an oracle always ranks candidate thoughts in the ideal order. Question: Does reasoning collapse into a simple search process? This is particularly relevant to modern AI. Many systems spend enormous compute evaluating possibilities. A perfect heuristic oracle would reveal how much of intelligence is "good guidance." A computational-depth oracle This is where the Fortnow paper becomes especially interesting. Suppose we ask: Is intelligence mostly stored depth or generated depth? Imagine two oracles. Oracle A: Infinite Knowledge The system knows every theorem ever proven. Every textbook. Every paper. Everything. But it cannot perform long sequential computations. Can it do frontier science? Maybe not. Oracle B: Infinite Compute Depth The system knows almost nothing initially. But it can perform arbitrarily long chains of reasoning. Can it rediscover science? Potentially yes. The comparison helps identify whether a task is fundamentally about stored information or generated computation. This is exactly the distinction computational depth is trying to illuminate. The oracle I'd most want for AI If I were formalizing modern debates, I'd define: The Reasoning Oracle Given a state s, the oracle returns: f(s) where f is the result of an arbitrarily long but polynomial-time reasoning process. Then ask: How much capability remains after removing reasoning? If an LLM with this oracle suddenly becomes superhuman, then reasoning depth was the scarce resource. If capability barely changes, then something else was scarce. A Fortnow-style reformulation of AI questions Many current AI questions become much sharper. Instead of: Can LLMs reason? Ask: Relative to an oracle for factual retrieval, what additional computational depth is required to solve the task? Instead of: Can LLMs do science? Ask: With an oracle for all existing scientific knowledge, how much sequential computation is still required to make new discoveries? Instead of: Is chain-of-thought important? Ask: If an oracle supplied the optimal next thought at each step, how much of the remaining computation disappears? These are questions complexity theorists know how to attack. The deepest oracle question The question I suspect Fortnow would find most interesting is something like: Is there a relativized world in which enormous knowledge and pattern recognition exist, but intelligence still requires computational depth? In complexity notation, that's roughly asking whether there are oracle worlds where: Knowledge  =Reasoning in a rigorous computational sense. If such separations exist, they would support the intuition that scaling model size and scaling reasoning depth are fundamentally different resources rather than two ways of buying the same thing. That's the kind of oracle thought experiment complexity theory excels at: not solving the problem directly, but forcing us to state precisely what resource we think intelligence is consuming.