3 ms·
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.
by jltsiren 2y ago
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.
- nyrikki 2y agoNit, 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.