• Dandroid@dandroid.app
    link
    fedilink
    arrow-up
    1
    ·
    1 year ago

    Aren’t Sudoku and protein folding essentially the same problem? Like, if you could write a computer program to solve sudoku in polynomial time, you could adapt that solution to solve protein folding problems in polynomial time? Or something like that.

    Someone who is smarter than me, please chime in.

    • Barbacamanitu@lemmy.world
      link
      fedilink
      arrow-up
      1
      ·
      1 year ago

      I heard on Stephen Wolfram’s podcast the other day that all NP Hard problems are equivalent. For example, you can embed the halting problem within the traveling salesman problem and vice versa. I believe this means that solving one would automatically solve all the others.

    • phorq@lemmy.ml
      link
      fedilink
      arrow-up
      0
      ·
      1 year ago

      You’re talking about the theory of p = np. The idea that any problem whose solution can be verified quickly can also be solved quickly. This has not been proven or disproven, it’s a bit of an open mystery in computer science, but most are under the impression this is not the case and that p != np. Someone smarter than me please verify my explanation in linear time please.

      • Riven@sh.itjust.works
        link
        fedilink
        arrow-up
        0
        ·
        1 year ago

        Specifically I think they’re talking about the subclass of np problems called “np complete” that are functionally identical to each other in some mathy way such that solving one of them instantly gives you a method to solve all of them.

        • Barbacamanitu@lemmy.world
          link
          fedilink
          arrow-up
          1
          ·
          1 year ago

          Is it only no complete? Or does this include np-hard? I just posted a comment about this and thought it applied to np-hard.

          • Riven@sh.itjust.works
            link
            fedilink
            arrow-up
            1
            ·
            1 year ago

            My understanding is that it’s layered. An np-complete solution solves all np and np-complete problems, and an np-hard solution solves all np, np-complete, and np-hard problems.

            Of course by “np” here I mean non-complete non-hard np problems.