Skip to main content
edited body
Source Link
Steven
  • 29.6k
  • 2
  • 28
  • 49

Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given short proof of mathematical statement is valid then there must exist an algorithm $B$ that decides whether such a short proof exists. Let's use $B$ on the statement $\mathsf{P}=\mathsf{NP}$.

There are several problems with that. First it assumes that $\mathsf{P}=\mathsf{NP}$ in the first place. If we knew that this is true we would have no need to run $B$ on $\mathsf{P}=\mathsf{NP}$.

Second, it assumes that we know $B$ while the above argument only shows that some $B$ must exist. It might be the case that $B$ exists but we don't know it. Moreover, if $B$ existed and we knew it, then $B$ itself would be a proof that $\mathsf{P}=\mathsf{NP}$.

Third: Suppose that $\mathsf{P}=\mathsf{NP}$ (but we don't know it) and that we have some magic candidate algorithm $B$. $B$ is only able to decide whether an input statement admits short proofs. By short I mean proofs whose lengths are upper bounded by $n^c$, where $n$ is the length of the statement, and $c$ is a constant of choice. How do you pick $c$? We don't know how long a proof of $\mathsf{P}=\mathsf{NP}$ is.

Finally, notice that $\mathsf{P}=\mathsf{NP}$ is a specific statement. Therefore, if we assume that "$\mathsf{P}=\mathsf{NP}$" can be proved either true or false, then we already have a constant-time algorithm that settles the matter. Consider the shortest proof written in binary (in some proof language) of "$\mathsf{P}=\mathsf{NP}$" or ""$\mathsf{P} \neq \mathsf{NP}$" and let $k$ be its length. Clearly $k$ is a fixed number. We can simply generate all possible proofs in lexicographic order and check whether each of them is a valid proof of either "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$". Eventually we will reach the proofs of length $k$. There are only finitely many proofs of length at most $k$ (namely $2^{k+1}-1$) and checking each of them requires a time upper bounded by some function $f(k)$. Therefore the overall running time is $O(2^k f(k)) = O(1)$. This constant can be huge and this does not bring us any closer to settling the $\mathsf{P}$ vs $\mathsf{NP}$ question.

Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given short proof of mathematical statement is valid then there must exist an algorithm $B$ that decides whether such a short proof exists. Let's use $B$ on the statement $\mathsf{P}=\mathsf{NP}$.

There are several problems with that. First it assumes that $\mathsf{P}=\mathsf{NP}$ in the first place. If we knew that this is true we would have no need to run $B$ on $\mathsf{P}=\mathsf{NP}$.

Second, it assumes that we know $B$ while the above argument only shows that some $B$ must exist. It might be the case that $B$ exists but we don't know it. Moreover, if $B$ existed and we knew it, then $B$ itself would be a proof that $\mathsf{P}=\mathsf{NP}$.

Third: Suppose that $\mathsf{P}=\mathsf{NP}$ (but we don't know it) and that we have some magic candidate algorithm $B$. $B$ is only able to decide whether an input statement admits short proofs. By short I mean proofs whose lengths are upper bounded by $n^c$, where $n$ is the length of the statement, and $c$ is a constant of choice. How do you pick $c$? We don't know how long a proof of $\mathsf{P}=\mathsf{NP}$ is.

Finally, notice that $\mathsf{P}=\mathsf{NP}$ is a specific statement. Therefore, if we assume that "$\mathsf{P}=\mathsf{NP}$" can be proved either true or false, then we already have a constant-time algorithm that settles the matter. Consider the shortest proof written in binary (in some proof language) of $\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$" and let $k$ be its length. Clearly $k$ is a fixed number. We can simply generate all possible proofs and check whether each of them is a valid proof of either "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$". Eventually we will reach the proofs of length $k$. There are only finitely many proofs of length at most $k$ (namely $2^{k+1}-1$) and checking each of them requires a time upper bounded by some function $f(k)$. Therefore the overall running time is $O(2^k f(k)) = O(1)$. This constant can be huge and this does not bring us any closer to settling the $\mathsf{P}$ vs $\mathsf{NP}$ question.

Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given short proof of mathematical statement is valid then there must exist an algorithm $B$ that decides whether such a short proof exists. Let's use $B$ on the statement $\mathsf{P}=\mathsf{NP}$.

There are several problems with that. First it assumes that $\mathsf{P}=\mathsf{NP}$ in the first place. If we knew that this is true we would have no need to run $B$ on $\mathsf{P}=\mathsf{NP}$.

Second, it assumes that we know $B$ while the above argument only shows that some $B$ must exist. It might be the case that $B$ exists but we don't know it. Moreover, if $B$ existed and we knew it, then $B$ itself would be a proof that $\mathsf{P}=\mathsf{NP}$.

Third: Suppose that $\mathsf{P}=\mathsf{NP}$ (but we don't know it) and that we have some magic candidate algorithm $B$. $B$ is only able to decide whether an input statement admits short proofs. By short I mean proofs whose lengths are upper bounded by $n^c$, where $n$ is the length of the statement, and $c$ is a constant of choice. How do you pick $c$? We don't know how long a proof of $\mathsf{P}=\mathsf{NP}$ is.

Finally, notice that $\mathsf{P}=\mathsf{NP}$ is a specific statement. Therefore, if we assume that "$\mathsf{P}=\mathsf{NP}$" can be proved either true or false, then we already have a constant-time algorithm that settles the matter. Consider the shortest proof written in binary (in some proof language) of "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$" and let $k$ be its length. Clearly $k$ is a fixed number. We can simply generate all possible proofs in lexicographic order and check whether each of them is a valid proof of either "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$". Eventually we will reach the proofs of length $k$. There are only finitely many proofs of length at most $k$ (namely $2^{k+1}-1$) and checking each of them requires a time upper bounded by some function $f(k)$. Therefore the overall running time is $O(2^k f(k)) = O(1)$. This constant can be huge and this does not bring us any closer to settling the $\mathsf{P}$ vs $\mathsf{NP}$ question.

added 123 characters in body
Source Link
Steven
  • 29.6k
  • 2
  • 28
  • 49

Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given short proof of mathematical statement is valid then there must exist an algorithm $B$ that decides whether such a short proof exists. Let's use $B$ on the statement $\mathsf{P}=\mathsf{NP}$.

There are several problems with that. First it assumes that $\mathsf{P}=\mathsf{NP}$ in the first place. If we knew that this is true we would have no need to run $B$ on $\mathsf{P}=\mathsf{NP}$.

Second, it assumes that we know $B$ while the above argument only shows that some $B$ must exist. It might be the case that $B$ exists but we don't know it. Moreover, if $B$ existed and we knew it, then $B$ itself would be a proof that $\mathsf{P}=\mathsf{NP}$.

Third: Suppose that $\mathsf{P}=\mathsf{NP}$ (but we don't know it) and that we have some magic candidate algorithm $B$. $B$ is only able to decide whether an input statement admits short proofs. By short I mean proofs whose lengths are upper bounded by $n^c$, where $n$ is the length of the statement, and $c$ is a constant of choice. How do you pick $c$? We don't know how long a proof of $\mathsf{P}=\mathsf{NP}$ is.

Finally, notice that $\mathsf{P}=\mathsf{NP}$ is a specific statement. Therefore, if we assume that "$\mathsf{P}=\mathsf{NP}$" can be proved either true or false, then we already have a constant-time algorithm that settles the matter. Consider the shortest proof written in binary (in some proof language) of $\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$" and let $k$ be its length. Clearly $k$ is a fixed number. We can simply generate all possible proofs and check whether each of them is a valid proof of either "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$". Eventually we will reach the proofs of length $k$. There are only finitely many proofs of length at most $k$ (namely $2^{k+1}-1$) and checking each of them requires a time upper bounded by some function $f(k)$. Therefore the overall running time is $O(2^k f(k)) = O(1)$. This constant can be huge and this does not bring us any closer to settling the $\mathsf{P}$ vs $\mathsf{NP}$ question.

Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given short proof of mathematical statement is valid then there must exist an algorithm $B$ that decides whether such a short proof exists. Let's use $B$ on the statement $\mathsf{P}=\mathsf{NP}$.

There are several problems with that. First it assumes that $\mathsf{P}=\mathsf{NP}$ in the first place. If we knew that this is true we would have no need to run $B$ on $\mathsf{P}=\mathsf{NP}$.

Second, it assumes that we know $B$ while the above argument only shows that some $B$ must exist. It might be the case that $B$ exists but we don't know it. Moreover, if $B$ existed and we knew it, then $B$ itself would be a proof that $\mathsf{P}=\mathsf{NP}$.

Third: Suppose that $\mathsf{P}=\mathsf{NP}$ (but we don't know it) and that we have some magic candidate algorithm $B$. $B$ is only able to decide whether an input statement admits short proofs. By short I mean proofs whose lengths are upper bounded by $n^c$, where $n$ is the length of the statement, and $c$ is a constant of choice. How do you pick $c$? We don't know how long a proof of $\mathsf{P}=\mathsf{NP}$ is.

Finally, notice that $\mathsf{P}=\mathsf{NP}$ is a specific statement. Therefore, if we assume that "$\mathsf{P}=\mathsf{NP}$" can be proved either true or false, then we already have a constant-time algorithm that settles the matter. Consider the shortest proof written in binary (in some proof language) of $\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$" and let $k$ be its length. Clearly $k$ is a fixed number. We can simply generate all possible proofs and check whether each of them is a valid proof of either "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$". Eventually we will reach the proofs of length $k$. There are only finitely many proofs of length at most $k$ (namely $2^{k+1}-1$) and checking each of them requires a time upper bounded by some function $f(k)$. Therefore the overall running time is $O(2^k f(k)) = O(1)$.

Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given short proof of mathematical statement is valid then there must exist an algorithm $B$ that decides whether such a short proof exists. Let's use $B$ on the statement $\mathsf{P}=\mathsf{NP}$.

There are several problems with that. First it assumes that $\mathsf{P}=\mathsf{NP}$ in the first place. If we knew that this is true we would have no need to run $B$ on $\mathsf{P}=\mathsf{NP}$.

Second, it assumes that we know $B$ while the above argument only shows that some $B$ must exist. It might be the case that $B$ exists but we don't know it. Moreover, if $B$ existed and we knew it, then $B$ itself would be a proof that $\mathsf{P}=\mathsf{NP}$.

Third: Suppose that $\mathsf{P}=\mathsf{NP}$ (but we don't know it) and that we have some magic candidate algorithm $B$. $B$ is only able to decide whether an input statement admits short proofs. By short I mean proofs whose lengths are upper bounded by $n^c$, where $n$ is the length of the statement, and $c$ is a constant of choice. How do you pick $c$? We don't know how long a proof of $\mathsf{P}=\mathsf{NP}$ is.

Finally, notice that $\mathsf{P}=\mathsf{NP}$ is a specific statement. Therefore, if we assume that "$\mathsf{P}=\mathsf{NP}$" can be proved either true or false, then we already have a constant-time algorithm that settles the matter. Consider the shortest proof written in binary (in some proof language) of $\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$" and let $k$ be its length. Clearly $k$ is a fixed number. We can simply generate all possible proofs and check whether each of them is a valid proof of either "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$". Eventually we will reach the proofs of length $k$. There are only finitely many proofs of length at most $k$ (namely $2^{k+1}-1$) and checking each of them requires a time upper bounded by some function $f(k)$. Therefore the overall running time is $O(2^k f(k)) = O(1)$. This constant can be huge and this does not bring us any closer to settling the $\mathsf{P}$ vs $\mathsf{NP}$ question.

Source Link
Steven
  • 29.6k
  • 2
  • 28
  • 49

Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given short proof of mathematical statement is valid then there must exist an algorithm $B$ that decides whether such a short proof exists. Let's use $B$ on the statement $\mathsf{P}=\mathsf{NP}$.

There are several problems with that. First it assumes that $\mathsf{P}=\mathsf{NP}$ in the first place. If we knew that this is true we would have no need to run $B$ on $\mathsf{P}=\mathsf{NP}$.

Second, it assumes that we know $B$ while the above argument only shows that some $B$ must exist. It might be the case that $B$ exists but we don't know it. Moreover, if $B$ existed and we knew it, then $B$ itself would be a proof that $\mathsf{P}=\mathsf{NP}$.

Third: Suppose that $\mathsf{P}=\mathsf{NP}$ (but we don't know it) and that we have some magic candidate algorithm $B$. $B$ is only able to decide whether an input statement admits short proofs. By short I mean proofs whose lengths are upper bounded by $n^c$, where $n$ is the length of the statement, and $c$ is a constant of choice. How do you pick $c$? We don't know how long a proof of $\mathsf{P}=\mathsf{NP}$ is.

Finally, notice that $\mathsf{P}=\mathsf{NP}$ is a specific statement. Therefore, if we assume that "$\mathsf{P}=\mathsf{NP}$" can be proved either true or false, then we already have a constant-time algorithm that settles the matter. Consider the shortest proof written in binary (in some proof language) of $\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$" and let $k$ be its length. Clearly $k$ is a fixed number. We can simply generate all possible proofs and check whether each of them is a valid proof of either "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$". Eventually we will reach the proofs of length $k$. There are only finitely many proofs of length at most $k$ (namely $2^{k+1}-1$) and checking each of them requires a time upper bounded by some function $f(k)$. Therefore the overall running time is $O(2^k f(k)) = O(1)$.