0
$\begingroup$

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.

Wikipedia, Cyclic language, Sparse Language

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

Constrained Sudoku Pseudo Proof

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's weird, the concept would have to be incredibly complex for English not to work. $\endgroup$ – Travis Wells Apr 28 at 2:16
  • $\begingroup$ @TravisWells, the issue is not so much that it is in English as that it is a summary. $\endgroup$ – D.W. Apr 28 at 2:24
  • $\begingroup$ 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. $\endgroup$ – Travis Wells Apr 28 at 2:27
  • $\begingroup$ 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??? $\endgroup$ – Travis Wells Apr 28 at 4:50
  • $\begingroup$ @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. $\endgroup$ – gnasher729 Apr 28 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.