4 ms·

> Could the P versus NP question itself be NP-hard, and therefore impossible to solve? Is there a way to formulate or rephrase this such that we could effectiv

> Could the P versus NP question itself be NP-hard, and therefore impossible to solve? Is there a way to formulate or rephrase this such that we could effectively ask this question? I'm thinking like some way of formally encoding the question (does P=NP?) that could be plugged into a turing machine which then computes the answer.

mrkeen 2y ago
Probably not! Thinking of a way for smart people to formally encode questions and hand them off to dumb computers is what led to the whole field of computing in the first place!
- deleted 2y ago
  [deleted]
Delk 2y ago
It seems that at least some theorists believe the P vs NP question isn't even provable using our current axioms, and that a proof would require new mathematics.
raincole 2y ago
I think "effectively ask this question" is quite ambiguous here. The original question implying NP-hard problems are "impossible to solve", which already makes no sense.
- pvillano 2y ago
  Pulling intent out of a invalid statement is difficult but I think the intent is something like > Could the P versus NP question itself be [mathy-difficult in a way] that makes it impossible [for humanity to know the answer]? Which becomes a family of interesting questions when you substitute exact expressions for the bracketed natural language
zeroonetwothree 2y ago
Single values cannot be “NP Hard”. Hardness applies to a class of problems. So it may be NP Hard to compute “prove or disprove X” but this says nothing for any individual value of X. Similarly the traveling salesman problem is NP Hard but there are inputs that have trivial outputs.
poikroequ 2y ago
I realize now it doesn't make sense to ask if it's np-hard. Chess can be solved in constant time because there are finitely many board positions. But there are "generalized" versions of chess where the board and number of pieces can grow infinitely, then it makes sense to ask questions about complexity. I guess I was thinking something along those lines. Perhaps if there's a way to "generalize" the P vs NP question, then we can hypothetically give some mildly meaningful answer about complexity.

mrkeen 2y ago

Probably not! Thinking of a way for smart people to formally encode questions and hand them off to dumb computers is what led to the whole field of computing in the first place!

deleted 2y ago
[deleted]

Delk 2y ago

It seems that at least some theorists believe the P vs NP question isn't even provable using our current axioms, and that a proof would require new mathematics.

raincole 2y ago

I think "effectively ask this question" is quite ambiguous here. The original question implying NP-hard problems are "impossible to solve", which already makes no sense.

pvillano 2y ago
Pulling intent out of a invalid statement is difficult but I think the intent is something like > Could the P versus NP question itself be [mathy-difficult in a way] that makes it impossible [for humanity to know the answer]? Which becomes a family of interesting questions when you substitute exact expressions for the bracketed natural language

zeroonetwothree 2y ago

Single values cannot be “NP Hard”. Hardness applies to a class of problems. So it may be NP Hard to compute “prove or disprove X” but this says nothing for any individual value of X. Similarly the traveling salesman problem is NP Hard but there are inputs that have trivial outputs.

poikroequ 2y ago

I realize now it doesn't make sense to ask if it's np-hard. Chess can be solved in constant time because there are finitely many board positions. But there are "generalized" versions of chess where the board and number of pieces can grow infinitely, then it makes sense to ask questions about complexity. I guess I was thinking something along those lines. Perhaps if there's a way to "generalize" the P vs NP question, then we can hypothetically give some mildly meaningful answer about complexity.