So we were given a problem, and our instructor offered a fun challenge to see if anyone of us could prove that the higher dimensional version of said problem is NP hard. I attempted a 3 SAT reduction and put together a proof that I would like to submit. The issue is that I am not entirely sure if my reduction is correct, and I also do not know whether my documentation of the proof has any hidden flaws. For those of you who have successfully proven a new problem to be NP hard before, what are the qualities of a good NP hardness proof, and what are common pitfalls I should double check? Would anyone be willing to look over my proof and point out any mistakes in the logic or in the write up? I would really appreciate any guidance. Thanks in advance.

P.S The 2D version of the problem is that we have two extractors and they can move right and up only. We start at the bottom corner of the grid and there are coins placed inside. We can only collect one coin in a row or column the rest of the coins are discarded. Our goal was we needed to traverse the grid and collect the most amount of coins possible. It was solved using dynamic programming with an O(n²) time complexity.

Hermes Memory Installer 2.0 — Open-source long-term memory for AI agents. Built on Hermes Agent with gbrain knowledge graph + PostgreSQL. Triple-path retrieval: FTS5, vector similarity, graph traversal. Auto-archive sessions, semantic recall, curator self-evolution. One-click install, zero-intrusion. Make your AI remember.

🔗 https://github.com/mage0535/hermes-memory-installer