7 ms·

Which NP tasks? ("Some" NP tasks are already possible in polynomial time)

• trashtoss 10y ago
  Seconding the question because I want to see the encodings. Intuitively this makes sense: in the GA formalism a "single" term requires 2^n fields (where n is the spatial dimension), and "simple" operations like addition and multiplication thus require 2^n (or more) operations to evaluate. If you could instead somehow do those operations in O(1) time you would clearly pick up a rather nice speedup, but again I'm curious what the problems and encodings (as GA) actually look like.
  • trashtoss 10y ago
    Actually easy to find, for example here: https://members.loria.fr/RSchott/staceyredujanv08.pdf https://members.loria.fr/RSchott/staceyredujanv08.pdf .
    • macawfish 10y ago
      Yup, that's what I was thinking of.
• ajamesm 10y ago
  Is this a genuine question, or are you trying to be blasé about employing the Socratic Method on HN?
• macawfish 10y ago
  This paper mentions the Hamiltonian cycle problem for graphs: https://members.loria.fr/RSchott/staceyredujanv08.pdf https://members.loria.fr/RSchott/staceyredujanv08.pdf
• deleted 10y ago
  [deleted]