User:Hakerh400/Proof 001

Let $S$ be the set of all finite strings of bits and let $P$ be a subset of $S$ such that $|P|=|S|$. Binary operator $+$ when applied on strings represent string concatenation.

Lemma 1. If for each $x\in S$ determining whether $x\in P$ is computable and there exists a total computable predicate $f$ that for each $x\in S$ determines whether there exists $y\in S$ such that $(x+y)\in P$, then there exists a computable bijection between $P$ and ${\mathbb {N}}$, where ${\mathbb {N}}$ is the set of natural numbers

Proof. Suppose that there is such $f$. We show an algorithm for constructing $g:{\mathbb {N}}\to P$ and $h:P\to {\mathbb {N}}$ using $f$, such that $g^{-1}(x)=h(x)$. We implement function g in Haskell:

data Bit = B0 | B1 deriving Eq g :: Integer -> [Bit] g n = g1 n [] True where g1 :: Integer -> [Bit] -> Bool -> [Bit] g1 n str allowEnd | end = ifEnd | append0 && append1 = ifBoth | append0 = next B0 | append1 = next B1 where end = allowEnd && (p str) append0 = f $ str ++ [B0] append1 = f $ str ++ [B1] ifEnd :: [Bit] ifEnd | n == 0 = str | n /= 0 = g1 (n - 1) str False ifBoth :: [Bit] ifBoth = g1 (n `div` 2) (str ++ [int2bit $ n .&. 1]) True next :: Bit -> [Bit] next a = g1 n (str ++ [a]) True int2bit :: Integer -> Bit int2bit 0 = B0 int2bit 1 = B1

Function p determines whether a binary string belongs to $P$, and function f satisfies the definition given in the lemma. While n is nonzero, in each recursive call of g1 the integer n either decreases, or parameter allowEnd goes from True to False, and when it goes to False in the next iteration either n must decrease, or the recursion base case is hit. If n is zero, then at most finite amount of recursive calls will be performed (until end becomes True), and it is guaranteed by f that it terminates.

Since $g$ is a total computable function and since we can enumerate all possible strings in P by eliminating strings from S that are not in P, it proves that the inverse of $g$ (which is $h$) is also a total computable function.

Corollaries

One of the interesting corollaries is that we can create a bijection between natural numbers and sudoku puzzles that have the following properties:

• The sudoku grid has dimensions $n\times n$, where $n$ is a perfect square
• At least one tile is empty
• There is exactly one valid solution
• If we remove any number that is already given, the solution will no longer be unique

This is usually a description of a good and hard sudoku puzzle. It is good because there is exactly one solution and it is hard because it has the minimum amount of given numbers. Each sudoku puzzle can be represented as an array of integers (and $n$ is the square root of the array's length). Since all integers are bounded, and each integer appears the same number of times for a fixed $n$, then for any fixed $n$, a sudoku with dimensions $n\times n$ can be represented using a fixed amount of bits. Clearly, we can well-define $P$ to contain only sudoku puzzles that are both good and hard. Then we can construct $f$ to check whether the given string of bits can be a pefix of some such sudoku. Finally, we can use $g$ to filter only sudoku puzzles that we are interested in. We can then reconstruct the sudoku grid from the bit array.

However, it can be shown that computing $f$, $g$ and $h$ is NP-hard, so it has at least exponential time complexity (assuming $P\neq NP$).