Those constant functions aren't proofs, the proof is in coming up with a series of computable steps to reduce a model of P=NP into that constant function. That is, the proof is the computation itself, not just the constant value.

What the author did describe is a function that we can only evaluate when we already have an answer for P = NP, not a function that computes it.

Computability is defined in terms of functions that map the input to yes/no. A function is computable if there exists a representation that computes it correctly for any input and eventually terminates. Every yes/no question where the answer does not depend on the input is by definition computable. The corresponding function is either the one that maps every input to "yes" or the one that maps every input to "no". We may not know which one, but that's irrelevant.

In some sense, computability is similar to probability. Your intuition is wrong, and following it only leads to further confusion. But if you unlearn it and rebuild it from basic principles, things become much clearer.

NP, by definition involves decision problems, but many NP-Hard problems are optimization problems.

More specifically NP is the set of decision problems solvable by a NTM in poly time with the following conditions:

1) If the answer is "yes," at least one computation path accepts. 2) If the answer is "no," all computation paths reject

Equivalently is is the set of decision problems verifiable by a TM in poly time.

Modern programming tends to only care about #1, and structured programming paradigm helps with that.

People not moving past NP in complexity theory is the real problem here. I also blame using the 'trys all answers at once' NTM intuition vs the max lucky guesser which makes it less silly.

But didactic half truths do really hurt. Entscheidungsproblem is better for teaching people in my experience.

Of course it's a not a proof of "P=NP", but no one is asking for it.

> What the author did describe is a function that we can only evaluate when we already have an answer for P = NP, not a function that computes it.

Yes. This function is still computable though. The question of computability doesn't depend on humans being able to evaluate this function on a given day in history.

But I think the issue there is the assumption that it even makes sense to define a function over ‘classes of questions’.

These kind of handwaveing are quite common in math. For example, Axiom of Choice assume there exists a choice function. It does not specify how.

Saint Anselm's Ontological Theory of Computation. "First.. imagine the most perfect function that could possibly exist.."

Yes, and one of them is "a fast program that correctly answers the P vs. NP question". We don't know which.

You being a clever programmer somehow know of a very powerful oracle, lets call the oracle Pauli. You're program works as follows:

  func main():

    response = write_pauli_asking_if_p_is_np() //synchronous, waits for response 

    if response is true:
      print(“P=NP.”)
    else:
      print(“P≠NP.”)

(This is of course not relevant to the oracle you suggest as that doesn't evaluate a noncomputable function, but it's relevant to what sort of "program" Aaronson is talking about here.)

The example is genuinely confusing to me because of the igtheism problem: the idea that the question of whether God exists is a poorly posed one, because God is undefinable. It's like dividing by zero or a type error or something. This was Bertrand Russell's perspective, for example.

Maybe the intent of the example is "here is a function whose inputs are unknown" but for me it was more like "here is a function whose outputs depend on an undefinable input."

The second example didn't seem much better for the same reason. Knowing that the output is prime regardless of the input — a logical conclusion from the "meta evaluation" of the function — doesn't seem to me to be the same as asking whether the function is computable.

To me it's like having the function depend on a contingency sort of like "if the color blue tastes like cheese, then..." It doesn't make sense.

If the example was meant to incorporate an unknown state (as opposed to an undefinable one), it would have been better off with a random unseen event or something, like a person flipping a coin in a different room. Or a particle decay in a box, but then that leads to quantum issues maybe which leads to the same sort of problem possibly.

No, it isn't. The if-then part of the question is about which of two trivial functions the label "f" refers to. It has nothing to do with the functions themselves or their computability. That, from what I can gather, is supposed to be the point of the question, but I don't think the question gets that point across very well.

> if response is true:

i've always wondered how people know when to stop (which, i guess, is relevant to the subject matter).

e.g. why is your next step not

> if (response is true) is true:

Depending on language

>if response:

could mean "response" is true,1,not empty, X....

Similarly for every hash function there exists a program that outputs a hash collision in well under a second. Just hardcore any collision and print it to the screen. [2]

[1] If you want to be pedantic then there's a third option that prints some more complicated statement about the relationship between standard axioms and P?=NP.

[2] Please don't ruin my short argument by pointing out that someone can create a hash function with output size in the petabytes range :)