# Pseudo-Proof of Constrained Sudoku is co-np

## The definition of CO-NP

A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. In other words, co-NP is the class of problems for which there is a polynomial-time algorithm that can verify "no" instances - wikipedia

## Sparse-Language

Where all strings have the form 1k, where "1" can be any fixed symbol. For example, the language {1, 111, 1111} is unary, as is the language {1k | k is prime}

For a string s over an alphabet Σ, let shift(s) denote the set of circular shifts of s, and for a set L of strings, let shift(L) denote the set of all circular shifts of strings in L. If L is a cyclic code, then shift(L) ⊆ L; this is a necessary condition for L being a cyclic language.

My algorithm follows a 3x3 shift language allowing valid Sudoku Grids. Valid grids up to 50x50 and seemingly 100x100 so far have been generated.

The language used by this algorithm is a 3x3 circular shift. A cyclic code of permutes allowing valid grid.

## What I'm trying to do/Decision Problem

I'm trying to compare two grids. One non-constrained and the other constrained. Both grids are technically valid but within their own "class"

Determine if a valid Sudoku grid is of the conventional class or the constrained class following the shift(L) circular language.

As mentioned in the co-NP definition a decision problem "X" is a member of co-np if and only if its complement X is in the complexity class "NP." As said before, co-np is the class of problems for which a poly verifier can say no instances. The algorithm verifies no instances for grids. If it does not follow the circular language. It says, "not a constrained puzzle." Therefore, Constrained Sudoku is co-np.

Assuming, that the cyclic language is maintained indefinitely.

Cyclic Permutation

let n = input

let k = shift(L)

Pn = (n-k)!

(n-3)! == lim_(n->∞) 3 = 3

In reduced form

(n - 3)! = n->∞-k

## Pseudo-Code

if indexes/elements match in grid and follows  shift(L) language:

print "yes"
else:

print "no"


Overall, is this sufficient proof that Constrained Sudoku is co-np?

Constrained Sudoku Algorithm

No, it's not a persuasive proof.

Before you can have a valid proof, you must first precisely state whatever it is you are trying to prove. You haven't done that.

A language (a decision problem) is in co-NP if it satisfies certain requirements. You have not defined a language; you have not defined a decision problem. You use the phrase "Constrained Sudoku" but you have not given a precise definition of what formal language that is intended to refer to.

What you list as a "definition" of co-NP is actually an English-language summary of the definition; it's not a substitute for knowing the precise mathematical definition.

The reasoning in your "proof" is faulty. You write:

I use an algorithm that in essence says "no" when [...]. Therefore, Constrained Sudoku is co-np.

That doesn't follow. Just because you have an algorithm that sometimes says no, doesn't mean that the corresponding problem is in co-NP. There are additional requirements, which you haven't checked.

I'd like to give some general advice. Before trying to tackle this problem, I suggest you spend a bunch of time studying the fundamentals. Set aside Sudoku and your ideas for a few weeks, and find an online course where you can learn complexity theory. That will give you a mathematical framework that, once you've learned it, you can come back and apply to Sudoku. Until you've done that, it is pointless to continue trying to frame questions like this.

• That's weird, the concept would have to be incredibly complex for English not to work. – Travis Wells Apr 28 '19 at 2:16
• @TravisWells, the issue is not so much that it is in English as that it is a summary. – D.W. Apr 28 '19 at 2:24
• Following the summary, is not enough to understand. The algorithm has always said no when I provided a non-constrained Sudoku grid. I thought that might be something. – Travis Wells Apr 28 '19 at 2:27
• I do not understand fully. Given two choices my algorithm tests two valid sudoku grids. 1 being a non-constrained and the other one being a constrained. It then verifies a no answer in poly time for the non-constrained. Why is this not co-np??? – Travis Wells Apr 28 '19 at 4:50
• @TravisWells It would really help if you defined what "Constrained Sudoku" is supposed to be. I frankly haven't got the slightest clue what you are trying to prove. – gnasher729 Apr 28 '19 at 16:53