Comment by omnicognate | Hacker News Reader

Comment by omnicognate | Hacker News Reader

> Indeed, a fast program that correctly answers the P vs. NP question trivially exists:

> If P=NP, then the program prints “P=NP.”

> If P≠NP, then the program prints “P≠NP.”

That's not a program, it's two programs. Likewise for the theological "function" at the start. If it were to determine whether God exists it would need inputs on which to base that determination. Instead, two functions are presented along with a theological rule to choose between the two. The properties of the functions have nothing to do with the theological question.

I get that that's the point of the article, and that the quoted homework question correctly refers to two functions. I just felt that it wasn't particularly clearly spelled out and that the article seemed to blur the distinction between the functions and the choices between functions, which would probably further confuse those suffering from the misconception he describes (while heaping scorn upon them).

Edit: And this seems to really muddy the waters:

> The deeper lesson Sipser was trying to impart is that the concept of computability applies to functions or infinite sequences, not to individual yes-or-no questions or individual integers.

Regardless of Sipser's motivations the question doesn't say anything about the difference between individual values and functions/sequences. What it reveals is the difference between a well defined mathematical function and a choice one might make or imagine between various such functions (the criteria for which may or may not be well defined).

I could replace the question about God with one about whether some other function (which we haven't yet determined the computability of) is computable and it would still be the case that "the function we have defined is computable". (Scare quotes because that's actually a category error and the correct observation is that "both functions we have defined are computable". Hmm, well given the computability of the third function is well defined, though unknown, I suppose in this case we actually have defined a single unknown function, but the point about the difference between the choice and the functions stands.)

He’s saying that because those two programs exist, there exists a program that correctly answers the P vs NP question. We don’t know which of the two it is. But equally, 50 years ago we would not have known whether to choose the program “Fermat’s last theorem is false” or “Fermat’s last theorem is true”. Still, the second program has always existed and has always printed the correct answer (at least if you sub in the theorem in pre-Fermat times).

But "we don't know which of the two it is" handwaves away that "answering P vs NP" means precisely coming up with the proof!

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.

Part of the point is that computability is different from knowing how to write a program that actually computes the desired value. We can say a program exists to print whether P=NP (whether it is computable) without knowing how to come up with a concrete implementation of that program.

Proving P vs. NP and answering the question correctly are two different problems.

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.

Nit, decision problems are one type of computable problems, but you have other types like function problems, optimization problems, etc.

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.

> ... handwaves away that ..

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.

> But "we don't know which of the two it is" handwaves away that "answering P vs NP" means precisely coming up with the proof!

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.

I think the intuition people want to apply here is that ‘is P=NP’ feels like an instance of a class of questions - ‘is P=x’, and if that is computable, then it implies we can attack P=NP by coming up with a way to compute it and feeding in NP.

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

The whole point is simply that the notion of computability is not related to coming up with proofs or to any mechanical process for arriving at a result based on a set of axioms. "Computable" and "Provable in ZFC (or whatever)" are just two different things and pertain to different mathematical objects. Functions are computable (or not). Theorems are provable (or not).

Correct, the author did not describe a program that computes whether P = NP. He merely proved that such a program exists, by describing two programs, and showing that one of them must be the one that computes whether P = NP (we just don't know which one, but we at least know that it exists).

> I could replace the question about God with one about whether some other function

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

> That's not a program, it's two programs

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

isn't it actually one program? Imagine the implementation using an oracle.

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.”)

I don't think that's what he was referring to. Apart from not being "fast", it's not a program in the sense being discussed here, given the article is about computability. It's an oracle turing machine rather than a plain turing machine, and oracle turing machines can trivially side step computability questions by having the oracle evaluate the noncomputable function.

(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.)

nit:

> 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:

I would say it's because this is pseudo code and it is a lot clearer that way.

Depending on language

>if response:

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

To me there's no other way to interpret it, really, except as one function. The if-then part of it is part of the function definition.

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.

> The if-then part of it is part of the function definition.

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.

It is one program. If P=NP then the body of the program consists of "print(P=NP)". And otherwise it consists of "print(P!=NP)". [1]

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 :)

Reply on news.ycombinator.com