# algorithms – The 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
complement X is in the complexity class NP. In other words,
co-NP is the class of problems for which there is a polynomial algorithm that can check for "no" instances – wikipedia

## What I think I know

= Problems with effective algorithms to find solutions

With regard to the input size, that is the number of basic steps and
The algorithm takes a size input. The size of an entry 𝑥 is
if there is need for 𝑛 bits of computer memory to store, in which case we
write | 𝑥 | = 𝑛.-Definitions Answer

I interpret this as an entry that would take linear time, it would be to find the solution to 2 + 2.

## 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 first}

For a string s on an alphabet, let's shift (s) the set of circular offsets of s and for a set L of strings, shift (L) denotes the set of all the circular offsets of strings in L If L is a cyclic code, then offset (L) L; it is a necessary condition for L to be a cyclic language.

My algorithm follows a 3×3 shift language allowing valid Sudoku grids. Grids valid up to 50×50 and apparently 100×100 have been generated up to now.

Wikipedia,
Cyclic language,
Sparse language

## Proof pseudo Sudoku forced

As stated in the definition of co-NP, a decision problem "X" is a member of co-np if and only if its complement X belongs to the complexity class "NP". As mentioned before, co-np is the class of problems for which a multiple verifier can not say any instance. I'm using an algorithm that basically says "no" when I test the validity of a general puzzle. If it does not follow the circular language. He says "not a constrained puzzle." Therefore, Sudoku constrained is co-np.

Assuming that the cyclic language is maintained indefinitely.

Cyclic permutation

Let n = enter

Let k = shift (L)

Pn = (n-k)!

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

In reduced form

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

## Bytecode

``````if the indexes / elements match in the grid and follow the offset language (L):

print "yes"
other:

print "no"
``````

Overall, is this evidence sufficient that Sudoku constrains is co-np?

Constrained Sudoku Algorithm

Posted on