Proving NP hardness in Puzzle with SAT reduction

Question

Introduction

I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on circular matrix shift of elements. It does so in such a way that allows valid grids to be formed. Explained Here-1 and Here-2 and Grid generation and Grid generation written in Python

SAT Instance Used

I have taken this SAT instance from this linked pdf on page 3 and reduced to a 3-SAT instance.

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3) ∧ x5

SAT reduced into 3-SAT

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3 ∨ x1)

Here are the definitions for the variables.

shift(L) = the circular shifts

x1 = shift(L) to generate valid n^2 x n^2 grid and puzzle

x2 = shift(L) to generate another valid n^2 x n^2 grid and puzzle

¬x4 = valid grids and puzzles not following shift(L)

¬x3 = another valid grid and its puzzle not following shift(L)

Explanation of the purpose of the 3-SAT instance

When x1 and x2 are true (shift(L) grids and puzzles)

Then the output is True (shift(L) puzzles/grid)

When x1 and/or x2 is not shift(L)... false.

While the negated form is basically a "not false"

Therefore the output is false because no two puzzles are made from shift(L)

Question

Did I prove correctly that my puzzles are NP-hard assuming that the language used to generate these grids never have missing instances?

Answer 1

As far as I can tell, no, you have not proved NP-hardness of your puzzle. NP-hardness is precisely defined. If you want to prove a mathematical statement, you must do mathematical work and can't get there by only hope and intuition.

If you want to show that problem X is hard by a polynomial-time reduction from 3-SAT, you should proceed as follows. Take any arbitrary instance $I$ of 3-SAT and construct, in polynomial-time, an instance $I'$ of X. Once you've done this, prove that $I$ has a solution if and only if $I'$ has a solution. This is the "mathematical part", where you use the properties of $I$ and $I'$ to argue for both implications; you need some insight and practice in writing mathematical proofs, where in the argument the next step follows from the previous.

For example, contrary to what you seem to say, you can't show hardness by reducing one fixed instance of 3-SAT to your problem X.

If all this feels confusing but you are still excited, I recommend that you:

1. Read the relevant definitions of NP, NP-hardness and polynomial-time reductions. Think about what they mean intuitively as well.

2. Look at examples of reductions and NP-completeness proofs. Don't expect to get it straight away, but be willing to do some work. There are plenty of exercises out there and many questions on this site too.

3. Come back to your original problem later, perhaps after getting a little bit more familiar with writing proofs in general.