4 ms·

The example given doesn't seem right to me. > There is one problem, though, that I find easily explainable. Place a token at the bottom left corner of a grid t

The example given doesn't seem right to me. > There is one problem, though, that I find easily explainable. Place a token at the bottom left corner of a grid that extends infinitely up and right, call that point (0, 0). You're given list of valid displacement moves for the token, like (+1, +0), (-20, +13), (-5, -6), etc, and a target point like (700, 1). You may make any sequence of moves in any order, as long as no move ever puts the token off the grid. Does any sequence of moves bring you to the target? If someone gives you such a sequence, it seems trivial to verify it in linear time. Even for arbitrary dimensions, and such witness can be verified in linear time.

Choco31415 2y ago
A sequence is easy to verify. Choosing the sequence not so much. Roughly put that is the certificate definition of being in NP.
- andrewla 2y ago
  The goal here was to show that it was strictly NP-hard, i.e. harder than any problem in NP.
  - Nevermark 2y ago
    Harder to solve, not necessarily harder to verify? If I am understanding things right.
    - andrewla 2y ago
      The crazy thing about the definition of NP-completeness is that Cook's theorem says that all problems in NP can be reduced in polynomial time to an NP-complete problem. So if a witness to a problem can be verified in polynomial time, it is by definition in NP and can be reduced to an NP-complete problem. If I can verify a solution to this problem by finding a path in polynomial time, it is by definition in NP. The goal here was to present an example of a problem known to not be in NP.
      - thaumasiotes 2y ago
        > The crazy thing about the definition of NP-completeness is that Cook's theorem says that all problems in NP can be reduced in polynomial time to an NP-complete problem. What were you trying to say here? Cook's theorem says that SAT is NP-complete. "All problems in NP can be reduced in polynomial time to an NP-complete problem" is just a part of the definition of NP-completeness.
quickthrower27 2y ago
[dead]
trixthethird 2y ago
Linear time in the length of the sequence, yes. But is the sequence length linear in dimension size, or number of moves given? Thats what is interesting.
- bjornsing 2y ago
  It doesn’t need to be linear though. Polynomial is enough. But I guess it can be proven that the shortest possible sequence grows faster than polynomial.
  - trixthethird 2y ago
    I think they proved it grows with Ackermann function.
    - bjornsing 2y ago
      Sounds implausible… Number of computational steps to find the shortest sequence maybe grows with Ackermann function. But length of the shortest sequence?
      - trixthethird 2y ago
        I think you are right. I just read this article linked in the OP: https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/ https://www.quantamagazine.org/an-easy-sounding-problem-yiel...
  - hwayne 2y ago
    Proving it's nonpolynomial is pretty easy: just make the goal vector `(10, 10, 10)` and the displacement vectors `{(1, 0, 0), (-10, 1, 0), (-10, -10, 1)}`. It takes ~1000 steps to reach the goal, and if we add one more dimension we need 10x more steps. So it grows, at least, exponentially. Back in 1970ish someone found a problem that's at least double-exponential, proving it was 2-EXPTIME-hard. It was conjectured to be 2-EXPTIME-complete for the longest time, but turned out to be significantly harder.
hwayne 2y ago
To be in NP, witness must be verifiable in polynomial time with respect to the size of the original input. In this problem (VAS Reachability), the solution can be `2^2^2^...^K` steps long. Even if that's linear with respect to the witness, it's not polynomial with respect to the set of moves + goal.
- andrewla 2y ago
  Hmm.. I'd love to see a more formal statement of this, because it feels unintuitive. Notably the question "given a number as input, output as many 1's as that number" is exponential in the input size. Is this problem therefore also strictly NP-hard?
  - johntb86 2y ago
    It needs to be a decision problem (or easily recast as a decision problem). "given a number as input, output as many 1's as that number" doesn't have a yes or no answer. You could try to ask a related question like "given a number as input and a list of 1s, are there as many 1s as the number?" but that has a very large input.
    - andrewla 2y ago
      Straightforward to pose as a decision problem -- you're given a sequence of {0,1} representing a base-2 input (N), output a string of {0, 1} such that there are N 1's. You could make it "N 1s followed by N 0s" to avoid being too trivial, but even in the original formulation there are plenty of "wrong" answers for each value of N, and determining whether a witness is correct requires O(2^b) time, where b is the number of bits in N.
      - deleted 2y ago
        [deleted]
      - bubblyworld 2y ago
        That's not a decision problem either. You need to cast it in the form of determining membership in some set of strings (the "language"). In this case the natural choice of language is the set of all strings of the form "{encoding of n}{1111....1 n times}", which is decidable in O(log(n)+n) steps, i.e. linear time.

Choco31415 2y ago

A sequence is easy to verify. Choosing the sequence not so much. Roughly put that is the certificate definition of being in NP.

andrewla 2y ago
The goal here was to show that it was strictly NP-hard, i.e. harder than any problem in NP.
- Nevermark 2y ago
  Harder to solve, not necessarily harder to verify? If I am understanding things right.
  - andrewla 2y ago
    The crazy thing about the definition of NP-completeness is that Cook's theorem says that all problems in NP can be reduced in polynomial time to an NP-complete problem. So if a witness to a problem can be verified in polynomial time, it is by definition in NP and can be reduced to an NP-complete problem. If I can verify a solution to this problem by finding a path in polynomial time, it is by definition in NP. The goal here was to present an example of a problem known to not be in NP.
    - thaumasiotes 2y ago
      > The crazy thing about the definition of NP-completeness is that Cook's theorem says that all problems in NP can be reduced in polynomial time to an NP-complete problem. What were you trying to say here? Cook's theorem says that SAT is NP-complete. "All problems in NP can be reduced in polynomial time to an NP-complete problem" is just a part of the definition of NP-completeness.

quickthrower27 2y ago

[dead]

trixthethird 2y ago

Linear time in the length of the sequence, yes. But is the sequence length linear in dimension size, or number of moves given? Thats what is interesting.

bjornsing 2y ago
It doesn’t need to be linear though. Polynomial is enough. But I guess it can be proven that the shortest possible sequence grows faster than polynomial.
- trixthethird 2y ago
  I think they proved it grows with Ackermann function.
  - bjornsing 2y ago
    Sounds implausible… Number of computational steps to find the shortest sequence maybe grows with Ackermann function. But length of the shortest sequence?
    - trixthethird 2y ago
      I think you are right. I just read this article linked in the OP: https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/ https://www.quantamagazine.org/an-easy-sounding-problem-yiel...
- hwayne 2y ago
  Proving it's nonpolynomial is pretty easy: just make the goal vector `(10, 10, 10)` and the displacement vectors `{(1, 0, 0), (-10, 1, 0), (-10, -10, 1)}`. It takes ~1000 steps to reach the goal, and if we add one more dimension we need 10x more steps. So it grows, at least, exponentially. Back in 1970ish someone found a problem that's at least double-exponential, proving it was 2-EXPTIME-hard. It was conjectured to be 2-EXPTIME-complete for the longest time, but turned out to be significantly harder.

hwayne 2y ago

To be in NP, witness must be verifiable in polynomial time with respect to the size of the original input. In this problem (VAS Reachability), the solution can be `2^2^2^...^K` steps long. Even if that's linear with respect to the witness, it's not polynomial with respect to the set of moves + goal.

andrewla 2y ago
Hmm.. I'd love to see a more formal statement of this, because it feels unintuitive. Notably the question "given a number as input, output as many 1's as that number" is exponential in the input size. Is this problem therefore also strictly NP-hard?
- johntb86 2y ago
  It needs to be a decision problem (or easily recast as a decision problem). "given a number as input, output as many 1's as that number" doesn't have a yes or no answer. You could try to ask a related question like "given a number as input and a list of 1s, are there as many 1s as the number?" but that has a very large input.
  - andrewla 2y ago
    Straightforward to pose as a decision problem -- you're given a sequence of {0,1} representing a base-2 input (N), output a string of {0, 1} such that there are N 1's. You could make it "N 1s followed by N 0s" to avoid being too trivial, but even in the original formulation there are plenty of "wrong" answers for each value of N, and determining whether a witness is correct requires O(2^b) time, where b is the number of bits in N.
    - deleted 2y ago
      [deleted]
    - bubblyworld 2y ago
      That's not a decision problem either. You need to cast it in the form of determining membership in some set of strings (the "language"). In this case the natural choice of language is the set of all strings of the form "{encoding of n}{1111....1 n times}", which is decidable in O(log(n)+n) steps, i.e. linear time.